find cycle in array

I have a M M=[1,2 ;1,5; 2,4;2,5;4,5; 4,9;5,6;6,11;9,10;10,11] I want to find a loop in this array. I want this answer A={[1,2,5],[2,4,5],[4,5,6,9,10,11]}

[Guillaume]

I'm assuming that your M represents the edges of a graph. Don't you think it's essential information that you should have mentioned?

You can plot your graph with:

M = [1,2 ;1,5; 2,4;2,5;4,5; 4,9;5,6;6,11;9,10;10,11]
G = graph(M(:, 1), M(:, 2));
plot(G)

which outputs

Why are loops

[1 2 4 5]
[2 5 6 11 10 9 4]
etc.

not valid outputs?

[NA]

I know this code. As you see the graph, [1,2,5] become one cycle, [2,4,5] is another cycle. I want this answer A={[1,2,5],[2,4,5],[4,5,6,9,10,11]}

[Guillaume]

Yes, but [1 2 4 5] is also a loop. So is [1 2 4 9 10 11 6 5]. Why are these not included in your list?

[Sim]

Hi Naime! I have your exact problem... Did you find any solution to share ?

[Guillaume]

@simone, have you looked at the answers provided? In particular, I linked to two fileexchange submissions in my answer.

[Sim]

@Guillaume

Yes, thank you.. I tried what you suggested:

[1] Count all cycles in simple undirected graph version 1.2.0.0 (5.43 KB) by Jeff Howbert

[2] Count Loops in a Graph version 1.1.0.0 (167 KB) by Joseph Kirk

Unfortunately, both solutions [1] and [2] were not working for my case... but I understood more about the problem and the way to describe it! Thanks a lot, very helpful FileExchange submissions!

Just for information, the solution I was looking for was kindly provided by Matt J here:

https://ch.mathworks.com/matlabcentral/answers/483968-find-cycles-in-undirected-graph?s_tid=ab_old_mlc_ans_email_view#answer_395354

[Can Chen]

Hi Na, I work at MathWorks on graphs. If you have a few minutes, I would very much appreciate hearing more about your workflow using cycles. Would you please contact me directly?

Answer 1

[Matt J]

This can be done using the spatialgraph2D submission on the File Exchange,

https://www.mathworks.com/matlabcentral/fileexchange/73630-spatialgraph2d

M = [1,2 ;1,5; 2,4;2,5;4,5; 4,9;5,6;6,11;9,10;10,11]
G = graph(M(:, 1), M(:, 2));
hg=plot(G);

obj=spatialgraph2D(G,hg.XData,hg.YData);

[~,A]=obj.polyshape;

>> A{:}

ans =

     1     5     2


ans =

     2     5     4


ans =

     4     5     6    11    10     9

 >> obj.mosaic

Answer 2

[KSSV]

M=[1,2 ;1,5; 2,4;2,5;4,5; 4,9;5,6;6,11;9,10;10,11] ;
A={[1,2,5],[2,4,5],[4,5,6,9,10,11]} ;

[c,ia,ib] = unique(M(:,1)) ;
N = length(c) ;
B = cell(N,1) ; 
for i = 1:length(c)
    T = M(ib==i,:) ;
    B{i} = unique(T(:)) ;
end

Answer 3

[Guillaume]

There are no built-in algorithms in matlab to find cycles in graphs (undirected or directed). You'll either have to write your own, eg. using DFS or BFS (both DFS and BFS are implemented in matlab) or some other algorithm that you can find using your favorite search engine, or you'll have to use one of the submissions in the FileExchange ( [1], [2], and probably more)