Find cycles in an undirected graph

23 Ansichten (letzte 30 Tage)
Sim
Sim am 7 Okt. 2019
Kommentiert: Sim am 16 Jun. 2022
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')
% Remove "branches"
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.
% Sergii Iglin
% https://iglin.org/All/GrMatlab/grCycleBasis.html
E = table2array(G.Edges);
Output_SI = grCycleBasis(E);
% [my part] From the Sergii Iglin's output to cycles nodes
for i = 1 : size(Output_SI,2)
w = [];
u = E(find(Output_SI(:,i)),:); % edges list
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
% Sergii Iglin's results
>> 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.
% Christine Tobler
% https://ch.mathworks.com/matlabcentral/answers/353565-are-there-matlab-codes-to-compute-cycle-spaces-of-graphs
t = minspantree(G, 'Type', 'forest');
% highlight(h,t)
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
% Christine Tobler's results
>> 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!
  6 Kommentare
Can Chen
Can Chen am 5 Jun. 2020
Hi Sim, 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?
Sim
Sim am 27 Dez. 2020
Hi Can, sorry I have just noticed your post! I am available for answering your questions. How can I contact you directly?

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Matt J
Matt J am 8 Okt. 2019
Bearbeitet: Matt J am 8 Okt. 2019
Because this sounds like a generally useful thing, I cooked up the attached polyregions class to do the partitioning that you described. It uses graph theoretic functions only.
Here is its application to the data example that you provided. Each partitioned polygon is contained in the polyshape array, pgon.
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];
obj=polyregions(G,x,y);
pgon=polyshape(obj);
plot(obj);
hold on
plot(pgon);
hold off
  43 Kommentare
Matt J
Matt J am 27 Dez. 2020
Bearbeitet: Matt J am 27 Dez. 2020
Hi JUN WANG,
In 3D, what would be the criterion be for deciding which vertices form a tile? In 2D, a polygon is a tile if it doesn't overlap with any other polygons in the graph. How would that generalize to 3D?
Also, in your example, there are only 23 vertices, so it is not clear how you could have a polygon with vertex indices 1-12-35-33-25.
NA
NA am 28 Feb. 2022
Bearbeitet: NA am 28 Feb. 2022
What is the time complexity of this algorithm?

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (2)

darova
darova am 7 Okt. 2019
Just use for loop and cells since you already know indices of each polygon
s = [1 1 1 2 3 3 4 4 5 6 6 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];
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];
ind = {{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}};
cla
% plot([x(s);x(t)],[y(s);y(t)],'.b')
hold on
for i = 1:length(ind)
ix = cell2mat(ind{i});
plot(x(ix),y(ix),'color',rand(1,3))
end
hold off
axis equal
  5 Kommentare
darova
darova am 8 Okt. 2019
Here is an example. Any ideas how to remove branches?
See the attached script
Sim
Sim am 9 Okt. 2019
Bearbeitet: Sim am 9 Okt. 2019
Hi Darova, to remove branches I used this:
% Remove branches
xy = [x' y'];
while ~isempty(find(degree(G)==1))
degreeone = find(degree(G)==1);
G = rmnode(G,degreeone);
xy(degreeone,:) = [];
end
About your idea/proposal, it looks cool and promising! Also, a nice animation!
However, is there any way to extrapolate the nodes composing each "cycle"/"polygon" that you were able to isolate ?
Thanks a lot for your efforts!

Melden Sie sich an, um zu kommentieren.


Sim
Sim am 15 Jun. 2022
Bearbeitet: Sim am 15 Jun. 2022
Hey @Matt J! hope this message finds you well! I am back to my post after a while :-)
... I have a quite silly question..... I was trying to use your function in a loop for, in order to get automatically the number of polygons / cycles.... However, sometimes, it happens that there are not polygons / cycles (i.e. there are only tree-like graphs) to detect, as in this example, which returns an error...
% (1) use the function "spatialgraph2D"
>> obj = spatialgraph2D(SG, SG.Nodes.X, SG.Nodes.Y)
obj =
spatialgraph2D with properties:
G: [1×1 graph]
x: [12×1 double]
y: [12×1 double]
labels: [1 2 3 4 5 6 7 8 9 10 11 12]
pruneType: 'basic'
% (2) plot the graph
>> plot(obj)
% (3) calculate "polyshape" of "obj"
>> pgon = polyshape(obj)
Index in position 1 exceeds array bounds.
Error in spatialgraph2D (line 70)
obj.tol=min(D(2,:))/1000;
Error in spatialgraph2D/pruneBranches (line 253)
obj=spatialgraph2D(Gp,xp,yp,lp);
Error in spatialgraph2D/polyshape (line 98)
obj=pruneBranches(obj);
Is there a way to workaround this error in spatialgraph2D ?
Maybe just giving an empty "pgon" or something, but not an error (otherwise the loop for breaks..) ?
All the best,
Sim
P.S.: Just for a sake of completness.... here following the edge list of my example:
>> obj.G.Edges(:,1)
ans =
11×1 table
EndNodes
________
1 6
2 3
2 9
3 8
4 7
5 6
5 7
7 11
9 10
10 11
11 12
  7 Kommentare
Sim
Sim am 16 Jun. 2022
Bearbeitet: Sim am 16 Jun. 2022
Yes, I do the same, copy to the clipboard, delete from the discussion panel and paste it there with my modifications... but I think that the matlab staff already knows it, and I am confident they will fix it soon :-)
Sim
Sim am 16 Jun. 2022
@Matt J, any idea on how to solve this small issue ? :)

Melden Sie sich an, um zu kommentieren.

Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by