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