In this tutorial we will learn how to explore a graph and its associated data by various means. In this tutorial we will work with a simple graph constructed from the following code :
import org.miv.graphstream.graph.*;
import org.miv.graphstream.graph.implementations.*;
public class Tutorial003 {
public static void main( String args[] ) {
new Tutorial003();
}
public Tutorial003() {
Graph graph = new DefaultGraph();
Node A = graph.addNode( "A" );
Node B = graph.addNode( "B" );
Node C = graph.addNode( "C" );
Node X = graph.addNode( "X" );
Node Y = graph.addNode( "Y" );
Node Z = graph.addNode( "Z" );
graph.addEdge( "AB", "A", "B" );
graph.addEdge( "BC", "B", "C" );
graph.addEdge( "CA", "C", "A" );
graph.addEdge( "XY", "X", "Y" );
graph.addEdge( "YZ", "Y", "Z" );
graph.addEdge( "ZX", "Z", "X" );
graph.addEdge( "AX", "A", "X" );
A.addAttribute( "label", "A" );
B.addAttribute( "label", "B" );
C.addAttribute( "label", "C" );
X.addAttribute( "label", "X" );
Y.addAttribute( "label", "Y" );
Z.addAttribute( "label", "Z" );
graph.display();
}
}
This graph looks like this :
Listing all nodes and edges
You already know one of the fastest ways to access elements in a graph : retrieving them by their name. Indeed, as we have seen each element possesses an identifier that uniquely identifies it. Therefore, to fetch a node by its name, you write :
Node aNode = graph.getNode( "aNode" );
If the node exists, a reference to the element that represents it is returned, else you receive null. You should probably test the result since there are no exception thrown for non existing nodes.
You proceed exactly the same way for edges.
However, you do not always know the identifiers of all the nodes or edges in your graph, for example because you read it from a file. Furthermore, some graph readers may generate the identifiers if they do not exist. Therefore, you can browse every node or edge using iterators :
Iterator<? extends Node> nodes = graph.getNodeIterator();
while( nodes.hasNext() ) {
System.out.printf( "%s%n", nodes.next().getId() );
}
Iterator<? extends Edge> edges = graph.getEdgeIterator();
while( edges.hasNext() ) {
System.out.printf( "%s%n", edges.next().getId() );
}
Let's try this. We will use these iterators to enumerate all nodes and give then change their label to a number. Add this code to the example given at start (you will have to import java.awt.Color and java.util.Iterator) :
int number = 0;
Iterator<? extends Node> nodes = graph.getNodeIterator();
while( nodes.hasNext() ) {
Node node = nodes.next();
node.addAttribute( "ui.color", Color.RED );
node.addAttribute( "label", number++ );
try { Thread.sleep( 1000 ); } catch( InterruptedException e ) {}
}
This code will process one node at a time every second. This small pause will help you visualise what's happening on the graph viewer : the nodes get coloured and numbered in a completely random order. Indeed there is no fixed order for node and edge iteration. Furthermore, this order may change at any time.
Iterating from node to node
Being able to iterate over the whole graph is a necessity, but one often needs to explore the graph starting from a given node, in a given order, following an algorithm.
For this, you either know the starting node or want a node taken randomly. We already have seen how to extract a given node. To choose one node randomly you can use a facility built in each graph implementation :
Node startNode = graph.algorithm().getRandomNode();
The algorithm() method yields an instance of the Algorithms class. Although most graph algorithms are implemented in a dedicated class, some very often used procedures are implemented in an Algorithms class. As each graph underlying implementation is specific, the corresponding Algorithms implementation tries to provides the fastest way to process this graph, knowing its implementation. it would pollute the Graph interface to define this growing set of algorithms as methods in the graph, therefore they are a dedicated class.
In our example, some graphs implementations require to iterate over the graph to find a random node, whereas others can give you a random node in constant time.
Once you have a starting node, you can start to explore the graph by this node. First you can iterate over the edges connected to this node :
Iterator<Edge> edges = startNode.getEdgeIterator();
When you declared directed edges, it is possible to iterate only over the set of edges that enter or leave a node :
Iterator<Edge> leavingEdges = startNode.getLeavingEdgeIterator(); Iterator<Edge> enteringEdges = startNode.getEnteringEdgeIterator();
However, remember that GraphStream supports mixed graphs where directed an undirected edges can coexist. Therefore undirected edges are counted as bidirectional edges. They both enter and leave the node (they can be counted twice if you use only the leaving and entering versions of the iterators).
When you iterate on the edge set of a given start node, you may have to check the nodes connected at the other end of the edge. This is not made easy since you have to check the two nodes of the edge using the Edge.getNode0() and Edge.getNode1() methods. If the edge is directed, there is no problem since the node 0 is the source node and the node 1 is the target node.
If the edge is not directed you have to compare the node 0 and 1 to the start node to know which one is the other node. To help this, you can use Edge.getOpposite(A) to automatically obtain the other node.
However, if you are interested only in the neighbour nodes and not the edges there is a better way :
Iterator<Node> neighbours = startNode.getNeighborNodeIterator();
Let's try these new ways to iterate over the graph. Add the code given under to your program :
Node startNode = graph.algorithm().getRandomNode();
Iterator<? extends Edge> edges = startNode.getEdgeIterator();
startNode.addAttribute( "color", Color.BLUE );
while( edges.hasNext() )
{
Edge edge = edges.next();
edge.addAttribute( "ui.color", Color.BLUE );
edge.getOpposite( startNode ).addAttribute( "ui.color", Color.BLUE );
try { Thread.sleep( 1000 ); } catch( InterruptedException e ) {}
}
This code will pick up a node at random in the graph, colour it in blue, and then iterate over each of its edges second after second, coloring them in blue as well as the other nodes they connect.
In the picture above, the node labelled "4" was chosen randomly.
Iterating the graph depth or breadth first
An often needed task is to browse the graph (or a connected component) in breadth-first or depth-first order. GraphStream provides two specific utility iterators accessible from a given node to do this.
Let's try this, add this code to your program :
number = 0;
startNode = graph.algorithm().getRandomNode();
Iterator<? extends Node> breadthFirst = startNode.getBreadthFirstIterator();
startNode.addAttribute( "ui.color", Color.GREEN );
startNode.addAttribute( "label", number++ );
while( breadthFirst.hasNext() ) {
Node currentNode = breadthFirst.next();
currentNode.addAttribute( "ui.color", Color.GREEN );
currentNode.addAttribute( "label", number++ );
try { Thread.sleep( 1000 ); } catch( InterruptedException e ) {}
}
try { Thread.sleep( 5000 ); } catch( InterruptedException e ) {}
number = 0;
Iterator<? extends Node> depthFirst = startNode.getDepthFirstIterator();
startNode.addAttribute( "ui.color", Color.MAGENTA );
startNode.addAttribute( "label", number++ );
while( depthFirst.hasNext() ) {
Node currentNode = depthFirst.next();
currentNode.addAttribute( "ui.color", Color.MAGENTA );
currentNode.addAttribute( "label", number++ );
try { Thread.sleep( 1000 ); } catch( InterruptedException e ) {}
}
This code will traverse the whole graph in breadth first order, starting from a random node, colour each node in green as soon as visited, and number it in the visit order. It waits five seconds and do the same in depth first order using the magenta colour.