finding cycles in directed graph

10 次查看（过去 30 天）

Josué Ortega 2020-4-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/515624-finding-cycles-in-directed-graph

评论： Emanuele Giacomuzzo 2021-3-9

I am creating a random adjacency matrix for a directed graph and I want to find the cycles. I am using the findcycles function that I found online

I have the following code

rand('seed',1)
n=5;
A=zeros(5);
x=zeros(1,n);
for i=1:n
    A(:,i)=randperm(n);
end
A
adj=zeros(n);
for i=1:n
    adj(i,A(1,i))=1;
end
   view(biograph(adj))
   findcycles(adj)

But I get the following error, any ideas?

Warning: Self connecting nodes are not allowed, ignoring the diagonal of CM. 
> In biograph (line 160)
  In tops (line 13) 
Error: File: findcycles.m Line: 5 Column: 10
Invalid expression. Check for missing multiplication operator, missing or unbalanced delimiters, or other syntax error. To construct matrices, use
brackets instead of parentheses.
Error in tops (line 14)
   findcycles(adj)

7 个评论
显示 5更早的评论隐藏 5更早的评论

Christine Tobler 2020-4-7

在 MATLAB Online 中打开

Here's a way that you can change the function to return all the cycles into a cell array:

function pathCell = findcyclesMod(G)
numNodes = size(G,1); 
pathCell = {};
for n = 1:numNodes
   [D,P]=graphtraverse(G,n);
   for d = D
       if G(d,n)
           pathCell{end+1} = graphpred2path(P,d);
       end
   end
   G(n,:)=0; 
end

A cell array is a datastructure where every element can contain an array of varying size, so each element of pathCell contains a vector that represents one path.

Looking at the findcycles function, it seems this won't find all the cycles. In an example:

Here findcycles returns the following cycles:

   5
   5     2     3
   3     5
   3     5     6     4
   5     6
   5     6     4
   6

This is not showing the possible cycle [2 6 4], for example.

Would you mind telling a bit more about what your requirements are for findcycles? Do you need all cycles in a graph, or just a cycle for any node that contains a cycle? Many of the possible cycles can be just recombinations of other existing cycles (for example in a complete graph (a graph where every pair of two nodes is connected by an edge), any list of nodes would be a cycle, leading to a very long list even for small graphs.

Emanuele Giacomuzzo 2021-3-7

adjacency_matrix.txt

I'm trying to make this code work for myself, but I have problems in running the graphtraverse function. The graph I am working with is - according to MATLAB - a non-sparse one. So the function won't work on it. Is there any function like graphtraverse that works on non-sparse matrices?

The attached file is my non-sparse adjacency matrix.

Cheers!

Emanuele Giacomuzzo 2021-3-9