Is there a way to obtain all cycles of a directed graph similar to all_simple_cycles() in sage?
4 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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
0 Kommentare
Antworten (1)
Christine Tobler
am 29 Mär. 2019
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.
6 Kommentare
NA
am 6 Jan. 2020
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
am 6 Jan. 2020
Siehe auch
Kategorien
Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!