We develop our graph-processing algorithms using an ADT that defines the fundamental tasks, using the standard mechanisms introduced in Chapter 4. is the ADT interface that we use for this purpose. Basic graph representations and implementations for this ADT are the topics of through . Later in the tutorial, whenever we consider a new graph-processing problem, we consider the algorithms that solve it and their implementations in the context of client programs and ADTs that access graphs through this interface. This scheme allows us to address graph-processing tasks ranging from elementary maintenance operations to sophisticated solutions of difficult problems.

Graph ADT interface

This interface is a starting point for implementing and testing graph algorithms. It defines a Graph data type with the standard representation-independent ADT interface methodology from Chapter 4 and uses a trivial Edge data type to encasulate pairs of vertices as edges (see text). The Graph constructor takes two parameters: an integer giving the number of vertices and a Boolean that tells whether the graph is undirected or directed (a digraph). The basic operations that we use to process graphs and digraphs are ADT operations to create and destroy them, to report the number of vertices and edges, and to add and delete edges. The method getAdjList provides an AdjList iterator so that clients can process each of the vertices adjacent to any given vertex. and illustrate the use of this mechanism. 

class Graph // ADT interface
 { // implementations and private members hidden
 Graph(int, boolean)
 int V()
 int E()
 boolean directed()
 int insert(Edge)
 void remove(Edge)
 boolean edge(int, int)
 AdjList getAdjList(int)
 }

The interface is based on our standard mechanism that hides representations and implementations from client programs (see Section 4.9). It provides the basic mechanisms that allow clients to build graphs (by constructing the graph and then adding the edges), to maintain the graphs (by removing some edges and adding others), and to test whether an edge exists. The contructor's second argument is a flag indicating whether the graph is directed; the interface also includes a method that allows clients to test this condition. Beyond these basic operations, the Graph interface of also specifies the basic mechanism that we use to examine graphs: an iterator AdjList for processing the vertices adjacent to any given vertex. Our approach is to require that any such iterator must implement a Java interface that we use only for the purpose of processing the vertices adjacent to a given vertex, in a manner that will become plain when we consider clients and implementations. This interface is defined as follows: 

interface AdjList
 {
 int beg()
 int nxt()
 boolean end()
 }

The first two of these methods are to return a vertex name (the first and the next, respectively, in a sequence of vertices); the third method is for testing whether there are more vertices to process. The Graph interface of refers to a simple class that allows our programs to manipulate edges in a uniform way, which may be implemented as follows: 

class Edge
 { int v, w;
 Edge(int v, int w)
 { this.v = v; this.w = w; }
 }

This implementation suffices for basic graph-processing algorithms; we consider a more sophisticated one in . The ADT in is primarily a vehicle to allow us to develop and test algorithms; it is not a general-purpose interface. As usual, we work with the simplest interface that supports the basic graph-processing operations that we wish to consider. Defining such an interface for use in practical apps involves making numerous tradeoffs among simplicity, efficiency, and generality. We consider a few of these tradeoffs next; we address many others in the context of implementations and apps throughout this tutorial. The graph constructor takes the maximum possible number of vertices in the graph as an argument so that implementations can allocate memory accordingly. We adopt this convention solely to make the code compact and readable. A more general graph ADT might include in its interface the capability to add and remove vertices as well as edges; this would impose more demanding requirements on the data structures used to implement the ADT. We might also choose to work at an intermediate level of abstraction and consider the design of interfaces that support higher-level abstract operations on graphs that we can use in implementations. We revisit this idea briefly in , after we consider several concrete representations and implementations.

Example of a graph-processing method

This method is a graph ADT client that implements a basic graph-processing operation in a manner independent of the representation. It returns an array having all the graph's edges. This implementation illustrates the basis for most of the programs that we consider: we process each edge in the graph by checking all the vertices adjacent to each vertex. We generally do not invoke beg, end, and nxt except as illustrated here, so that we can better understand the performance characteristics of our implementations (see ). 

static Edge[] edges(Graph G)
 { int E = 0;
 Edge[] a = new Edge[G.E()];
 for (int v = 0; v < G.V(); v++)
 {
 AdjList A = G.getAdjList(v);
 for (int w = A.beg(); !A.end(); w = A.nxt())
 if (G.directed() || v < w)
 a[E++] = new Edge(v, w);
 }
 return a;
 }

A general graph ADT needs to take into account parallel edges and self-loops, because nothing prevents a client program from invoking insert with an edge that is already present in the graph (parallel edge) or with an edge whose two vertex indices are the same (self-loop). It might be necessary to disallow such edges in some apps, desirable to include them in other apps, and possible to ignore them in still other apps. Self-loops are trivial to handle, but parallel edges can be costly to handle, depending on the graph representation. In certain situations, including a remove parallel edges ADT operation might be appropriate; then, implementations can let parallel edges collect, and clients can remove or otherwise process parallel edges when warranted. We will revisit these issues when we examine graph representations in and .

A client method that prints a graph

This implementation of the show method from the GraphIO package of uses the graph ADT to print a table of the vertices adjacent to each graph vertex. The order in which the vertices appear depends upon the graph representation and the ADT implementation (see ).

Screenshot Adjacency lists format

This table illustrates yet another way to represent the graph in : We associate each vertex with its set of adjacent vertices (those connected to it by a single edge). Each edge affects two sets: For every edge u-v in the graph, u appears in v's set and v appears in u's set.

Java graphics 17fig07 

static void show(Graph G)
 {
 for (int s = 0; s < G.V(); s++)
 {
 Out.print(s + ": ");
 AdjList A = G.getAdjList(s);
 for (int t = A.beg(); !A.end(); t = A.nxt())
 { Out.print(t + " "); }
 Out.println("");
 }
 }

is a method that illustrates the use of the iterator class in the graph ADT. This method extracts a graph's set of edges and returns it in a client-supplied array. A graph is nothing more nor less than its set of edges, and we often need a way to retrieve a graph in this form, regardless of its internal representation. The order in which the edges appear in the array is immaterial and will differ from implementation to implementation. is another example of the use of the iterator class in the graph ADT, to print out a table of the vertices adjacent to each vertex, as shown in . The code in these two examples is quite similar and is similar to the code in numerous graph-processing algorithms. Remarkably, we can build all of the algorithms that we consider in this tutorial on this basic abstraction of processing all the vertices adjacent to each vertex (which is equivalent to processing all the edges in the graph), as in these methods. As discussed in , it is convenient to package related graph-processing methods into a single class. is an ADT interface for such a class, which is named GraphIO. It defines the show method of and two methods for inserting into a graph edges taken from standard input (see and for implementations of these methods). We use GraphIO throughout the tutorial for input/output and a similar class named GraphUtilities for utility methods such as the extract-edges method of .

Graph-processing input/output interface

This ADT interface illustrates how we might package related graph-processing methods together in a single class. It defines methods for inserting edges defined by pairs of integers on standard input (see ), inserting edges defined by pairs of symbols on standard input (see ), and printing a graph (see ). We will use these methods throughout the tutorial. We also reserve a similar class name GraphUtilities to package various other graph-processing methods needed by several of our algorithms, such as . 

class GraphIO
 {
 static void scanEZ(Graph)
 static void scan(Graph)
 static void show(Graph)
 }

Generally, the graph-processing tasks that we consider in this tutorial fall into one of three broad categories:

Examples of the first are the number of connected components and the length of the shortest path between two given vertices in the graph; examples of the second are a spanning tree and the longest cycle containing a given vertex; examples of the third are whether two given vertices are in the same connected component. Indeed, the terms that we defined in immediately bring to mind a host of computational problems. Our convention for addressing such tasks will be to build ADTs that are clients of the basic ADT in but that, in turn, allow us to separate client programs that need to solve a problem at hand from implementations of graph-processing algorithms. For example, is an interface for a graph-connectivity ADT. We can write client programs that use this ADT to create objects that can provide the number of connected components in the graph and that can test whether or not any two vertices are in the same connected component. We describe implementations of this ADT and their performance characteristics in , and we develop similar ADTs throughout the tutorial. Typically, such ADTs include a preprocessing method (the constructor), private data fields that keep information learned during the preprocessing, and query methods that use this information to provide clients with information about the graph.

Connectivity interface

This ADT interface illustrates a typical paradigm that we use for implementing graph-processing algorithms. It allows a client to construct an object that processes a graph so that it can answer queries about the graph's connectivity. The count method returns the number of connected components, and the connect method tests whether two given vertices are connected. is an implementation of this interface. 

class GraphCC
 {
 GraphCC(Graph G)
 int count()
 boolean connect(int, int)
 }

In this tutorial, we generally work with static graphs, which have a fixed number of vertices V and edges E. Generally, we build the graphs by executing E invocations of insert, then process them either by using some ADT operation that takes a graph as argument and returns some information about that graph or by using objects of the kind just described to preprocess the graph so as to be able to efficiently answer queries about it. In either case, changing the graph by invoking insert or remove necessitates reprocessing the graph. Dynamic problems, where we want to intermix graph processing with edge and vertex insertion and removal, take us into the realm of online algorithms (also known as dynamic algorithms), which present a different set of challenges. For example, the connectivity problem that we solved with union-find algorithms in Chapter 1 is an example of an online algorithm, because we can get information about the connectivity of a graph as we insert edges. The ADT in supports insert edge and remove edge operations, so clients are free to use them to make changes in graphs, but there may be performance penalties for certain sequences of operations. For example, union-find algorithms may require reprocessing the whole graph if a client uses remove edge. For most of the graph-processing problems that we consider, adding or deleting a few edges can dramatically change the nature of the graph and thus necessitate reprocessing it. One of our most important challenges in graph processing is to have a clear understanding of performance characteristics of implementations and to make sure that client programs make appropriate use of them. As with the simpler problems that we considered in Parts 1 through 4, our use of ADTs makes it possible to address such issues in a coherent manner. is an example of a graph-processing client. It uses the ADT of , the input-output class of to read the graph from standard input and print it to standard output, and the connectivity class of to find its number of connected components. We use similar but more sophisticated clients to generate other types of graphs, to test algorithms, to learn other properties of graphs, and to use graphs to solve other problems. The basic scheme is amenable for use in any graph-processing app. In through , we examine the primary classical graph representations and implementations of the ADT operations in . These implementations provide a basis for us to expand the interface to include the graph-processing tasks that are our focus for the next several chapters. The first decision that we face in developing an ADT implementation is which graph representation to use. We have three basic requirements. First, we must be able to accommodate the types of graphs that we are likely to encounter in apps (and we also would prefer not to waste space). Second, we should be able to construct the requisite data structures efficiently. Third, we want to develop efficient algorithms to solve our graph-processing problems without being unduly hampered by any restrictions imposed by the representation. Such requirements are standard ones for any domain that we consider-we emphasize them again them here because, as we shall see, different representations give rise to huge performance differences for even the simplest of problems.

Example of a graph-processing client program

This program illustrates the use of the graph-processing ADTs described in this section, using the ADT conventions described in Section 4.5. It constructs a graph with V vertices, inserts edges taken from standard input, prints the resulting graph if it is small, and computes (and prints) the number of connected components. It uses the Graph, GraphIO, and GraphCC ADTs that are defined in , , and (respectively). 

class DriverExample
 {
 public static void main(String[] args)
 { int V = Integer.parseInt(args[0]);
 Graph G = new Graph(V, false);
 GraphIO.scanEZ(G);
 if (V < 20) GraphIO.show(G);
 Out.print(G.E() + " edges ");
 GraphCC Gcc = new GraphCC(G);
 Out.println(Gcc.count() + " components");
 }
 }

For example, we might consider an array of edges representation as the basis for an ADT implementation (see ). That direct representation is simple, but it does not allow us to perform efficiently the basic graph-processing operations that we shall be studying. As we will see, most graph-processing apps can be handled reasonably with one of two straightforward classical representations that are only slightly more complicated than the array-of-edges representation: the adjacency-matrix or the adjacency-lists representation. These representations, which we consider in detail in and , are based on elementary data structures (indeed, we discussed them both in Chapters 3 and 5 as example apps of sequential and linked allocation). The choice between the two depends primarily on whether the graph is dense or sparse, although, as usual, the nature of the operations to be performed also plays an important role in the decision on which to use.

Exercises

Java graphics ltr 17.12 Implement the scanEZ method from : Write a method that builds a graph by reading edges (pairs of integers between 0 and V - 1) from standard input.

Java graphics ltr 17.13 Write an ADT client that adds all the edges in a given array to a given graph.

Java graphics ltr 17.14 Write a method that invokes edges and prints out all the edges in the graph, in the format used in this text (vertex numbers separated by a hyphen).

Screenshot 17.15 Develop an implementation for the connectivity ADT of , using a union-find algorithm (see Chapter 1).

• 17.16 Provide an implementation of the ADT operations in that uses an array of edges to represent the graph. Use a brute-force implementation of remove that removes an edge v-w by scanning the array to find v-w or w-v and then exchanges the edge found with the final one in the array. Use a similar scan to implement the iterator. Note: Reading first might make this exercise easier.