|
|
#include <List.h>
#define Graph_algdeclare(G,V,E)...
#define Graph_algimplement(G,V,E)...
Expanding Graph_algdeclare(G,V,E) produces the following text:
List_of_p<E> cycle_list(const G& g,const V* v);
List_of_p<E> cycle_list(const G& g,const E* e);
List_of_p<E> cycle_list_u(const G& g,const V* v);
List_of_p<E> cycle_list_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 return an arbitrary cycle in g involving a given Edge or Vertex. As usual, functions whose names end in _u treat Graphs as undirected, while functions without the suffix treat Graphs 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.
The sequence of Edges constituting the cycle is returned as a list of Edge pointers (see List(3C++)).
Worst case 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.
If you merely need to know whether a given Edge or Vertex is involved in a cycle, use cycle(3C++).
Graph_alg(3C++) cycle(3C++) List(3C++)