[NetworkX-discuss] Cycle detection in networkx graphs?

[Andrés Jaramillo-Botero]

Is there an computationally efficient embedded method to detect
multi-level cycles (cycles within cycles) in a networkx graph and
report on involved nodes/edges?.
Andres

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
NetworkX-discuss mailing list
NetworkX...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/networkx-discuss

[Aric Hagberg]

Hi Andrés,

On Mon, Aug 21, 2006 at 04:05:00PM -0700, Andrés Jaramillo-Botero wrote:
> Is there an computationally efficient embedded method to detect
> multi-level cycles (cycles within cycles) in a networkx graph and
> report on involved nodes/edges?.

Right now there aren't any functions to find cycles. One simple
approach is to do a depth first search and look for "back edges" at
each level (that would indicate a cycle). I have a prototype DFS code
I could send you (it will soon appear in NetworkX) as an example that
could be modified to do this.

Depending on exactly what you are doing this problem can get quite
hard (I suspect it is NP-complete). I don't know the literature on
cycle counting and finding but I'd guess there are much better methods.

Aric

[Andrés Jaramillo-Botero]

Thanks Aric, I would definitely like to try your code. Right now, I'm
doing an exhaustive search using the adjacency matrix row-column
entries information. The problem I have is that for very large systems
the cost is prohibitive.
Andres

[Aric Hagberg]

Andrés,

I checked in the DFS code at
https://networkx.lanl.gov/browser/networkx/trunk/networkx/paths.py

Here is a code snippet that does something with cycles.
I'm not sure if I got the counting right or if it
finds all of the cycles - but it is a start.
This may not be the right idea - I just did a quick look and found
http://www.math.tau.ac.il/~nogaa/PDFS/ayz4.pdf
which may be of help and also has a list of references.

Aric

--- cut ---

#/usr/bin/env python

from networkx import *

def cycle_lengths(G,source):
"""
Traverse the graph G with depth-first-search from source.
Look for cycles.
"""
seen={} # nodes seen
pred={} # predecessors
queue=[source] # use as LIFO queue
seen[source]=0 # level seen
cycles=[]
while queue:
v=queue.pop()
level=seen[v]
for w in G.neighbors(v):
if w not in seen:
pred[w]=v
seen[w]=level+1
queue.append(w)
else: # possible cycle
if pred[v]==w: # we've already seen this edge
continue
else: # cycle
cycle_length=seen[w]+seen[v]+1
cycles.append(cycle_length)
print "found cycle of length %s"%(cycle_length)
return cycles

G=cycle_graph(4)
#G.add_edge(0,2)
print cycle_lengths(G,0)

--- cut ---

[Andrés Jaramillo-Botero]

Great, I'll try it tonight and get back to you with my results.
Andrés