|
|
#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);
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.
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.
These functions only tell if one or more cycles exist; to examine the cycles, use cycle_list(3C++).