Cette documentation est issue de celle contenue dans la librairie Graphstream.
GraphStream is a library concerned about graphs and how to deal with them. It would have been justified to create a new graph library simply because it is important to reinvent the wheel at least three times a day, but in addition we added a concept rarely found in graph libraries: we see a graph as a dynamic entity which can constantly evolve. Not only it can evolve in its values and attributes (values associated with each edge and node), but its structure may change at any time. In other words, the number of edges and nodes may vary in time.
Although this salient feature driven the whole development of the project, we tried to make GraphStream also adequate to deal with non-evolving graphs, and the API devotes a whole set of algorithms to what we will call static graphs.
We have tried to make GraphStream as easy to both learn and use as possible (as always without considering the user is dumb and letting him master details if needed and wanted). However the API has grown and may seen impressive at first. To demonstrate you this is not the case, we propose you to read the example code that is given a paragraph under. However if you are new to the project, the better way to apprehend the API is to run through the various proposed tutorials before reading this guide. Indeed this programmer's guide is more like a specification than a way to discover the API. It is made for reference, not for learning.
So, before entering into the details let's helloworld with GraphStream as promised. We will see how to create a simple graph and display it:
import org.miv.graphstream.graph.Graph;
public class Test
{
public static void main( String args[] )
{
Graph graph = new Graph( "Hello, world!", false, true );
graph.addEdge( "AB", "A", "B" );
graph.addEdge( "BC", "B", "C" );
graph.addEdge( "CD", "C", "D" );
graph.addEdge( "DA", "D", "A" );
graph.addEdge( "AC", "A", "C" );
graph.addEdge( "BD", "B", "D" );
graph.display();
}
}
We hope this is easy enough. If this is not the case you should probably consult a specialist.
The package “org.miv.graphstream.graph” contains classes allowing to build a graph, evolve it, and manipulate it. The main class is the “Graph” class. Creating a graph is simple:
"Graph myGraph = new Graph( "graphName" );"
The argument given to the constructor is the name of the graph and its unique identifier. It is mandatory since, in a graph, all elements must have a unique way of being identified, and the graph itself must follow this rule.
Indeed, all components that make up a graph, the graph itself, nodes and edges are all elements that may appear inside another graph. This means that graphs can be nested.
Inside a graph, all elements must be easily retrievable. This is why each of them has an unique name. This is the identifier, or id for short, and it must be a text string. Here is the class hierarchy for all components of a graph:
"Element | +--- Graph | +--- Node | +--- Edge"
Now that you know that a graph must absolutely have an identifier, we can tell you: the “Graph” class can be constructed without this identifier:
"Graph myGraph = new Graph();"
Indeed the graph will have the empty string identifier. This constructor has been added to simplify programs where an unique graph is used. Now, you know you should never forget to give your graph an identifier.
But the “Element” class contains more than an id. It is also considered as a list of attributes. This means that each graph, node or edge can have an arbitrary number of attributes. This is a central feature of the element class, since it allows to store data used by algorithms that will work with the graph.
An attribute is identified by a key (a text string). For one given element all attributes must have a distinct key, however several different elements may contain attributes that have the same key. For example, all nodes may have the attribute “color”, but a node cannot have two “color” attributes.
The attribute key points to arbitrary data stored as an Object in the attribute list. To add an attribute inside an element use:
"Element.addAttribute( String key, Object value );"
To change the value of an attribute, use:
"Element.changeAttribute( String key, Object value );"
But note that in fact, this is strictly equivalent to the “addElement()” method: adding an attribute that already exist merely overwrite it (the two methods are indeed the same, and the second is only here for clarity).
To remove an attribute use:
"Element.removeAttribute( String key )"
To test if an element has an attribute, use
"boolean Element.hasAttribute( String key );"
And finally to obtain the value of an attribute use:
"Object Element.getAttribute( String key );"
This returns the value of the attribute identified by the given key, or null if no attribute matches the key. Always think to verify the attribute is not null.
As attributes are stored as objects, without specifying their type, you will often end in first fetching the attribute using “getAttribute()” then verifying if the attribute is of the expected type (and if you do not, you probably should). To simplify this, the following method exists:
"Object Element.getAttribute( String key, Class clazz )"
If returns the attribute value if and only if it is an instance of the given class. Else it returns null, even if the attribute has a value that does not match the given class.
You can also iterate on all the attribute keys of an element:
"Iterator<String> Element.getAttributeKeyIterator()"
Will help you do that. Now lets see some helper method that ease the use of attributes. Attributes are one of the easiest way to store elements in the graph so that algorithms operating on it can retrieve them in a simple way. Therefore an algorithm will often have to fetch attributes values and push new values.
To search for several attributes and take the first that exist in an element, use:
"Element.getFirstAttributeOf( String ... keys )"
This method takes as argument a variable list of strings. The method will iterate on these keys in order and return the first attribute that match one of the keys, ignoring non existing attribute keys. There exist a counterpart that also checks the attribute is of the correct type:
"Element.getFirstAttributeOf( Class clazz, String ... keys )"
It works the same as “Element.getAttribute( String key, Class clazz )”, and consider an attributes only if its value is an instance of the given class.
Very often, attributes values will be strings, numbers or arrays. There are specific methods to access such attributes more easily. The three methods:
"boolean Element.hasLabel( String key ) boolean Element.hasNumber( String key ) boolean Element.hasVector( String key )"
Allow to ensure an attribute of type or descendant of type “CharSequence”, “Number”, and “ArrayList<? extends Number>” respectively, exists in the element. They return false even if an attribute exists for the key, but has not the correct type. Similarly, the three methods:
"CharSequence Element.getLabel( String key ) double Element.getNumber( String key ) ArrayList<? extends Number> Element.getVector( String key )"
Allow to retrieve these kinds of attributes, or return null if not found or not the correct type.
The last method to deal with attributes is:
"Element.clearAttributes()"
That removes in one pass all the attributes and their values stored in the element.
Attributes are a key feature of the graph classes. They allow to push, inspect and remove arbitrary data in all graph elements: graphs, nodes and edges. However there are other methods to store user data in these elements: you can override them, creating your own set of node or edge classes for specific needs. This special use of the graph class is described later (Specifying the Node and Edge Classes).
This is one of the easiest part, simply use:
"Graph g = new Graph( "" ); g.addNode( "nodeIdentifier1" ); g.addNode( "nodeIdentifier2" );"
to add nodes. The argument gives to the node its unique identifier. Adding an edge is almost as simple:
"g.addEdge( "edgeIdentifier1", "nodeIdentifier1", "nodeIdentifier2" );"
This adds an edge between two nodes already created (if the nodes do not already exist, a “NotFoundException” maybe raised, it depends on the security settings of the graph. In strict mode, the graph throws an exception, in non strict mode, the graph creates the non-existing nodes for you if an edge references them. See under). The edge, as any element in the graph, must have a unique identifier (however, the node and edge name spaces are separated, and it is possible to have an edge with the same name as a node).
To remove a node or edge, simply use:
"g.removeEdge( "edgeIdentifier1" ); g.removeNode( "nodeIdentifier1" ); g.removeNode( "nodeIdentifier2" );"
Why do we remove the edge first ? Because the graph tries to preserve its coherence. If a node is removed, all its connected edges will be removed automatically. If we had used:
"g.removeNode( "nodeIdentifier1" ); // At this point the edge "edgeIdentifier1" does not exist any more. g.removeNode( "nodeIdentifier2" ); g.removeEdge( "edgeIdentifier1" );"
The last line would have caused an exception “org.miv.util.NotFoundException”. Indeed, by default, the graph strictly checks what you try to insert or remove. It throws you a (friendly) exception to warn you something is probably wrong:
You can disable these verifications (they are enabled by default) using the following method:
"g.setStrictChecking( false );"
This avoids the errors given above, and silently fails. Be careful, with such a behavior, methods that can return an node or an edge, now can return null.
But the graph can still be more fault-tolerant: it can automatically create nodes that do not exist. When you create an edge, and one or two of the node identifiers you give do not exist, the method can automatically insert the missing nodes for you. This feature is enabled using:
"g.setAutoCreate( true );"
With such a feature, it is possible to create a complete graph by specifying only the edges. For example:
"Graph g = new Graph( "" );
g.setStrictChecking( false ); g.setAutoCreate( true );
g.addEdge( "AB", "A", "B" ); g.addEdge( "BC", "B", "C" ); g.addEdge( "CA", "C", "A" );"
will create a triangle, without having to ever create the “A”, “B” or “C” nodes.
The graph can be directly created with the strict-checking and auto-create features:
"Graph g = new Graph( "graphId", false /* no strict-checking*/, true /* auto-create */ );"
Once the graph is built, or even during its evolution, one of the most common operation is to explore the graph. All algorithms working on the graph will have to traverse it in a way or another.
When you know the identifier of the element you want to retrieve, the most direct way is to use:
"Node n = g.getNode( "nodeIdentifier" );"
or
"Edge e = g.getEdge( "edgeIdentifier" );"
Once you have such an element, you can also use it to explore the graph from this point. But we will see this later. First let see ways to globally iterate on the graph:
"Iterator<? extends Node> nodes = g.getNodeIterator();
while( nodes.hasNext() )
{
Node node = nodes.next();
System.out.printf( "node %s%n", node.getId() );
}"
However, be careful, it is not possible to add elements during the iteration process. It will cause a ConcurrentModificationException.
It is also possible to iterate on edges:
"Iterator<? extends Edge> edges = g.getEdgeIterator();
while( edges.hasNext() )
{
Edge edge = edges.next();
System.out.printf( "edge %s%n", edge.getId() );
}"
The same recommendation holds for the insertion of elements during edge iteration, as well as for any iteration.
Note that you can obtain the number of edges of a node using:
"Node.getDegree()"
And that there is a special method allowing to iterate over edges as over an array:
"Node.getEdge( int i )"
But its use is discouraged in favor of the iterator.
These iterators allow to browse the whole set of nodes and edges in an arbitrary order. It is also possible to explore the graph in an ordered way using the breadth first iterator:
"Node n = g.getNode( "myFirstNode" ); BreadthFirstIterator i = new BreadthFirstIterator( n );
while( i.hasNext() )
{
Node m = i.next();
System.out.printf( "node %s%n", m.getId() );
}"
This iterator needs a starting node. From this node it will start an exploration of the graph in breath first order (as opposed to an in depth first exploration). Starting from a node, it is also possible to write:
"Node n = g.getNode( "myFirstNode" ); BreadthFirstIterator i = n.getBreadthFirstIterator(); // ... etc."
As you can see in this second example, the “Node” class proposes also some ways to explore a graph, starting from a given instance of node. For example, given the node “n”, you can explore its surroundings using:
"Iterator<? extends Node> neighbours = n.getNeighborNodeIterator(); // ... etc."
This is an easy way to know all the nodes connected to a given one. You can also explore the surroundings by the edges:
"Iterator<? extends Edge> connections = n.getEdgeIterator();"
This way, you can browse the graph going from node to node. Here is an example that uses a commodity method named “Edge.getOpposite(Node)”:
"public void recursiveExploration( Node start )
{
if( endCondition )
return;
Iterator<? extends Edge> edges = start.getEdgeIterator();
Edge edge = null;
while( edges.hasNext() )
{
Edge e = edges.next();
if( edgeHasThePropertyISearchFor( e ) )
{
edge = e;
}
}
if( edge != null )
{
Node opposite = edge.getOpposite( start );
recursiveExploration( opposite );
}
}"
TODO: Describe (and code) other iterators.
In the precedent section we have seen how to create undirected edges. An undirected edge “e” between nodes “A” and “B” allow to go from “A” to “B” and from “B” to “A”.
However, some graphs are directed (or some say oriented) and it may be possible to go from “A” to “B”, but not from “B” to “A”. Automata is a good example of such graphs.
The “Graph”, “Node” and “Edge” classes are able to handle such cases. The “Graph” class offers more than one method to create edges, for example:
"Graph.addEdge( String edgeId, String fromNodeId, String toNodeId, boolean directed )"
The last argument, if set to true, allows to specify that the newly added edge will be directed. The direction will be from the first given node id toward the second given node id. In other words if you create edges this way:
"Graph g = new Graph( false, true ); g.addEdge( "AB", "A", "B", true ); g.addEdge( "CB", "C", "B", true ); g.addEdge( "DB", "D", "B", true );"
The edge “AB” will go from “A” toward “B”, and the “B” node will have no edge going toward the other nodes “A”, “C” and “D”.
From now, this will not change anything in the way you can explore the graph as seen above. If you try to iterate on all the edges of “B” you will still obtain three edges:
"Iterator<? extends Edge> i = B.getEdgeIterator(); int i=0;
while( k.hasNext() )
{
k.next();
++i;
}
System.out.printf( "count %d%n", i );"
This code snippet will output “3”. Indeed, it can be useful to be able to iterate on all edges, bidirectional ones, leaving ones and even entering ones, and the “Node.getEdgeIterator()” method does not make any distinction between leaving and entering edges.
The “Node” class, however, offers several other methods that take edge direction into account. First, we can test if an edge is an entering edge and/or leaving edge:
"boolean Node.hasEdgeToward( String nodeId ) boolean Node.hasEdgeFrom( String nodeId )"
You can fetch only leaving edges:
"Node.getEdgeToward( String nodeId )"
or fetch only entering edges:
"Node.getEdgeFrom( String nodeId )"
You can obtain the number of leaving edges:
"Node.getOutDegree()"
or the number of entering edges:
"Node.getInDegree()"
Then, you can iterate only the leaving or entering edges of a node:
"Node.getLeavingEdgeIterator() Node.getEnteringEdgeIterator()"
This allows you to traverse the graph with respect to the edges direction.
You can also look at the edges. First you can check if the edge is directed using the method:
"Edge.isDirected()"
If the edge is directed, its direction goes from the its “Edge.getSourceNode()” node toward its “Edge.getTargetNode()” node. Indeed the edge gives you four methods to obtain the nodes it links:
"Edge.getSourceNode() Edge.getTargetNode() Edge.getNode0() Edge.getNode1()"
Four ? Yes, in fact methods “getNode0()” is totally equivalent to “getSourceNode()” and “getTargetNode()” is equivalent to “getNode1()”. The source/target methods are more readable when the graph you deals with is considered oriented, whereas the two other methods are more suited to undirected graphs.
You can also change your mind, once an edge is created, using:
"Edge.setDirected(boolean) Edge.switchDirection()"
The first method allows to transform a directed edge into a bidirectional one, and vice versa. The second method allows to change the direction of the edge, swapping its source node with the target node. Note however that the “switchDirection()” method does not make an edge directed if it was not.
TODO:
The principal feature of the GraphStream API is its ability to handle so called Dynamic graphs. This means that the graph will be changed continuously. Therefore it must be possible to capture the changes in this graph in a common way. This is made possible using graph instrumentation.
This process uses the concept of listeners similar to the one found in the AWT or Swing GUI toolkits. A graph listener looks like this:
"public interface GraphListener
{
public void beforeGraphClear( Graph graph );
public void afterNodeAdd( Graph graph, Node node );
public void beforeNodeRemove( Graph graph, Node node );
public void afterEdgeAdd( Graph graph, Edge edge );
public void beforeEdgeRemove( Graph graph, Edge edge );
public void attributeChanged( Element element, String attribute,
Object oldValue, Object newValue );
}"
It lists all the possible changes that can occur in a graph. The events are:
graph clear
This should barely happen, but if this is the case, instead of sending as many remove events as there are elements in the graph, this event is sent.
element add
This is sent each time a node or edge is added.
element remove
This is sent each time a node or edge is removed.
attribute change
This is sent each time an attribute is changed in an element (node, edge or the graph).
One can register a listener in a graph like this:
"Graph g = new Graph( "" ); g.addGraphListener( myListener );"
After this, the listener “myListener” will receive notifications of every change in the graph structure and attributes.
In the GraphStream API, all the UI and graph displaying (that lives in the “org.miv.graphstream.ui” package), uses this feature to keep in sync with the current state of the graph.
This indeed allows to separate the graph manipulation, and its various side-effects in process that depend on it. This way, other graph classes that can (will!) appear in the API will be able to use directly the UI features without changes.
This feature also allow one of the features of GraphStream that permit to build a distributed application, where a graph and the algorithms that modify/use it lie on one machine, whereas the display of this graph and various data collected on it runs on another machine.
The uses of such a feature are numerous.
TODO: explanation of the inner working of the graph class:
Input and output in GraphStream are simple (once again). To read a graph instantiate one and call the “read(String filename)” method. To write a graph call the “write(String filename)” method. That's it.
If you are in a hurry, you can stop reading here. The recipe given above just works. However the next sections give details for interested readers.
The whole I/O package (“org.miv.graphstream.io”) of GraphStream is made of readers and writers very similar to the one found in the Java Development Kit. Each reader and writer is specific to a graph file format.
The whole I/O package is made to be independent of the “graph” package. This means that you can use it without using the graph classes provided by GraphStream. It can also be useful for example to output a graph on disk without ever constructing a graph in memory, merely by generating events. More on this topic later.
As there can be a lot of readers, they can be more easily instantiated using a “GraphReaderFactory”. This factory is a class that has only one static method “readerFor(String fileName)”. This method takes the name of a file on the local file system and tries to guess the correct reader class for the format of the file. This method is smart (at least a little smart). It opens the file and tries to infer from what it reads at the beginning of it the type of file. Most of the time this works. If this fails, it looks at the file name extension. If this last try fails, you are so out of luck, or you should reconsider the way you manage your files (does your desktop is a mess?).
Here is an example of use:
"GraphReader reader = GraphReaderFactory.readerFor( fileName );"
| Tip | The thing to remember is that the “GraphFactory” will correctly infer the type of any graph written with graph writers of this library. |
Once you have a reader, two usage scenarii are possible:
Why the second solution ? As you must well know now, GraphStream has been written to handle constantly evolving graphs. Therefore begin able to read and write graph files in one unique operation is not completely satisfying. Indeed a graph file has to be able to store not only a picture of the graph at any time “t”, but it has to be able to store the evolution of the graph.
In order to handle this, a new graph format has been devised, it is called “DGS” (and a specification is given in the appendices (DGS)). But in addition to this format, it must also be possible to read continuously a graph while doing other things.
This said, we will first look at the first scenario. The reading of the graph is done by a reader, but this reader does not give you directly a graph. In fact, a reader is completely disconnected from the “Graph” class. A reader produces events that can then be used to build a graph (an utility class that capture this events and build a “Graph” is given though). This feature allows to use the “org.miv.graphstream.io” package to read and write graphs without in fact building a graph (after all there are many uses for graph data), or to build a graph with another class that the one proposed in the “graph” package.
Therefore, in order to read a graph, one has to instantiate a reader, and then to pass it a listener that will be called for any bit of graph read in the file. This listener is very similar to the one seen in the Graph Instrumentation section. Here is the “GraphReaderListener” interface:
"void graphChanged( Map<String,Object> attributes ) void nodeAdded( String id, Map<String,Object> attributes ) void nodeChanged( String id, Map<String,Object> attributes ) void nodeRemoved( String id ) void edgeAdded( String id, String from, String to, boolean directed, Map<String,Object> attributes ) void edgeChanged( String id, Map<String,Object> attributes ) void edgeRemoved( String id ) void stepBegins( double time ) void unknownEventDetected( String unknown )"
It has methods to handle the following events:
graph change
Any change in the attributes of the graph.
element change
Any change in the attributes of a node or edge.
element addition
Any addition of a node or edge.
element removal
Any deletion of a node or edge.
steps
Events can be grouped in steps, in order to handle time. If steps are used, any event between two steps can be considered as occurring at the same time. The DGS format has a “step” instruction.
unknown things
Some formats are able to pass more instructions that the events listed above. If so, these events are passed as unknown.
Therefore to read a graph, you have to implement this interface and, when you receive an event, modify your graph accordingly. Hopefully, has this is a fairly common task, this is already done for you. You can use the “DefaultGraphReaderListener” class. Under is a full example on how to read a graph file using the graph reader factory to detect the file type and instantiate the correct reader, then using a “DefaultGraphReaderListener” to build the graph following the events of the graph reader:
"Graph g = new Graph(); GraphReader r = GraphReaderFactory.readerFor( "mygraphfile.dgs" ); DefaultGraphReaderListener l = new DefaultGraphReaderListener( g ); r.addGraphReaderListener( l ); r.read( "mygraphfile.dgs" );"
The method “GraphReader.read(String filename)” slurps the whole graph in one big operation. If your graph is not too large and/or static, this is probably the better way to read it. With these five lines you move a graph from inert memory to live memory. This is exactly the method used by “Graph.read()”.
Now, your graph can be too large to merely load it in RAM, or you may want to load it step by step, because it evolves in time. This is the second scenario that was listed above.
To read the graph event by event, all you have to do is to replace the call to “GraphReader.read()” by a loop of this form:
"r.begin( "mygraphfile.dgs" );
while( r.nextEvents() )
{
// ...
}
r.end();"
The “begin()” method opens the file and makes the necessary initialisation. For some formats, it can already send some events. The “nextEvents()” method reads as few events as possible and returns “true” while it remains events to read, then it stops. This is why it must be called in a loop. The “end()” method makes the necessary cleaning and closes the file (so never forget it! but you are a programmer, you cannot bypass the psychological lock of writing “begin” without writing “end”).
The fact the “nextEvents()” method stops after having read as few events as possible, allows to interrupt the reading to do other things. If the graph evolution in temporised, you are for example able to merely insert a “sleep()” inside the loop:
"Graph g = new Graph(); GraphReader r = GraphReaderFactory.readerFor( "mygraphfile.dgs" ); DefaultGraphReaderListener l = new DefaultGraphReaderListener( g ); r.addGraphReaderListener( l ); g.display(); r.begin( "mygraphfile.dgs" );
while( r.nextEvents() )
{
try { Thread.sleep( 100 ); } catch( InterruptedException e ) {}
}
r.end();"
The code given above displays a graph (notice the “g.display()” added) and reads it, pausing “100” milliseconds between each event.
The method “nextEvents()” should probably be called “nextEvent()” since most of the time, it will read only one event, and it tries to read as few event as possible. But for some formats it is not possible to read only one event at a time, hence its name. For the DGS file format, it is ensured that each call to “nextEvents()” will only read one event at a time.
Now, if you handle time, and your DGS file is organised in steps, you prefer probably handle the graph step by step, instead of event by event. This can be easily done using the “GraphReader.nextStep()” method instead of the “GraphReader.nextEvents()” method. This is handy for DGS files, but be careful that for other graph file formats this method acts merely the same as the “GraphReader.nextEvents()” method, since they do not support the notion of steps.
TODO: there are probably more to say about graph reading, and the nextEvents() method.
Now that you know how to read, let's see how to write a graph. This follows the same paradigm: you write the graph event by event. As for readers, writers are completely independent of the graph API. This means that you can write on disk a graph without ever constructing it in the computer memory (without instantiating a “Graph” instance).
To write a graph you need a “GraphWriter”. The “GraphWriter” interface defines ways to output nodes, edges, and attributes. There are specialised graph writers for each kind of graph file format possible. For example, to output a DGS graph use the “GraphWriterDGS” to output a GML graph, use the “GraphWriterGML”.
As for readers, the graphs are not seen as a static entity, but as something that can evolve in time. The interface reflects this stream nature:
"begin(String filename, String graphName); begin(OutputStream stream, String graphName); end();
addNode(String id, Map<String,Object> attributes); changeNode(String id, Map<String,Object> attributes); delNode(String id)
addEdge(String id, String node0Id, String node1Id, boolean directed, Map<String,Object> attributes); chageEdge(String id, Map<String,Object> attributes); delEdge(String id);
step(int time);"
You start the graph output using the “begin()” method. This method takes as argument a file name or an output stream. Later, when graph output will end, you will have to call the corresponding “end()” method, to properly close the file and cleanly free things.
In between you can generate “graph events”. These events are similar to the ones found in the readers: add/change/delete nodes and edges plus the step event that allows to group events. These events allow to tell what happens along time to the graph structure, instead of merely describing the graph structure statically.
Here is an example of how to write a simple “triangle” (static) graph in DGS format:
"GraphWriter writer = new GraphWriterDGS();
writer.begin( "triangle.dgs", "Triangle" ); writer.addNode( "A", null ); writer.addNode( "B", null ); writer.addNode( "C", null ); writer.addEdge( "AB", "A", "B", false, null ); writer.addEdge( "BC", "B", "C", false, null ); writer.addEdge( "CA", "C", "A", false, null ); writer.end();"
Notice that we did not created an instance of “Graph”. As said above, the API is completely independent of the “org.miv.graphstream.graph” package. Naturally this could also be a drawback for people that use the “graph” package and we will see later that there are utilities to simplify the writing of “Graph” instances (the “GraphWriterHelper” class).
The output starts with a call to “begin()” and finishes with a call to “end()”. Nodes are created with the “addNode()” method and edges with “addEdge()”. The first one at least needs to know the node identifier. The second one needs at least to know the edge identifier as well as the identifiers of the source and destination nodes and if the edge is directed (the boolean argument, true meaning “directed”).
In the example above we did not passed attributes. It is however possible to define them, merely by passing a Map made of pairs ”(String,Object)” where the string gives the name of the attribute and the object is the value. When you have a “Graph” instance you can use the “Element.getAttributeMap()” method on the “Graph” as well as on “Node” and “Edge” instances (remember that “Graph”, “Node” and “Edge” inherit from “Element”).
The “GraphWriter” interface allows to output these attributes in addition to the graph structure and indeed, the fact that these attributes themselves can evolve in time are the reason why there are “changeNode()” and “changeEdge()” methods.
However not all graph formats allow to handle attributes, and when then do, they do not handle them the same. Therefore you cannot expect graph writers to handle magically all the things you stored in your graph. DGS for example handles well numbers, booleans, strings, and vectors (List) of numbers/booleans/strings.
Therefore, as sometimes you do not want to ouput all attributes, it is possible to filter them by their name. There are filters for nodes and edges (they are separated). The following methods allow to filter attributes:
"unfilterNodeAttribute( String name ); unfilterEdgeAttribute( String name ); unfilterAllNodeAttributes(); unfilterAllEdgeAttributes(); unfilterAllAttributes();
filterNodeAttribute( String name ); filterEdgeAttribute( String name );"
The “GraphWriter” interface may be heavy and unpractical to use. Furthermore, most of the users of GraphStream will use the “Graph” class, and will not necessarily be happy with the complete separation of the “io” package with the “graph” package.
Therefore a “GraphWriterHelper” class has been devised, that takes as argument a graph instance and write it using either a dynamically created writer or one already chosen by the user. By default, all you have to do is:
"GraphWriterHelper gwh = new GraphWriterHelper( graph ); gwh.write( "myGraphFile.dgs" );"
Simpler than what has been explained in the previous section ?
The helper is able to detect the graph format from the filename extension. If it does know the extension (but you care about your extensions? right?) or if there is no extension, it will choose the DGS format. This is the method used by “Graph.write()”.
You can disable any attribute output by using:
"GraphWriterHelper gwh = new GraphWriterHelper( graph, false );"
Indeed the “GraphWriterHelper(graph)” constructor is a shortcut to “GraphWriterHelper(graph,true)”.
As for any automatic process, it must be possible to prevent or override it. If you want to be able to define what attributes should not be output by yourself, you can use the constructor with “false” and instead of calling “gwh.write(“file”)” you can use:
"GraphWriter gw = new GraphWriterDGS(); GraphWriterHelper gwh = new GraphWriterHelper( graph ); gw.filterNodeAttribute( "myAttribute" ); gwh.write( "myGraphFile.dgs", gw );"
Indeed you can choose the graph output format and what attribute filters it use by merely giving the writer to the “GraphWriterHelper”.
TODO: describe (and implement) a graph listener that dynamically output the graph to a file.
TODO: quick!
At the most basic level, the display of a graph can be done using the “Graph.display()” method. The example under shows how to use this method:
"Graph graph = new Graph( "a graph", false, true );
graph.addEdge( "AB", "A", "B" ); graph.addEdge( "BC", "B", "C" ); graph.addEdge( "CA", "C", "A" );
graph.display();"
Notice that this method comes in two flavours: “Graph.display()” and “Graph.display(boolean)”. The first one is merely a shortcut for a call to “Graph.display(true)”. This boolean argument asks the displayer to both render the graph and launch a special thread that continuously computes the best graphical position of each node of the graph in 2D (and with some renderers in 3D) so that the graph is easier to read.
This special thread implements what we call a “layout algorithm”. The role of such an algorithm is to produce graphically pleasing graph renderings by choosing appropriately the positions of each node. Such layout often try to avoid edge crossing that create messy drawings, so that the user can easily know which node is connected to which other node.
Actually, GraphStream only contains one graph layout algorithm (the spring algorithm), but more may be implemented later.
If you display your graph with “Graph.display()”, you may (should) notice that you graph moves! Indeed, your are seeing the graph layout algorithm in action. As often such algorithms tend to be complex and require time to compute the best graph layout, the GraphStream implementation shows you the different steps used by the algorithm to achieve its graph layout solution, instead of waiting for the termination of this layout computation.
This allows to avoid waiting, but has another very important advantage: when your graph evolves continuously, the layout can handle it almost instantly. As one of the main features of GraphStream is its handling of dynamics in graphs, this property of the graph presentation API is almost a necessity. This ensures that even if the graph gets new nodes or some are removed, the graph layout will constantly be re-adjusted to be always readable.
However the layout algorithm consumes CPU (and GPU) cycles. By clicking with the middle button of your mouse somewhere on the graph viewer window, you open a settings window that let you pause and restart the graph layout algorithm.
Naturally, if you do not want to have this part of the presentation API, you merely call “graph.display(false)”. It is always possible to position the nodes in space by yourself as explained under.
When you call any flavour of “Graph.display()”, you access a default mechanism to display the graph, under the form of an instance of “org.miv.graphstream.ui.viewer.GraphViewer” or “org.miv.graphstream.ui.viewer.GraphPanel”.
All the classes in the “org.miv.graphstream.ui.viewer” package implement a very basic graph viewer that opens a window or panel to display the graph. This is clearly the highest level of use of the graph rendering API. This viewer is already completely implemented for your use. It handles:
The “GraphViewer” class creates a window and starts rendering the graph it is the class used by the “graph.display()” method. The “GraphPanel” class creates a “JPanel” and renders the graph in it. It is therefore easy with this class to insert a graph renderer inside your own applications.
It has a (somewhat crude) setting window that you can access by middle-clicking on the graph. This window allows you to setup the graph layout thread is one was requested, and to do screenshots of what the graph panel displays. The screenshot feature is able to save the display in BMP, JPG and PNG but also supports a SVG export. SVG is a vector format, not a bitmap format. It allows to convert the graph rendering into EPS, PDF or FIG formats for example with a very high quality.
If a layout thread was requested, the setting window allows to choose the quality of the rendering algorithm. As this algorithm works in background all the time this window allows:
It is possible to click on nodes of the “GraphPanel” or “GraphViewer” classes to drag them at another location.
There exist a (lot more) low-level API, that has been devised to allow a more fine grained handling of graph rendering. However in this section we will continue to browse the features of the hi-level API and we will delve into the low-level gory details in the next section.
You can control the way nodes and edges are rendered in this viewer using the node and edge attributes. For example to set the color of a node simply use:
"node.setAttribute( "color", Color.RED );"
this works the same for edges. The attribute name is “color” and the value must be an instance of the “java.awt.Color” class. It is possible to put the “nodeColor” or “edgeColor” attribute on the graph instead of individual nodes or edges to change the default color of all edges or nodes.
It is preferable to use directly a “java.awt.Color”, but you can also specify colors using strings. The renderers handle colors values specified as a string. The understood formats are:
To change the position of edges and nodes you can use the “x”, “y” and “z” attributes that accept any derivative of the “Number” interface as the value (“Double”, “Float” and “Integer”). This has influence only if there is NO graph layout thread active, that is, if you called “graph.display(false)” (and not “graph.display(true)” or merely “graph.display()”).
To change the width of an edge or node, use the attribute name “width” and a value that implements “Number” (“Double”, “Float”, “Integer”).
To render a text aside a node or edge, use the “label” attribute with a value that implements “CharSequence” (for example “String”!).
To render the node as a small image icon, use the “icon” attribute. Here the value must identify an image file. This file can be on the local disk (but must be in a directory on the class path) or can be in a jar file in the class path. The icon mechanism uses a cache. It is therefore possible to put the “icon” attribute on each node element without having performance problems. It is possible to put the “nodeIcon” attribute on the graph instead of putting the “icon” attribute on individual nodes to specify the default icon to use for all nodes.
To return to the default rendering, simply remove the attribute.
TODO: There is lots more to say:
DGS is a file format allowing to store graphs and dynamic graphs in a textual human readable way, yet with a small size allowing to store large graphs. Graph dynamics is defined using events like adding, deleting or changing a node or edge. With DGS, graphs will therefore be seen as stream of such events.
Files following the DGS format are textual files (ASCII, UTF-8, etc.) eventually compressed using gzip. Indeed it is often useful and advantageous to compress dynamic graph streams because of their large redundancy and often very large size. The gzip format has been chosen since it is easily streamable and easy to use in Java. For example to open a gzip-ed file in Java and read its contents as any other textual file, one can use the following code snippet:
"BubberedReader buffer = new BufferedReader(
new InputStreamReader(
new GZIPInputStream(
(InputStream)new FileInputStream("filename"))));"
DGS sees graphs as composed of nodes and edges. These elements can however be equipped with attributes. Attributes can be arbitrary numbers, vectors of numbers or strings, and there can be any number of attributes per node and edge. However, once declared in the header, this number is the same for each subsequent node and edge declaration.
The format is composed of a header and a body. The header contains two lines defining the format version and the graph name and optionnal lengths. The body contains the events descriptions that will make up the graph stream.
The body is made of a sequence of steps containing zero or more events. Steps allow to introduce a notion of time inside the graph stream, one tick of the clock will pass at each step, and all the events in one step can be considered occurring at the same time. It is however possible to omit step events or to add a step event between each other event, as needed.
Each event stands on one line, terminated by a line separator. Each field on each line of the header and body is separated by one or more spacing characters.
Comments are allowed everywhere in the file excepted in the header. The two first lines of the file must therefore be free of any comment.
The first line contains a magic cookie defining the file format. This line is invariant for each file in the DGS file format for a given version. It changes from version to version. Actually 003 is the lastest:
"DGS003"
The second line contains three fields, the graph name followed by the number of steps and hen the total number of events in the graph. Theses numbers are only indicative and may be both set to zero. However, if known, they can describe the stream duration in number of steps (clock ticks) and number of events. In the example under, the graph name is “myDynGraph”, the number of steps is 2000 and there are 100000 events total.
"myDynGraph 2000 100000"
Hereafter are listed the events one can encounter inside a graph stream. Some of these events can take parameters (also known as attributes). Parameters allows to define what values will be stored in a node or edge. A parameter is made of a name and a value. They are separated by a : (colon) or = (equal) sign. The accepted values are strings (any sequence of character enclosed by ” (double quote) characters), numbers, single words (like strings but without quotes since they do not contain spaces) and vectors. A vector is a sequence of strings, words or numbers separated by the , (comma) character. Vectors can contain heterogeneous elements (mix of strings, words and numbers).
Here is the list of possible events:
“st”
Allows to define a new step (clock tick). The number that follows allows to identify the step. For the first step for example:
"st 0"
“an”
Allows to add a node. The command is followed by the unique node identifier allowing to identify this node compared to others. This name can be a single word or a string delimited by the double quote character. Other fields allow to define parameters. The following example adds a node with identifier “n1 and values +x=3.14159265” and “y=1.61803399” as parameters:
"an n1 x=3.14159265 y=1.61803399"
“cn”
Allows to modify attributes values for a node. In this example we modify the “n1” node attributes (notice that we use ”:” as separater for parameters, both ”=” and ”:” are allowed):
"cn n1 x:3 y:1"
“dn”
Allows to delete a node. In the example we delete the “n1” node:
"dn n1"
ae
Allows to add an edge. This command must be followed by the unique identifier of the edge, and then the identifiers of two other nodes. As for nodes, you can specify a parameter list. It is possible to create directed edges by adding a ”>” (greater-than) or ”<” (smaller-than) character between the nodes identifiers. This indicates the direction of the edge. When no ”<” or ”>” is present, the edge is not directed. The following examples creates an edge with identifier “e1” between nodes “n0” and “n1” with a parameter “weight” and another edge “e2” between nodes “n1” and “n2” that is directed from “n1” to “n2”:
"ae e1 n0 n1 weight=23 ae e2 n1 > n2 weight:40"
“ce”
As for nodes, allows to modify the parameters of the edge. The following example change the “weight” parameter of the “e1” edge:
"ce e1 weight=10"
“de”
Allows to delete an edge:
"de e1"
The format accepts empty line, even if they contain spaces. It is possible to use the # character to introduce comments that will last until the end of the line where they appear. A line containing a single comment will be ignored, but it is possible to add comments at the end of a line.
This version of the DGS file format, 003, is not compatible with the first and second versions of the format. The GraphStream library proposes graph readers for the old formats as well as for the new.
One of the simplest examples is the graph that forms a triangle:
"DGS003 triangle 0 6 an A an B an C ae AB A B ae BC B C ae CA C A"
The same with directed edges:
"DGS003 triangled 0 6 an A an B an C ae AB A > B ae BC B < C ae CA C > A"
The same with position attributes:
"DGS003 triangledp 0 6
an A x:0 y:0 an B x:1 y=0 an C x=0.5 y=1
ae AB A > B ae BC B < C ae CA C > A"
The same with more attributes (examples of vector attributes):
"DGS003 triangledpm 0 6
an A x:0 y:0 an B x:1 y=0 an C x=0.5 y=1
ae AB A > B weight:1 values=1,3,5,none ae BC B < C weight:5 values=none,2,4,6 ae CA C > A weight:2 values=none,1 "
The GML format has been devised by Michael Homsolt of the Passau University GML format specification). The format read by the GML parser of GraphStream matches the one defined in GML and adds some specific features. It was the first format designed to talk about dynamic graphs before we felt that creating a dedicated format (DGS) was a necessity.
GML is a very simple hierarchical ASCII graph format. It is made to describe graphs but not their evolution. At its base it consists in three elements “graph”, “node” and “edge”. These elements nest and can contain other elements. The group delimiters are the square brackets.
Here is a simple example of a GML file:
"graph [
node [ id "A" ]
node [ id "B" ]
node [ id "C" ]
edge [ id "AB" source "A" target "B" ]
edge [ id "BC" source "B" target "C" ]
edge [ id "CA" source "C" target "A" ]
]"
TODO: document the “map” key that allows to map an unknown attribute to a class and therefore easily read classes. document the “external” key. document the “include” key. document the new “step” key. document the new “del” keys. document the new “chg” keys.
The GraphStream library comes in to flavours:
The second ones are dedicated to developers and courageous users and should probably not be used for every day use. The first one is dedicated to users, is considered stable (or at least the most stable we could achieve…).
In order to use a release in your own project, all you have to do is to ensure the “graphstream.jar” and its dependencies are in your classpath. Indeed, GraphStream has some dependencies located in several java archive that you can find in the “lib/” directory. This directory only contains the class files. The GraphStream jar contains both the sources and the classes.
The dependencies listed in the “lib/” directory are all made by us and are GP Led also. However you will maybe need another library that we cannot distribute with GraphStream: JOGL.
The JOGL library provides access to OpenGL to the JVM. In GraphStream it is used only by the “ui” package for the 3D graph renderers. If you do not use these renderers, you will never need JOGL unless you try to compile GraphStream yourself. Else you can find it at https://jogl.dev.java.net/. Please download and install a version superior to 1.0.0 (or one that is marked as following the JSR231). There is a fundamental change in the package names after this release, and old releases are not compatible with GraphStream.
The SVN sources are always up to date with the development, but may contain (more) bugs, be unstable, contains testing features, non-completely implemented things, etc. Adventurous user, you will have been warned.
In order to use the SVN sources, the requirements are the same: put all the dependencies into your classpath. This time, JOGL is mandatory, since GraphStream will not build without it.
If you are using eclipse, you're right…. oups, I mean, if you use eclipse, you should probably create a library for JOGL, as this one not only depends on jars but also on native libraries.
For more adventurous developers, there is a build script usable with any good bash shell or POSIX shell in the “src/” directory. The build script compile the whole package and generates a java archive.
GraphStream allows to read and write graphs in so-called “dot” files. The dot format was created for the GraphViz set of tools, a graph visualisation library developed by AT&T.
Actually the DOT graph reader has one limitation: it cannot read graph descriptions where subgraphs appear. Aside from this limitation, the complete DOT format is recognised.
Colors are understood and displayed. Widths are read and used for nodes and edges (the height attribute is ignored). All attributes specified in the dot file are passed and stored into the graph.
The dot format allows to create both directed and undirected graphs with a somewhat straightforward syntax. Here is an example:
"digraph MyGraph {
a -> b;
b -> c;
c -> a;
}"
This creates a simple directed graphs with three nodes, “a”, “b” and “c”. Here the node declaration is implicit. Directed edges are declared using an arrow ”→”. Each line is terminated by a semi-colon.
Here is the same example for a non directed graph:
"graph MyGraph {
a -- b;
b -- c;
c -- a;
}"
Here edges are specified with an horizontal bar “—” made of two dash.
Although the “graph” and “digraph” specifiers are normally used to introduce non-directed and directed graph respectively, a directed graph can contain non directed edges and a non-directed graph can contain directed edges.
It is possible to add C and C++ style comments:
"/* a simple
* comment.
*/
graph MyGraph {
// A C++ comment, on one line only.
a -> b;
b -> c;
c -- d;
d -- a;
}"
Although it is possible to implicitly declare nodes as seen above, it is also possible to specify them directly.
"graph MyGraph {
a; // a node declaration is a simple node name.
b;
c;
a -- b;
b -- c;
c -- a;
}"
But this is often used to specify attributes for nodes. Attributes are given between square brackets. It is a list of name/value pairs where the attribute name and the value are separated by an equal sign. Each name/value pair is separated by a comma. For example:
"digraph MyGraph {
a [label="A",color="red",width="10"];
b [label = "B", color = "#00FF00", width = 5];
c [label=C, color="rgb(0,0,255)", width = 8];
a -> b;
b -> c;
c -- a;
}"
Note that when the attribute value is made of an unique word, the quote marks are not a necessity.
When an attribute should be specified for each node or each edge, once can also write:
"graph MyGraph {
// Specify these attributes for each node:
node [color="red"];
// Specify these attributes for each edge:
edge [color="blue"];
a -- b;
b -- c;
c -- a;
}"
Although the dot format can specify an incredible amount of attributes that affect rendering, the purpose of GraphStream is not to produce such outputs. Therefore the GraphStream renderer does not take all attributes into account.
You can use numbers for node names:
"graph MyGraph {
1 -- 2;
2 -- 3;
3 -- 1;
}"
The “GraphPanel” and “GraphViewer” classes allow to output the computed position of each node displayed in a file. Middle-click on the graph display to let appear a settings window that will provide a button and a text field allowing to save the node coordinates computed by the graph layout process.
This file will contain the coordinates of each node of the graph along with the node identifier. The format is simple. Each line concerns an unique node. The line starts with the node identifiers, followed by a colon. Then three numbers are given, one for the X coordinate, one for the Y coordinate and one for the Z coordinate.
Example:
"node1: 1 0 0 node2: 0 1 0 node3: 0 0.5 0"
This is one of the simplest and compact graph file format. Each line contains two or more node names. The node declaration is implicit. Each time a new node is encountered on a line it is created. The first node name of the line is then linked to all other node name on the line.
Here is an example:
"A B B C C A"
This will produce a triangle. But you can also write:
"A B C B C"
That will produce the same graph since edges are not oriented. The “edge” reader of GraphStream can optionnaly orient the edges.