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