Cycles

In many Graph applications, it is often necessary to establish whether a given Graph is in fact a tree, i.e., a Graph that represents a hierarchical relationship between Vertices. Trees are used extensively to solve programming problems as varied as sorting a list of alphanumeric strings (such as English language words) to representing the Table of Contents of this document.

To maintain a hierarchical relationship, the Graph must guarantee that it does not contain a cycle, that is, a sequence of Edges that both start and end at the same Vertex. A family of cycle algorithms are defined:

       // for directed Graphs
       Vertex* cycle(const Graph& g);

       int cycle(const Graph& g, const Vertex* v);
       List_of_p<Edge> cycle_list(const Graph& g,
           const Vertex* v);

       int cycle(const Graph& g, const Edge* e);
       List_of_p<Edge> cycle_list(const Graph& g,
           const Edge* e);

For a given Graph g, cycle(g) returns the first Vertex it finds that is part of a cycle. In directed Graphs, a cycle may be of any length greater than 0 (thus, a loop Edge creates a cycle at the Vertex which is its source and destination). Successive calls to cycle will not return additional Vertices that satisfy the test: to retrieve these, the Graph must be altered.

The Graph can be systematically altered using cycle_list which identifies the Edges that define a cycle:

       .
       .
       .
       Vertex* v = cycle(g);
       while (v) {
           List_of_p<Edge> elist = cycle_list(g, v);
               // returns Edges in the cycle
           g.remove(elist.head());
               // arbitrarily remove an Edge
           v = cycle(g);
               // perhaps a new Vertex will be identified
           }
       .
       .
       .

This method provides a quick way to find many cycles but has the same drawback that any very simple algorithm in this regard will have: an Edge that contributes to two or more cycles will, when removed, have identified only one of them. Further processing that more closely inspects these areas of the Graph can recover the cycles that remain.

We've used cycle_list(g, v) here: cycle_list is also defined for use with a given Edge. cycle(g, v) tests whether a given Vertex v is part of a cycle in g, in which case it returns true; cycle(g, e) does the same for an Edge e.

Versions of these cycle functions are also defined for undirected graphs. In an undirected Graph, the cycle found must be of length 3 or greater.

       //for undirected Graphs
       Vertex* cycle_u(const Graph& g);

       int cycle_u(const Graph& g, const Vertex* v);
       List_of_p<Edge> cycle_list_u(const Graph& g,
           const Vertex* v);

       int cycle_u(const Graph& g, const Edge* e);
       List_of_p<Edge> cycle_list_u(const Graph& g,
           const Edge* e);