Algorithms Third Edition in C++ Part 5. Graph Algorithms (2006)

CHAPTER SEVENTEEN
Graph Properties and Types

17.2 Graph ADT

We develop our graph-processing algorithms using an ADT that defines the fundamental tasks, using the standard mechanisms introduced in Chapter 4. Program 17.1 is the ADT interface that we use for this purpose. Basic graph representations and implementations for this ADT are the topic of Sections 17.3 through 17.5. Later in the book, 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 functions to sophisticated solutions of difficult problems.

The interface is based on our standard mechanism that hides representations and implementations from client programs (see Section 4.8). It also includes a simple structure type definition that allows our programs to manipulate edges in a uniform way. The interface provides the basic mechanisms that allow clients to build graphs (by constructing the graph and then adding the edges), to maintain the

Program 17.1 Graph ADT interface

This interface is a starting point for implementing and testing graph algorithms. It defines two data types: a trivial Edge data type, including a constructor function that creates an Edge from two given vertices; and a GRAPH data type, which is defined with the standard representation-independent ADT interface methodology from Chapter 4.

The GRAPH constructor takes two arguments: an integer giving the number of vertices and a boolean that tells whether the graph is undirected or directed (a digraph), with undirected the default.

The basic operations that we use to process graphs and digraphs are ADT functions to create and destroy them; to report the number of vertices and edges; and to add and delete edges. The iterator class adjIterator allows clients to process each of the vertices adjacent to any given vertex. Programs 17.2 and 17.3 illustrate its use.

graphs (by removing some edges and adding others), and to examine the graphs (using an iterator for processing the vertices adjacent to any given vertex).

The ADT in Program 17.1 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 applications 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 applications throughout this book.

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 Section 17.5, after we consider several concrete representations and implementations.

A general graph ADT needs to take into account parallel edges and self-loops, because nothing prevents a client program from calling 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 applications, desirable to include them in other applications, and possible to ignore them in still other applications. Self-loops are trivial to handle, but parallel edges can be costly to handle, depending on the graph representation. In certain situations, including aremove parallel edges ADT function 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 Sections 17.3 and 17.4.

Program 17.2 is a function that illustrates the use of the iterator class in the graph ADT. It is a function that extracts a graph’s

Program 17.2 Example of a graph-processing client function

This function shows one way to use the graph ADT to implement a basic graph-processing operation in a manner independent of the representation. It returns all the graph’s edges in a vector.

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 call beg, end, and nxt except as illustrated here, so that we can better understand the performance characteristics of our implementations (see Section 17.5).

template <class Graph>
vector <Edge> edges(Graph &G)
{ int E = 0;
vector <Edge> a(G.E());
for (int v = 0; v < G.V(); v++)
{
typename Graph::adjIterator A(G, v);
for (int w = A.beg(); !A.end(); w = A.nxt())
if (G.directed() ||v<w)
a[E++] = Edge(v, w);
}
return a;
}

set of edges and returns it in a C++ Standard Template Library (STL) vector. 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 vector is immaterial and will differ from implementation to implementation. We use a template for such functions to allow for using multiple implementations of the graph ADT.

Program 17.3 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 Figure 17.7. 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 book 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 functions.

Figure 17.7 Adjacency lists format

This table illustrates yet another way to represent the graph in Figure 17.1: 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.

Program 17.3 A client function that prints a graph

This implementation of the show function from the io class of Program 17.4 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 Figure 17.7).

template <class Graph>
void IO<Graph>::show(const Graph &G)
{
for (int s = 0; s < G.V(); s++)
{
cout.width(2); cout << s << “:”;
typename Graph::adjIterator A(G, s);
for (int t = A.beg(); !A.end(); t = A.nxt())
{ cout.width(2); cout << t << “ ”; }
cout << endl;
}
}

As discussed in Section 17.5, we often package related graph-processing functions into a single class. Program 17.4 is an interface for such a class. It defines the show function of Program 17.3 and two functions for inserting into a graph edges taken from standard input (see Exercise 17.12and Program 17.14 for implementations of these functions).

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

• Compute the value of some measure of the graph.

• Compute some subset of the edges of the graph.

• Answer queries about some property of the graph.

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 Section 17.1 immediately bring to mind a host of computational problems.

Program 17.4 Graph-processing input/output interface

This class illustrates how we might package related graph-processing functions together in a single class. It defines functions for printing a graph (see Program 17.3); inserting edges defined by pairs of integers on standard input (see Exercise 17.12); and inserting edges defined by pairs of symbols on standard input (see Program 17.14).

template <class Graph>
class IO
{
public:
static void show(const Graph &);
static void scanEZ(Graph &);
static void scan(Graph &);
};

Our convention for addressing such tasks will be to build ADTs that are clients of the basic ADT in Program 17.1, but that, in turn, allow us to separate client programs that need to solve the problem from implementations. For example, Program 17.5 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 Section 18.5, and we develop similar ADTs throughout the book. Typically, such ADTs include a preprocessing public member function (usually the constructor), private data members that keep information learned during the preprocessing, and query public member functions that use this information to provide clients with information about the graph.

In this book, 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 calls to insert, then process them either by calling some ADT function 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 calling insert or remove necessitates reprocessing the graph. Dynamic problems,

Program 17.5 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 member function returns the number of connected components and the connect member function tests whether two given vertices are connected. Program 18.4 is an implementation of this interface.

template <class Graph>
class CC
{
private:
// implementation-dependent code
public:
CC(const Graph &);
int count();
bool connect(int, int);
};

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 Program 17.1 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

Program 17.6 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 assumes that Program 17.1, Program 17.4, andProgram 17.5 (with implementations) are in the files GRAPH.cc, IO.cc, and CC.cc (respectively).

#include <iostream.h>
#include <stdlib.h>
#include “GRAPH.cc”
#include “IO.cc”
#include “CC.cc”
main(int argc, char *argv[])
{ int V = atoi(argv[1]);
GRAPH G(V);
IO<GRAPH>::scan(G);
if (V < 20) IO<GRAPH>::show(G);
cout << G.E() << “edges”;
CC<GRAPH> Gcc(G);
cout << Gcc.count() << “components” << endl;
}

Parts 1 through 4, our use of ADTs makes it possible to address such issues in a coherent manner.

Program 17.6 is an example of a graph-processing client program. It uses the basic ADT of Program 17.1, the input-output class of Program 17.4 to read the graph from standard input and print it to standard output, and the connectivity class of Program 17.5 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 application.

In Sections 17.3 through 17.5, we examine the primary classical graph representations and implementations of the ADT functions in Program 17.1. 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 applications (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.

For example, we might consider a vector of edges representation as the basis for an ADT implementation (see Exercise 17.16). 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 applications can be handled reasonably with one of two straightforward classical representations that are only slightly more complicated than the vector-of-edges representation: the adjacency-matrix or the adjacency-lists representation. These representations, which we consider in detail in Sections 17.3 and 17.4, are based on elementary data structures (indeed, we discussed them both in Chapters 3 and 5 as example applications 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

• 17.12 Implement the scanEZ function from Program 17.4: write a function that builds a graph by reading edges (pairs of integers between 0 and V− 1) from standard input.

• 17.13 Write an ADT client that adds all the edges in a given vector to a given graph.

• 17.14 Write a function that calls edges and prints out all the edges in the graph, in the format used in this text (vertex numbers separated by a hyphen).

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

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