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 19:03:24

Hi David,

thanks a lot for the detailed help on the SMILES conversion!
Great. Seems that the encoding is straight forward in BGL and easy to 
do. I will have a look at that soon and think it wont be a big deal.

Do you have any code fragment for the encoding at hand that I might use 
as a guide or that can be directly be reused? If not no problem at all! 
You helped already a lot!

Another thing that I am facing as soon as the SMILES encoding is working 
is the generation of "canonical SMILES" such that one gets a unique 
encoding of the graph independently of the node the DFS is started from.
Do you have any solution for that too or worked on that?

So once again, many thanks for your help,

Martin

David Walthall wrote:
> Hi Martin,
> 
> To generate SMILES strings, you don't need to enumerate the cycles.  For 
> an undirected graph, all you have to do is a depth first search.  Every 
> back edge (that is not also a tree edge) is the closing of a cycle.  You 
> won't actually need to remove any edges since the depth first search 
> generates a tree (of the tree edges) which is exactly what a SMILES 
> string is.  The depth first search also gives a list of the cycles that 
> were "broken" by the set difference of the back edges and the tree 
> edges.  The trickiest part that I found was the need to add the cycle 
> labels to previously visited atom labels.  I ended up doing two depth 
> first searches: the first was to generate the list of pairs of verticies 
>  that were part of "broken" cycles, and the second was to actually 
> generate the string.
> 
> David