cycle(3C++)


cycle, cycle_u -- determine whether a Graph contains cycles

Synopsis

   #define Graph_algdeclare(G,V,E)... 
   #define Graph_algimplement(G,V,E)... 
   Expanding Graph_algdeclare(G,V,E) produces the following text:
       V* cycle(const G& g);
       V* cycle_u(const G& g);
       int cycle(const G& g,const V* v);
       int cycle_u(const G& g,const V* v);
       int cycle(const G& g,const E* e);
       int cycle_u(const G& g,const E* e);

Description

A cycle is a sequence of Edges starting at a Vertex and returning to that Vertex (no Edge can appear twice in the sequence). For an undirected Graph, the sequence must include at least three Edges; for a directed Graph, at least one. These functions indicate whether a given Graph contains cycles. As usual, functions whose names end in _u treat Graphs as undirected, while functions without the suffix treat Graph as directed. A cycle in an undirected Graph must include at least three Edges; a cycle in a directed Graph must include at least one.

V* cycle(const G& g);

V* cycle_u(const G& g); These determine whether g contains cycles; if there are no cycles, they return zero. Otherwise, they return a pointer to an arbitrary Vertex involved in a cycle.

int cycle(const G& g,const V* v);

int cycle_u(const G& g,const V* v); These return non-zero if there is a cycle involving Vertex v.

int cycle(const G& g,const E* e);

int cycle_u(const G& g,const E* e); These return non-zero if there is a cycle involving Edge e.

Complexity

O(max(v,e)), where v is the number of Vertices and e is the number of Edges in the Graph. Average performance seems much better.

Notes

These functions only tell if one or more cycles exist; to examine the cycles, use cycle_list(3C++).

References

Graph_alg(3C++), cycle_list(3C++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004