Package lu.cs.co.graph

Provides classes and interfaces for graphs, subgraphs, vertices, edges, paths, forests, etc.

See:
Description

Interface Summary

Embedding	Specifies an embedded graph (a graph whose vertices have fixed plane coordinates).
Subgraph	Specifies common methods for subgraphs of a graph.

Class Summary

Book	Constructors for undirected graphs based on a work of literature.
DirectedEdge	A directed edge.
Edge	This abstract class defines and provides fields and methods for an edge in a graph.
Edges	An iterator over a set of edges.
Embedding.Point
Forest	A class for (undirected) forests whose vertex set coincides with the underlying graph.
Graph	A class for combinatorial graphs.
Marks	A class for marking vertices, which can be viewed as a class for subsets of the vertices of a graph.
Miles	Constructor for undirected graphs based on US mileage data.
Path	A class for simple paths in a graph.
RandomGraph	Constructors for random graphs.
Roget	Constructors for graphs based on Roget's Thesaurus.
UndirectedEdge	An undirected edge.
Vertex	A vertex.
Vertices	An iterator over a set of vertices.
Viewer
Words	Constructors for undirected graphs whose vertices are five-letter words.

Exception Summary

NoSuchElementException
StructureViolationException

Package lu.cs.co.graph Description

Provides classes and interfaces for graphs, subgraphs, vertices, edges, paths, forests, etc.

Graphs

The Graph class represents combinatorial graphs. Methods vertices() and edges() access the graphs vertices and edges, respectively, which are returned as an iterator over these sets (see below).

The Graph class models both directed and undirected graphs, the method isDirected() distinguishes the two.

Constructing graphs

Constructors are provided for basic graphs:

Class of graph	Constructor
Empty n-graph	Graph(n,false)
Complete n-graph	Graph(n,true)
Complement of G	Graph(G,true)
Subgraph induced by U	Graph(U)

Random graphs of all sizes and flavours are easily constructed. Each constructor takes a seed parameter defining all the random choices, such that random graphs are reproducible.

Random graph	Constructor
With n vertices and medges	RandomGraph(n,m,seed)
With n vertices and edge probability p	RandomGraph(n,p,seed)
Given G with random edge lengths	RandomGraph(G,min,max,seed)

Finally, many constructors exist for several non-random graphs with interesting structure. These are based on [1].

Description	Graph class
Intercity distances	Miles
Encounters in books	Book
Associations in a thesaurus	Roget
Five-letter words	Words

Subgraphs

The Subgraph interface provides common methods for subgraphs, which are implemented by the classes Forest, Path, and Marks.

Forests

The Forest class models cycle-free edge subsets in undirected graphs.

Paths

The Path class models simple paths (sequences of connected vertices) and cycles. Methods are provided for traversing and modifying the path, and checking for Hamiltonicity.

Marked vertices

The Marks class is an all-purpose class to model a subset of (`marked') vertices, useful for a number of basic graph algorithms like connectivity.

For example, the Marks class provides the static method Marks.reach that returns a marking of the vertices reachable from a given vertex. After performing

M=Marks.reach(G,v)

M will contain the vertices reachable from v. Especially we have M.contains(u) if and only if u is reachable from v.

This can be used with the Graph(Subgraph) constructor to produce a connected component in an undirected graph G with vertex v:

Marks M= Marks.reach(G,v);
Graph CC= new Graph(M);

Graph Input and Output

The Graph class provides a static method parseGraph() that is convenient for constructing graphs from the command line. For example,

	java lu.cs.co.graph.Graph 23 41
	java lu.cs.co.graph.Graph miles 35
	

constructs a random graph with 23 vertices on 41 edges, and on the graph representing intercity mileage between 35 US cities, respectively.

Here is an example of using the parseGraph() method:

class MyProgram
  {
  public static void main(String[] args)
      { Graph G= Graph.parseGraph(args);
        System.out.println(G);
      }
  }

The example also shows that the Graph class implements toString() in some sensible way, returning a textual representation of the graph in a human-readable fashion. The syntax can also be read by graph drawing programs. This representation is complemented by the the Viewer class which draws a pictorial representation of the graph in a window.

Both the Graph and Viewer classes are executable and construct a graph from the command line (parseable by parseGraph()), which is then output to standard output or drawn on-screen, respectively. See Graph.main() and Viewer.main().

Vertices

The graph's vertices are given by an iteratorclass Vertices. Here is an example:

for (Vertices V= G.vertices(); V.hasNext();)
  { Vertex v= V.next();
    handle(v);
  } 

However, every graph also comes equipped with an ordering of its vertices in the range 0..G.n, which is available through the graph's getVertex(int) and getIndex(Vertex) methods. Thus, the vertices can be enumerated in a different fashion:

for (int i= 0; i < G.n; ++i)
  { Vertex v= G.getVertex(i);
    handle(v);
  } 

Of the two methods, the first is preferred, since it does not use the (somewhat arbitrary) ordering of the vertices. However, the ordering of the vertices is (i) convenient when random access is required for performance reasons (ii) consistent with the ordering of the vertices assumed in the getAdjecencyMatrix() and getDistanceMatrix() methods.

Note also that a vertex does not know its own index: there is no Vertex.getIndex() method. This is because (in principle) two graphs may share a vertex, which then might have different indices in each graph.

Edges

The method G.edges() returns an instance of the iterator class Edges containing G's edges. Thus, the canonical way to process the edges of graph G is as follows:

  for (Edges E= G.edges(); E.hasNext(); )
	     { Edge e= E.next();
	       handle(e);
	     }
	     

This processes all of E in no particular order.

The same mechanism applies to the edges incident to a particular vertex. To this end the incoming and outgoing methods return iterators of the edges around a vertex. For example, if v is a vertex, we process its outgoing edges as follows

  for (Edges E= G.outgoing(v); E.hasNext(); )
   { Edge e= E.next();
     handle(e);
   }
  

The vertex incident to another vertex on an edge is accessed using the edge's neighbour method. If e={u,v} then u=e.neighbour(v). We can extend the above piece of code to iterate over all of u's neighbours:

  for (Edges E= G.outgoing(v); E.hasNext(); )
   { Edge e= E.next();
     Vertex u= e.neighbour(v);	
     handle(u);
   }
  

Obviously, we could write the inner block as handle(E.next().neighbour(v));

Directed and undirected edges

An edge class is either directed or undirected. The undirected edge {u,v} is outgoing from both u and v. It is also incoming to both u and v. In contrast, the directed edge (u,v) is outgoing from u and incoming to v but not vice versa.

The insert method makes sure that when an edge is inserted into the graph, it will be handled according to these conventions depending on whether it is an instance of DirectedEdge or UndirectedEdge.

As a final illustration, the following code also runs through all of G's edges:

  for (Vertices V=G.vertices(); V.hasNext(); ) 
    for (Edges E= G.outgoing(V.next()); E.hasNext(); )
       handle(E.next());

   

Exercise

How often is each of G's edges handled by the above code?

Coding conventions

Iterators

It is worth noting that there is no random access to the edges: no methods are provided for accessing (say) the 7th edge, nor is it possible to access the `index' of a specific edge. Programmers can of course use an array to create such a data structure:

Edge[] EE= new Edge[G.m];
int i= 0;
for (Edges E= G.edges(); E.hasNext();)  EE[i++]= E.next();

Now, G's edges are in EE[0],...,EE[G.m-1]. However, this way of forcing an ordering on the edges is discouraged and should not be used except when random access is required for performance reasons. Failure to follow this coding convention is considered an error.

To some extend the same rule applies to vertices. The random access methods Graph.getIndex(Vertex) and Graph.getVertex(int) exist only to ease coding and increase efficiency in a number of special cases. In all other cases, the iteration provided by Graph.vertices() is preferred.

Variable names

The use of variable names to mimick standard mathematical notation is encouraged. Whenever possible, use the following names:

• use upper case roman letters to denote a collection of elements (for example, a graph, path)
• use lower case roman for letters to denote an single element (a vertex or an edge).
• use G, H for a graph
• use U, V, W for a collection of vertices
• use E for a collection of edges
• use F for a forest
• use P, Q, R for a path
• use M for a marking
• use u,v,w for a vertex
• use e, f for an edge
• avoid using n and m for other values than the number of vertices and edges in a graph

Most of the time, not all of conventions cannot be followed and programmers have to use their good judgement to adhere to the naming policy.

Failure to follow these coding conventions is considered an error.

References

[1] Donald E. Knuth, The Stanford Graphbase: a platform for combinatorial computing, Addison-Wesley 1993.