2

For a huge graph I need an efficient implementation for Python to find all the cycles/circuits in the graph. Currently I am using the package networkx function cycle_basis, which "returns a list of cycles which form a basis for cycles of G. A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis. Here summation of cycles is defined as “exclusive or” of the edges. Cycle bases are useful, e.g. when deriving equations for electric circuits using Kirchhoff’s Laws."

What is an efficient, preferably pre-implemented, way of finding all the cycles in my graph? Maybe I can build on top an implementation on top of the basis (intersecting the cycles).

PeterHeuz
  • 390
  • 1
  • 4
  • 17
  • 1
    Does the [`simple_cycles`](http://networkx.readthedocs.org/en/networkx-1.11/reference/generated/networkx.algorithms.cycles.simple_cycles.html#networkx.algorithms.cycles.simple_cycles) function do what you want? It looks like it omits only cycles that are "cyclic permutations" of each other (i.e. the same set of nodes, just with a different start and end node). – Blckknght Feb 11 '16 at 21:07
  • @Blckknght Want to turn that into an answer? It looks like exactly what OP wants. – Joel Feb 12 '16 at 09:00
  • @Blckknght: Thank you for the quick answer! `simple_cycles` does look like what I need, but I use an undirected graph though. I could transform it into a directed graph by adding two oppositely directed edges for each undirected edge, but isn't that quite inefficient? I am working on a graph with more than 100,000 nodes and 200000 edges and have similar graphs 400 times. – PeterHeuz Feb 12 '16 at 20:00
  • Try looking at this question: http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs. Most of the answers focus on the directed case (basically doing `simple_cycles` I think), but one of the answers gives a detailed discussion of the undirected case. – Joel Feb 12 '16 at 21:13
  • @PeterHeuz Did that question help? – Joel Feb 15 '16 at 03:25
  • @Joel: I found [this answer](http://stackoverflow.com/a/18388696/5240546) helpful, thanks! He explained in detail how to get the simple base as well as how to get all cycles from it. I am going to transform my graph into a symmetric, directed graph and us the `simple_cycles` function. I am posting then how it went speed-wise. – PeterHeuz Feb 15 '16 at 19:35

0 Answers0