2

I am having trouble finding an efficient solution (or any solution as a matter of fact) for enumerating cycles in a very large graph.

The graph has 1 million nodes and 1.25 million edges. I have tried using an algorithm from the NetworkX library, but the process was killed with exit code 137 (Python) after 24 hours.

I have also tried using Tarjan's algorithm described here, but this process has been running for 25 days on my server, with no results yet.

Are there any approaches you could recommend to find all cycles? Would using MapReduce help? Are there any other approaches for very large graphs?

Community
  • 1
  • 1
matsair
  • 51
  • 1
  • 5
  • Is your graph directed or undirected? In case of undirected graph, I have found [a comment to this question](http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph) that states that with your numbers you'll have a 2^125000 *different* cycles, that would take quite a lot of time to enumerate them all. – Vesper Aug 01 '16 at 13:01
  • Have you tried Union Rank Algorithm. – Prakhar Asthana Aug 01 '16 at 13:49
  • 2
    There are efficient algorithms for detecting [strongly connected components](https://en.wikipedia.org/wiki/Strongly_connected_component) (including, coincidentally, [one developed by Tarjan](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)). Perhaps it would speed things up if you first break the graph into SCCs and then look for cycles in each SCC separately? And obviously porting your code to a compiled language would make it run a lot faster. – r3mainer Aug 01 '16 at 14:09
  • 1
    Have you considered the possibility that there are simply far too many cycles to enumerate in a reasonable time? On a complete graph with just 15 vertices, there are already more than 15!/15 = 87178291200 length-15 cycles, and many more shorter ones. – j_random_hacker Aug 01 '16 at 14:29
  • 1
    This is almost certainly hopeless. You're looking at something like (10^6)^(10^6) cycles. That's 1 followed by 6 million zeros. math.stackexchange.com/a/727620/201006 You need to reformulate your problem. – Joel Aug 01 '16 at 20:41

0 Answers0