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