I'm trying to find cycles of length 2, 3, 4, and 5 in a directed graph. So far I've had decent luck on most inputs using the simple_cycles algorithm from networkx (https://networkx.readthedocs.io/en/stable/reference/generated/networkx.algorithms.cycles.simple_cycles.html), except in the cases with very large graphs. Is there an algorithm for finding smaller cycles that has a faster runtime?
How to find cycles of a given length in a directed graph? (Using networkx)
can't you traverse recursively and having a hashmap of the (node,level) as you have visited in the recursive function so once you come to the node that also exists in the hashmap then you already know it is a cycle and then you substract the current level from the one you have in your hashset then you return that to add to a linkedlist so that at the end of recursive call you have the list that has cycles that are smaller than a certain size. –
Baal
graph-tool is usually faster then NetworkX and has a function called all_circuits for it. It does not look like it can be limited to cycles of certain lengths explicitly, but perhaps it delivers smaller ones first and you can stop the iterator once it starts to return larger ones. –
Coucal
Can you please provide a small sample graph so that we can try out ourselves? –
Quittor
@MrIrrelevant the post is 7+ years old –
Patrilineage
For cases when the given length is something obscure, I also recommend graph-tool as @Robert Haas pointed out in the comments (although not sure what the result of all_circuits is, because if you have one circuit, you have infinitely many as you just keep repeating that one circuit).
There isn't really a great general solution. Firstly, in the general example, if one would look at cycles of N length (number of nodes), that'd be equivalent to the Hamilton-cycle finding problem, which is NP-hard, therefore slow. Another thing to note is that if your graph is dense, you can have exponentially many cycles (even factorially many, like in complete graphs) which would mean that just to put all of them in memory would take a long time.
On the other hand, if you just look for small, defined length cycles, you could find all of them without taking too much time. This is the case in your example. Naively, you could just look at every 2, 3, 4, 5 size combinations of nodes, and check for each whether they make a directed cycle (possibly more of them), this would take O(N5) time complexity. You could improve this approach by looking at just combinations of 5 nodes which make connected subgraph, I propose one such approach:
Similarly to a BFS algorithm, you take a node and put it on a "0th layer", then put it's neighbours on the 1st layer, then put those nodes' neighbours on the 2nd layer, and so on.. Draw the edges. You'll get something like this:
Intuitively, if you do not account for one layer inbetween edges (we'll talk about them later), then the only way we get cycles is if we follow a "downward" path from a node then jump back from a lower level to a higher level at least once.
Already we could improve a lot on the runtime by just checking node combinations where the nodes are only 1/2/3/4 layers away from each other.
But cycles with these jumpbacks could be very easily detected, improving runtime: for the case e.g. looking at 5-length cycles, these cycles in our representation are either "go 4 times down, then jump back to the beginning", or "go 3 times down, and jump up two times: once one layer, once two layers" cycles, there are no other possibilities. Going through neighboring nodes and checking for layer number differences helps us identify the cycles easier.
But inbetween-layer edges increase the complexity, already for the case of 5-length cycles. (In 2, 3, 4 length cycles they still are fairly easily manageable.) I would probably just deal separately with edges and do something brute force (e.g., we could try looking through all 3-node combinations from close layers to make a 5-length cycle with the two nodes of an inbetween-layer edge).
© 2022 - 2025 — McMap. All rights reserved.