Is there a way to obtain all cycles of a directed graph similar to all_simple_cycles() in sage?
4 ビュー (過去 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?
NA
2020 年 1 月 6 日
参考
カテゴリ
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!