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

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