Is there a way to obtain all cycles of a directed graph similar to all_simple_cycles() in sage?

Is there a way to obtain all cycles of a directed graph similar to all_simple_cycles() in sage?

http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/digraph.html?highlight=all_simple_cycles#sage.graphs.digraph.DiGraph.all_simple_cycles

Answer 1

[Christine Tobler]

There's no direct function, but I've attached a solution I've quickly put together just now. This recursively iterates through all possible paths, so it will not be fast for large or dense graphs. I tested it for graph(ones(4)), and it gave me the expected cycles.

Note that the output here can become quite long - the number of cycles in a complete graph grows faster than exponentially.

[NA]

I have a question about this code, Is this code is Depth first search algorithm?

[Christine Tobler]

It's similar to depth-first search, but depth-first search only visits every edge once, while this algorithm could visit each edge many times.

This is necessary because the number of all cycles can potentially grow more than exponentially with the number of nodes in a graph. Think of a complete graph: Every possible permutation of the nodes is a valid cycle, and every permutation of a subset of the nodes is also a valid cycle. The algorithm that returns all these cycles must have the same or higher complexity.

[NA]

Is there any way to improve this code?

I attached the data of edge. I tried to use your code for this graph.

But after 4 days of running code still have not get any result.

[Christine Tobler]

Is your input a digraph? In that case, it has no cycles at all (call isdag(g) to verify that). This can be checked in advance of calling findcycles.

I would not expect findcycles to work well for graphs with more than 8 nodes in general (a fully connected graph with 9 nodes took 21s just now). It may work better for some graphs with very few edges, but it's hard to tell when this will be the case.

It's possible to compute a Cycle basis very efficiently (here's a MATLAB Answers post with some code to do that). This should take under a second to compute, but only gives you a basis of all cycles in your graph, not every cycle. Every cycle in the graph can be constructed by combining the cycles in the cycle basis.

While there could be some improvements for finding all cycles, I'm afraid the computational complexity is just too high to work out unless the graph is very small.

[NA]

My graph is not a directed graph. I attached an edge data.

I only want to find cycles that starts from node 1. So, I removed 'for loop' from your code.

% for ii=1:numnodes(g)
%     % Find all cycles starting with node ii, which only contain nodes
%     % with indices >= ii.
%     c = findcycleRecursive(ii, g, c, ii);
% end

c = findcycleRecursive(1, g, c, 1);

Simulation I thought this change gives me less cycles. But

If I comment 'for loop' it gives me 52584 cycles.

If I kept 'for loop' it gives me 17674 cycles.

So, how I can find less cycles?

[NA]

How can I change findcycles.m to depth-first search, (only visits every edge once)?