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

From: David Walthall (walthall_at_[hidden])
Date: 2008-08-07 17:35:55

Martin Mann wrote:
> 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.

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