Re: [Boost-users] [graph] Is there a way to detect circles in graphs using boost?

From: Niko Vuokko (niko.vuokko_at_[hidden])
Date: 2008-08-07 03:10:28

Martin Mann wrote:
> Hi,
> 
> I would like to know if there is an easy/straight-forward way to get all 
> circles of a graph using the boost::graph facilities?
> 
> And if so where to look or how to do?
> 
> Thanks a lot,
> 
> Martin

Are you sure you want to find out _all_ the cycles in the graph or 
something else? Finding all cycles is NP-hard, because it implies 
finding the Hamilton tour and for complete graphs for example the amount 
of cycles is exponential.

Most probably you don't need all the cycles and something in P suffices 
for you. What is the problem you want to solve?

If you _really_ want everything (for very small graphs), then you must 
either cook up your own code or do stuff slowly. A very simple algorithm 
for this stuff is in Liu, Wang: A new way to enumerate cycles in graph.
Basically you extend paths from every node and check if some of them 
creates a cycle.

A quick and dirty approach would run separate DFS from every node and 
use the visitor to check if one of the neighbours has already been 
visited (except the one we came from).

niko