0

I want to ask whether it is possible to list all cycle in a really large directed graph. The size of the graph is around 600 node and around 7000 edges.

I have tried naive dfs algorithm and multi threaded it using python process. I set it to use 10 processes. The problem is, I still can not finish the program. It takes too long. I noticed that it listed many duplicates cycles. For example, I found a cycle consists of 200 nodes. It means it computes same cycle 200*200 times! I believe it is useless because it is all the same cycle.

I have tried Johnson algorithm but my 64GB RAM can not handle it. It said it runs out of memory.

Other things that I have done is to list whether a cycle exixts between 2 nodes.

I detect if node A can reach node C and node C can reach node A, it means there is at least a cycle that involves A and C. This algorithm is quite fast and I can list there are around 600,000 possibilities although I know there are many duplicates too. For example if A can reach B, B can reach C, and C can reach A, it means there is a cycle between A and C and B and C.

What should I do?

OmG
  • 18,337
  • 10
  • 57
  • 90
Bharata
  • 685
  • 3
  • 11
  • 23
  • Will this help? https://stackoverflow.com/questions/44789738/union-find-disjoin-set-data-structure-for-directed-graph – Nagarajan Shanmuganathan Nov 15 '17 at 12:33
  • 3
    If there are cycles, then there are an infinite number of cycles. Perhaps you really want just simple cycles in the graph (those where the path consists of unique vertices). – Gordon Linoff Nov 15 '17 at 12:34
  • @Gordon Why should there be infinite number cycles? Consider a clique of size 3 with vertices {a, b, c}. These are the cycles: *{abc, bca, cab, cba, bac, acb}*. I understand your intention. But do you really mean infinite? Moreover, the OP has told that he has a directed graph. That should reduce the number of cycles even if we ignore the *simple cycles* case right? – Nagarajan Shanmuganathan Nov 15 '17 at 12:42
  • 3
    @NagarajanShanmuganathan . . . If A->B->C->A is a cycle, then so is A->B->C->A->B->C->A. That's why I reference simple cycles. – Gordon Linoff Nov 15 '17 at 12:56
  • This is helpful https://stackoverflow.com/a/261595/3768871 – OmG Nov 15 '17 at 13:26
  • Is speed a tight issue for the solution? – MrSmith42 Nov 15 '17 at 13:31
  • Did you write your own algorithm or did you use networkx? – Eric Duminil Nov 15 '17 at 14:00
  • I wrote my own algorithm. It is a simple DFS that's why it is brute force. I have said it is not infinite. I have tried to detect cycles with another algorithm. The problem is not speed, it is not efficient because it is detecting duplicate loop over and over again. – Bharata Nov 15 '17 at 14:38
  • @GordonLinoff Of course I am trying to find simple cycle. Why should I want to find another? As I stated in my question, my problem is I keep detect duplicate loop. – Bharata Nov 15 '17 at 14:39

1 Answers1

0

There would be perfect algorithms for your problem of course, but you could prune some processing by finding a Strongly Connected Component of your graph. There is no chance for a node of a SCC to form a cycle with a node of another SCC. So you can then run your current algorithm for different SCCs separately which could save a lot of processing and traversing.

dipal
  • 71
  • 3