The C++ Graph Classes: A Tutorial - Graph(3C++) and Graph_alg(3C++)

What is a Graph?

A graph is a data structure which includes the following components:

a set of vertices (or nodes) which represent the objects being related. In the Graph package, the Vertex class represents vertices. In our example, each widget module is represented by a Vertex.
a set of edges (or arcs) which represent the relationships between the vertices. An edge is an ordered pair of vertices (v1, v2), where v1 represents the source (or tail) of the edge, and v2 represents the destination (or head) of the edge. One or more edges may exist between two given vertices. In the Graph package, the Edge class represents edges. In our example, each widget relation is represented by an Edge.
the graph itself, which represents the universe in which the vertices and edges may be placed to facilitate queries, etc. In the Graph package, the Graph class represents graphs. In our example, the widget is represented by a Graph.

Edges have inherent directionality; however, that directionality may be ignored if the relation that the edge represents is symmetric, i.e., the data items are not an ordered pair. In this case, their relation is represented by an undirected edge which can be used as if it were two directed edges, one in each direction between the items. Graphs in which the edge directionality is ignored are termed undirected graphs; where the edge directionality is significant, they are termed directed graphs. In our example, the manufacturing process will be represented by a directed graph.

Thus, the same Graph package may be used in either a directed graph or undirected graph application: the operations that are defined on the Graph manipulate the associated Edges under one paradigm or the other. The Graph Algorithms that accompany the Graph package include versions that support both directed and undirected graphs, where dual versions are appropriate. We'll see examples of both directed and undirected Graphs later in this tutorial.

In a directed Graph, if an edge starts at a vertex, it is an out Edge; likewise, if it ends at a vertex, it is an in Edge. In our example, if we consider the Edge between modules B and Z, it is considered both an out Edge of B, and an in Edge of Z. If it is both an out edge and an in edge of the same vertex, that is, it starts and ends at the same vertex, it is also called a loop Edge.

Traversing a graph (visiting the vertices in some order) is often required. The Graph Algorithms package provides versions of some of the most well-known traversal algorithms. Concurrent traversals may also be needed. The Graph package provides this capability through the use of Tickets, which are used in the same way that tickets are used in bank or delicatessen queues. We'll discuss traversals in detail in the section, ``Traversals''.

At a given point in time, a vertex or edge may need to be included in more than one graph simultaneously. For instance, in the manufacturing example described above we might later want to create another product that contains several of the same modules as in the widget. We'll see an example of this as part of the discussion of one of the Graph class members, induced_graph (see the section, ``Graph Subgraph Creation'').

The Graph package makes this possible by requiring Vertices and Edges to have reference semantics, that is, they are handled via pointers. A Vertex or Edge can become a Graph component only after it has been independently created by the user (using the new operator for dynamically-declared variables, or static declaration of local variables); after insertion of the Vertex or Edge into a Graph, queries can be made via pointers as to its status in the Graph.

Similarly, Vertices and Edges can only be destroyed by the user (through the use of the delete operator in the case of dynamically declared variables, or by exiting the block). Since user Vertices and Edges are derived from generic versions supplied with the Graph package, the package can silently remove any Vertices and Edges that have been destroyed from all affected Graphs. We'll discuss this derivation process in detail in the section, ``Using the Graph Classes to Create Objects''.

Let's begin discussing Graphs by continuing with the manufacturing example.