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 17:07:04

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