Martin Mann wrote:
Hi Niko,
thanks for your answer!
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.
Right. Currently, I want to detect all (simple) cycles (without repeated nodes) in a graph, but the graphs size is small (less than a hundred nodes) with low connectivity. Therefore I hope to achieve reasonable results even with exhaustive solutions.
Most probably you don't need all the cycles and something in P suffices for you. What is the problem you want to solve?
Maybe you are right. What I am currently working on is an easy transformation of graphs describing molecules into the so called SMILES string representation. This includes the detection and handling of cycles so I came upon that problem. But I have to check if I "only" need to break all cycles that is much easier than enumeration of all of them. If the only breaking is neccessary, I would perform DFS with a customized visitor to detect a cycle via a back_edge. Than remove the edge to break the cycle and repeat the procedure until all cycles are broken. Just as a first brute force idea. Maybe there are better ways to do so.
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.
Yes, I found the paper yesterday night but have not checked about the details.
Another approach I found was by Horton. It is the initial step (to enumerate all simple cycles) to construct the optimal cycle basis of a graph. As a sketch it works like:
for all edges (u,v) { for all nodes x != u,v { p1 = shortest_path(x,u); p2 = shortest_path(x,v); if (intersection(p1,p2) == x) { report_cycle(p1 + invert(p2)); } } }
I like this method due to its simplicity and the possibility to reuse e.g. BFS for shortest_path. So the implementation will stay very small. Furthermore, one can add some tweaks like only nodes with degree > 1 are checked etc.
But if somebody knows a better approach or has some templated function for boost::graphs, POST IT! ;)
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).
Is this approach ensuring to find all cycles only once? Think I will find some cycles several times or am I just wrong? But I will check that! Thanks!
Are you absolutely sure that a simple spanning tree wouldn't be enough? At least to me it seems that you need a spanning tree and some housecleaning after that. This would be a very simple and quick task. I wouldn't dare to try enumeration of cycles for graphs more than ten nodes, it can so easily explode and give billions of cycles, the complexity is actually much more than exponential. I checked some info on SMILES, it looks like 1. Remove hydrogens 2. Create some spanning tree 3. Traverse the tree to mark up broken cycles niko