From: Martin Mann (mmann_at_[hidden])
Date: 2008-08-07 04:42:26
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!
So far,
Martin