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

8 次查看（过去 30 天）

Hao Sun 2019-3-29

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453193-is-there-a-way-to-obtain-all-cycles-of-a-directed-graph-similar-to-all_simple_cycles-in-sage

评论： NA 2020-1-6

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Christine Tobler 2019-3-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453193-is-there-a-way-to-obtain-all-cycles-of-a-directed-graph-similar-to-all_simple_cycles-in-sage#answer_368115

findcycles.m

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 个评论
显示 4更早的评论隐藏 4更早的评论

NA 2020-1-6

在 MATLAB Online 中打开

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?