Boost logo

Boost Users :

From: Niko Vuokko (niko.vuokko_at_[hidden])
Date: 2008-08-07 17:07:04


Martin Mann wrote:
> Hi Niko,
>
> thanks for your answer!
>
> > Martin Mann wrote:
> > > Hi,
> > >
> > > I would like to know if there is an easy/straight-forward way to get
> > > all circles of a graph using the boost::graph facilities?
> > >
> > > And if so where to look or how to do?
> > >
> > > Thanks a lot,
> > >
> > > Martin
> >
> > Are you sure you want to find out _all_ the cycles in the graph or
> > something else? Finding all cycles is NP-hard, because it implies
> > finding the Hamilton tour and for complete graphs for example the
> > amount of cycles is exponential.
>
> Right. Currently, I want to detect all (simple) cycles (without repeated
> nodes) in a graph, but the graphs size is small (less than a hundred
> nodes) with low connectivity. Therefore I hope to achieve reasonable
> results even with exhaustive solutions.
>
>
> > Most probably you don't need all the cycles and something in P
> > suffices for you. What is the problem you want to solve?
>
> 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.
>
>
> > If you _really_ want everything (for very small graphs), then you must
> > either cook up your own code or do stuff slowly. A very simple
> > algorithm for this stuff is in Liu, Wang: A new way to enumerate
> > cycles in graph.
> > Basically you extend paths from every node and check if some of them
> > creates a cycle.
>
> Yes, I found the paper yesterday night but have not checked about the
> details.
>
> Another approach I found was by Horton. It is the initial step (to
> enumerate all simple cycles) to construct the optimal cycle basis of a
> graph. As a sketch it works like:
>
> for all edges (u,v) {
> for all nodes x != u,v {
> p1 = shortest_path(x,u);
> p2 = shortest_path(x,v);
> if (intersection(p1,p2) == x) {
> report_cycle(p1 + invert(p2));
> }
> }
> }
>
> I like this method due to its simplicity and the possibility to reuse
> e.g. BFS for shortest_path. So the implementation will stay very small.
> Furthermore, one can add some tweaks like only nodes with degree > 1 are
> checked etc.
>
> But if somebody knows a better approach or has some templated function
> for boost::graphs, POST IT! ;)
>
>
> > A quick and dirty approach would run separate DFS from every node and
> > use the visitor to check if one of the neighbours has already been
> > visited (except the one we came from).
>
> Is this approach ensuring to find all cycles only once? Think I will
> find some cycles several times or am I just wrong? But I will check
> that! Thanks!

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net