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

From: Martin Mann (mmann_at_[hidden])
Date: 2008-08-07 18:54:13

Hi Niko,

thanks very much for your search on the SMILES problem. And yes you are 
absolutely right that for SMILES encoding no full cycle enumeration is 
needed. Actually a DFS is sufficient and David showed how to do.

Independently, I could leave the problem of writing an algorithm for 
full cycle enumeration. :) Today, I have implemented the Horton 
algorithm of my last posting using BFS and a customized bfs_visitor. It 
is able to identify all cycles (at least for the small examples I tried) 
but as expected one has to worry about multiple identifications of the 
same cycles. But this is easy to solve by "normalizing" the cycles to 
start with the smallest index. At least it is working and I have learned 
some algorithmic things and BGL usage! ;)
Next I want to implement your DFS suggestion and do a small comparison 
of the performance of both approaches. Think one can tweak this approach 
too if only cycle closing back edges to indices lower than the start 
vertex are used. This might increase performance. I will have a look. :)
Finally, I might check the paper you mentioned (downloaded already) to 
see if a fast BGL implementation can be done and how it performs in 
comparison to the first two.

We will see how much time I will spent on that! ;)

So thanks again for the dedicated help!

Martin

Niko Vuokko wrote:
> 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