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.

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)

}