Re: [Boost-users] [Graph] find cycles

From: Young, Michael (Michael.Young_at_[hidden])
Date: 2006-09-27 12:43:57

>  Please, couold you suggest me  a simple way to find a cycle into a graph (just a sentence, no code)? What about the computational complexity?

You really need to get the BGL book or read the online tutorial (see the documentation page for BGL - http://www.boost.org/libs/graph/doc).  My explanation here will not do the algorithm justice, and there really is no "shortcut" - you do need to understand the concepts presented in that documentation.

To find cycles, you start a recursive traversal starting at each "incomplete" vertex (node) in the graph, keeping track of what nodes you've visted.  A "completed" vertex is one that has had all its outbound edges traversed both ways ("out and back").  The visitation traversal occurs in a Depth-First search manner, and the nodes "in progress" (i.e., all nodes in the paths originating with the current start node that is not yet completed - i.e., traversal is not finished/paths not exhaustively traversed) are marked in a distinct manner.  If, while traversing the nodes, one is found with this distinct marking, then there is a cycle in the graph.  There is also ways to determine the extent of the cycle (i.e., what edges and vertexes are involved/reachable in the cycle), and that is also discussed in the book.

The computational complexity is based on the traversal - i.e., the complexity of the DFS - see the documentation - the cost is related to the actual graph type, I believe.

HTH,
  Mike