Find a cycle in an undirected graph (boost) and return its vertices and edges.

Question

I need a functions thats find a cycle in an undirected graph (boost) and returns its vertices and edges. It needs only return the vertices/edges of one cycle in the graph. My question is - what is the best way to do this using with boost? I am not experienced using it.

Answer 1

Generally you can do this with a depth first search. I'm not intimately familiar with boost's graphing facilities but this page will give you an overview of the algorithm.

Answer 2

I do not know Boost, but here is the answer from S.O. at a conceptual level:

Here is my guess: walk through the graph using BFS. On every node note its "depth" and add a reference to a "parent" (should be only one even if there are many cycles). Once you discover that a link from A to B creates a cycle (because B is already colored), then: 1) Backtrack from A back to the root, save the edges / vertices along the way. 2) Backtrack from B back to the root, save the edges / vertices along the way. 3) Add A, B, AB 4) "Sort" to restore the proper order. Consider using a LIFO (stack) for 1) and a FIFO for 2)

I hope this helps.

Answer 3

If you want to find a cycle, then using depth first search should do just fine. The DFS visitor has a back_edge function. When it's called, you have an edge in the cycle. You can then walk the predecessor map to reconstruct the cycle. Note that:

• There's the strong_components function, to find, well, strong components
• Finding all cycles, as opposed to a cycle, is much harder problem, and I believe Boost.Graph does not have a implementation for that at present