ADTGraph
A graph, like a tree, is a collection of vertices (also called nodes), all of which may or may not be, but generally are, connected by edges. Unlike a tree, which has a special vertex called the root, a graph has no such special vertex and is therefore a more general structure than a tree, in the sense that every tree is a graph, but many graphs are not trees.
There is currently no kind of graph structure available from the STL. On the other hand, there are third-party graph libraries available for use with C++, and the Boost graph library seems to be one of the more popular. In fact much of the Boost library (which contains a lot more than its graph component) is likely to be incorporated into the C++ Standard during the next iteration.
| What kind of Graph interface will we need or want? | |
|---|---|
| We must be able to create a Graph object. | |
| Default constructor for creating an empty Graph object | |
| Should we have each of the "big three"?
It depends on the implementation. |
|
| Destructor | |
| Copy constructor | |
| Overloaded assignment operator | |
| As with all containers, we will want to know if a graph is empty. | |
| Test if a graph is empty (contains no vertices) | |
| Test if a graph is full (contains the maximum number of vertices) | |
| Test if a graph is complete (contains the maximum number of edges) | |
| We must be able to add new values to a graph. | |
| Insert a vertex | |
| Insert an edge | |
| Set the weight of an edge. | |
| We must be able to find values in a graph. | |
| Find a particular vertex | |
| Find a particular edge | |
| We must be able to remove values from a graph. | |
| Delete a particular vertex | |
| Delete a particular edge | |
| Clear the graph of all vertices and edges. | |
| We will need status information about a graph. | |
| Get the number of vertices (size of the graph). | |
| Get the degree, in-degree and/or out-degree of a vertex. | |
| Get the set of all neighbors of a vertex (in an undirected graph). | |
| Get the set of all "to vertices" of a vertex (in a directed graph). | |
| Get the set of all "from vertices" of a vertex (in a directed graph). | |
| Get the number of edges. | |
| Get the weight of an edge. | |
| We may want to process all vertices of the graph for
some reason.
Should these be member functions or functions external to the class? |
|
| Display all values in the graph on an output stream in some order. | |
| Update all values in the graph. | |
| Are there any other operations we will need or might find useful? | |
The above ADT interface for a Graph class gives us a start. We might want to alter or extend the interface during the development of an implementation. Remember that this is our ADT Graph, and hence we would have some flexibility in how we might choose to implement it.