Is there a way to obtain all cycles of a directed graph similar to all_simple_cycles() in sage?
6 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(1 个)
Christine Tobler
2019-3-29
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 个评论
NA
2020-1-6
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?
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!