Tutorial - Graph

A graph is composed of Vertices and Edges where each edge joins two vertices i.e. has as an origin and a destination. If the edge is undirected, then the two vertices play exactly the same role. If the edge is directed, we say that it goes from its origin to its desination. Each Vertex and Edge can contain an element, hence it is a Position. In order to manipulate the graph (or any of its edges and vertices), we have to call methods of the graph.

Create a graph

In the following example, we present the creation of an undirected graph:

boolean directed=false;
Graph g = new DefaultGraph(directed);
Position vertA = g.insertVertex("A");
Position vertB = g.insertVertex("B");
Position vertC = g.insertVertex("C");
Position vertD = g.insertVertex("D");
Position vertE = g.insertVertex("E");
Position vertF = g.insertVertex("F");
g.insertEdge(0,vertA,vertE);
g.insertEdge(0,vertE,vertD);
g.insertEdge(0,vertC,vertE);
g.insertEdge(0,vertC,vertD);
g.insertEdge(0,vertB,vertC);
g.insertEdge(0,vertA,vertB);
g.insertEdge(0,vertA,vertF);
g.insertEdge(0,vertA,vertF);

If one wants to creat a directed graph, only the boolean value directed has to be changes. It is also possible to change a directed edge into an undirected one or vice-versa using the two methods: graph.setDirected(edge) and graph.setUndirected(edge).

Visit a graph

The method g.vertices() can be used to visit all of the vertices of a graph or g.edges() for all of its edges.
So a loop over all the vertices of a graph would look like:

List> vertices = g.vertices();
for(Position v : vertices){
    // Do something with v
}

The following program presents an implementation of the breadth first search algorithm. In this version, we use a buffer (which is a sequence) to store vertices. We also have a sequence result that stores the returned value. We need in that version a hash table for "marking" the visited vertices, we use a java.util.HashSet to do this.
We use the following loop to visit all the adjacent vertices of w.

for(Position v2 : g.adjacentVertices(v,Direction.ALL)){
    // Work using v2 
}

Graph g = ...;
Sequence> buffer = new LinkedSequence>();
Sequence> result = new LinkedSequence>();
Set> bufferedVertices = new HashSet>();

List> vertices = g.vertices();
for(Position v : vertices){
    if(! bufferedVertices.contains(v)){
	buffer.add(v);
	bufferedVertices.add(v);
	while(! buffer.isEmpty()){
	    Position> pFirst= buffer.first();
	    v = (Position)buffer.element(pFirst);
	    buffer.delete(pFirst);
	    result.add(v);
	    
	    for(Position v2 : g.adjacentVertices(v,Direction.ALL)){
		if(!bufferedVertices.contains(v2) && v2 !=null){
		    bufferedVertices.add(v2);
		    buffer.add(v2);
		}
	    }
	}
    }

Using a hash table to mark the vertices of a graph is not object oriented, even if it works and is quite efficient. We suggest never to use such a system, but instead to use the decorator pattern as it is presented in the chapter Add properties to the Edges or the Vertices

Examples:

GraphExample1.java: Very simple program, creating a small graph and visiting it using a Depth First Search. Marking of the visited vertices is done using a HashMap. (java source file)
GraphExample2.java In this example, we use new verices having more properties. Therefor we use the factory pattern. (the graph is undirected). (java source file)
GraphExample3.java: This example uses also the factory pattern, but uses a directed graph. (java source file)
GraphExampleNonGenerics.java: This example has been written using old fashion Java including no generics but using casting instead.(java source file)

Previous Tutorial Next