Previous    Next

### Variations, Extensions, and Costs

##### Screenshot Digraph representations

The adjacency-matrix and adjacency-lists representations of a digraph have only one representation of each edge, as illustrated in the adjacency-matrix (top) and adjacency-lists (bottom) representation of the set of edges in Screenshot interpreted as a digraph (see Screenshot, top).

## Vertex-degrees class implementation

This class provides a way for clients to learn the degree of any given vertex in a Graph in constant time, after linear-time preprocessing in the constructor. The implementation is based on maintaining a vertex-indexed array of vertex degrees as a private data field and using a method degree to return array entries. We initialize all entries to 0, then process all edges in the graph, incrementing the appropriate entry for each edge. We use classes like this one throughout the tutorial to develop object-oriented implementations of graph-processing operations as clients of class Graph.

```class GraphDegree
{
private Graph G;
private int[] deg;
GraphDegree(Graph G)
{ this.G = G;
deg = new int[G.V()];
for (int v = 0; v < G.V(); v++)
{
deg[v] = 0;
for (int w = A.beg(); !A.end(); w = A.nxt())
deg[v]++;
}
}
int degree(int v)
{ return deg[v]; }
}
```

For each of the graph-processing tasks that we consider in this tutorial, we encapsulate solutions in classes like this one, with a constructor and query methods specific to the task that perhaps use private methods and communicate via private fields. Clients create objects whose methods do the graph processing. This approach amounts to extending the graph ADT interface by defining a cooperating set of classes. Any set of such classes defines a graph-processing interface, but each encapsulates its own constructor, private fields, and methods. There are many other ways to build upon an interface in Java. One way to proceed is to simply add query methods (and whatever private fields and methods we might need) to the basic Graph ADT definition. While this approach has all of the virtues extolled in Chapter 4, it also has some serious drawbacks, because the world of graph-processing is significantly more expansive than the kinds of basic data structures that are the subject of Chapter 4. Chief among these drawbacks are the following:

• There are many more graph-processing operations to implement than we can accurately define in a single interface.
• Simple graph-processing tasks have to use the same interface needed by complicated tasks.
• One method can access a field intended for use by another method, contrary to encapsulation principles that we would like to follow.

Interfaces of this kind have come to be known as fat interfaces. In a tutorial filled with graph-processing algorithms, an interface of this sort would be fat indeed. Another approach is to use inheritance to define various types of graphs that provide clients with various sets of graph-processing tasks. Comparing the intricacies of this approach with the simpler approach that we use is a worthwhile exercise in the study of software engineering, but would take us still further afield from the subject of graph-processing algorithms, our main focus. Table 17.1 shows the dependence of the cost of various simple graph-processing operations on the representation that we use. This table is worth examining before we consider the implementation of more complicated operations; it will help you to develop an intuition for the difficulty of various primitive operations. Most of the costs listed follow immediately from inspecting the code, with the exception of the bottom row, which we consider in detail at the end of this section.

##### Table 17.1. Worst-case cost of graph-processing operations
 The performance characteristics of basic graph-processing ADT operations for different graph representations vary widely, even for simple tasks, as indicated in this table of the worst-case costs (all within a constant factor for large V and E). These costs are for the simple implementations we have described in previous sections; various modifications that affect the costs are described in the text of this section. array of edges adjacency matrix adjacency lists space E V2 V + E initialize empty 1 V2 V copy E V2 E destroy 1 V E insert edge 1 1 1 find/remove edge E 1 V is v isolated? E V 1 path from u to v? E lg* V V2 V + E

#### Exercises

Develop an adjacency-matrix representation for dense multigraphs, and provide an ADT implementation for Program 17.1 that uses it.

17.40 Why not use a direct representation for graphs (a data structure that models the graph exactly, with vertex objects that contain adjacency lists with references to the vertices)?

17.41 Why does Program 17.11 not increment both deg[v] and deg[w] when it discovers that w is adjacent to v?

17.42 Add to the graph class that uses adjacency matrices (Program 17.7) a vertex-indexed array that holds the degree of each vertex. Add a method degree that returns the degree of a given vertex.

Do Exercise 17.42 for the adjacency-lists representation.

17.44 Add a row to Table 17.1 for the problem of determining the number of isolated vertices in a graph. Support your answer with method implementations for each of the three representations.

17.45 Give a row to add to Table 17.1 for the problem of determining whether a given digraph has a vertex with indegree V and outdegree 0. Support your answer with method implementations for each of the three representations. Note: Your entry for the adjacency-matrix representation should be V.

Use doubly linked adjacency lists with cross links as described in the text to implement a constant-time remove edge method remove for the graph ADT implementation that uses adjacency lists (Program 17.9).

Add a remove vertex method remove to the doubly linked adjacency-lists graph class described in the previous exercise.

17.48 Modify your solution to Exercise 17.16 to use a dynamic hash table, as described in the text, such that insert edge and remove edge take constant amortized time.

Add to the graph class that uses adjacency lists (Program 17.9) a symbol table to ignore duplicate edges so that it represents graphs instead of multigraphs. Use dynamic hashing for your symbol-table implementation so that your implementation uses space proportional to E and can insert, find, and remove edges in constant time (on the average, amortized).

Develop a multigraph class based on a array-of-symbol-tables representation (with one symbol table for each vertex, which contains its list of adjacent edges). Use dynamic hashing for your symbol-table implementation so that your implementation uses space proportional to E and can insert, find, and remove edges in constant time (on the average, amortized).

Develop a graph ADT intended for static graphs, based upon a constructor that takes a array of edges as an argument and uses the basic graph ADT to build a graph. (Such an implementation might be useful for performance comparisons with the implementations described in Exercises 17.52 through 17.55.)

Develop an implementation for the constructor described in Exercise 17.51 that uses a compact representation based on a class for vertices that contains an adjacent-edge count and an array with one vertex index corresponding to each adjacent edge and a class for graphs that contains a vertex count and an array of vertices.

• 17.53 Add to your solution to Exercise 17.52 a method that eliminates self-loops and parallel edges, as in Exercise 17.34.

17.54 Develop an implementation for the static-graph ADT described in Exercise 17.51 that uses just two arrays to represent the graph: one array of E vertices, and another of V indices or pointers into the first array. Implement GraphIO for this representation.

• 17.55 Add to your solution to Exercise 17.54 a method that eliminates self-loops and parallel edges, as in Exercise 17.34.

Develop a graph ADT interface that associates (x, y) coordinates with each vertex so that you can work with graph drawings. Include methods drawV and drawE to draw a vertex and to draw an edge, respectively.

Write a client program that uses your interface from Exercise 17.56 to produce drawings of edges that are being added to a small graph.

Develop an implementation of your interface from Exercise 17.56 that produces a PostScript program with drawings as output (see Section 4.3).

Develop an implementation of your interface from Exercise 17.56 that uses appropriate methods from the Java Graphics2D class to draw the visualization on your display.

• 17.60 Extend your solution to Exercises 17.56 and 17.59 to develop an abstract class in support of animating graph-processing algorithms so that you can write client programs that provide dynamic graphical animations of graph algorithms in operation (see Programs 6.16 and 6.17). Hint: Focus on the nxt method in the iterator.

 Previous    Next