Hi, I need to find cycles in a graph, exactly as it was asked here (and apparently without fully clear/working solutions!):
Here my example/code:
clear all; clc; close all;
figure('Color',[1 1 1]);
s = [1 1 1 2 3 3 4 4 5 6 7 6 8 9 10 10 12 12 13 14 15 16 17 17 18 19 20 21 20 25];
t = [2 8 18 3 4 23 5 21 6 7 8 11 9 10 11 12 14 13 15 18 16 17 18 25 19 20 1 22 24 26];
G = graph(s,t);
x = [0.5 0 0 0 0.5 1 1.5 2 3 3 3 5.5 6 4 6 6 4 3 2 0.5 -1 -2 -1 1.5 4.5 4.5];
y = [0 0.5 1 1.5 2 2 1.5 1 1 1.5 2 1 0.5 0.5 0 -1 -1 -0.5 -1 -1 1 0.5 0.5 -0.5 -0.5 0];
h = plot(G,'XData',x,'YData',y,'linewidth',2,'MarkerSize',7);
nl = h.NodeLabel;
h.NodeLabel = '';
xd = get(h, 'XData');
yd = get(h, 'YData');
text(xd, yd, nl, 'FontSize',17, 'FontWeight','bold', ...
'HorizontalAlignment','left', 'VerticalAlignment','top')
set(gca,'Fontsize',15,'FontWeight','Bold','LineWidth',2, 'box','on')
xy = [x' y'];
while ~isempty(find(degree(G)==1))
degreeone = find(degree(G)==1);
G = rmnode(G,degreeone);
xy(degreeone,:) = [];
end
Here the corresponding Figure (after removal of "branches"):
My goal would be to find the following 5 cycles as output (i.e. lists of nodes composing each cycle):
- 1-2-3-4-5-6-7-8-1
- 6-7-8-9-10-11-6
- 1-8-9-10-12-14-18-1
- 1-18-19-20-1
- 12-13-15-16-17-18-14-12
Note 1:
This method is partially working for my purposes.
Unfortunately, the 2nd and 4th cycles are not what I needed/expected.
E = table2array(G.Edges);
Output_SI = grCycleBasis(E);
for i = 1 : size(Output_SI,2)
w = [];
u = E(find(Output_SI(:,i)),:);
w(1) = u(1,1);
w(2) = u(1,2);
u(1,:) = [];
j = 2;
while ~isempty(u)
[ind,~] = find(u==w(j));
[~,ind2] = ismember(u, u(ind,:), 'rows');
g = u( ind2==1 ,:) ~= w(j);
w(j+1) = u( ind2==1 , g);
u( ind2==1 ,:) = [];
j = j + 1;
end
cycles_SI{i} = w;
end
>> cycles_SI{:}
1 2 3 4 5 6 7 8 1
1 2 3 4 5 6 11 10 9 8 1
1 8 9 10 12 14 18 1
1 8 9 10 12 13 15 16 17 18 1
1 18 19 20 1
Note 2:
This method is partially working for my purposes.
Unfortunately, the 2nd and 4th cycles are not what I needed/expected.
t = minspantree(G, 'Type', 'forest');
nonTreeEdges = setdiff(G.Edges.EndNodes, t.Edges.EndNodes, 'rows');
cycles_CT = cell(size(nonTreeEdges, 1), 1);
for i = 1 : length(cycles_CT)
src = nonTreeEdges(i, 1);
tgt = nonTreeEdges(i, 2);
cycles_CT{i} = [tgt shortestpath(t, src, tgt)];
end
>> cycles_CT{:}
8 7 6 5 4 3 2 1 8
11 10 9 8 1 2 3 4 5 6 11
18 14 12 10 9 8 1 18
18 17 16 15 13 12 10 9 8 1 18
20 19 18 1 20
Note 3:
Methods from Sergii Iglin and Christine Tobler give the same result!
Note 4:
The ideas / FileExchange submissions
- Count all cycles in simple undirected graph version 1.2.0.0 (5.43 KB) by Jeff Howbert
- Count Loops in a Graph version 1.1.0.0 (167 KB) by Joseph Kirk
kindly suggested here
are not working for my case...
Any further idea / suggestion ?
Thanks a lot!
4 Comments
Steven Lord (view profile)
Direct link to this comment
https://ch.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_753862
Matt J (view profile)
Direct link to this comment
https://ch.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_753953
Sim (view profile)
Direct link to this comment
https://in.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_754348
Sim (view profile)
Direct link to this comment
https://ch.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_754353
Sign in to comment.