cycle_list(C++)

Synopsis

   #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);

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 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++)).

Complexity

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.

Notes

If you merely need to know whether a given Edge or Vertex is involved in a cycle, use cycle(3C++).

References

   Graph_alg(3C++)
   cycle(3C++)
   List(3C++)