MATLAB Answers

Sim
1

Find cycles in an undirected graph

Asked by Sim
on 7 Oct 2019
Latest activity Commented on by Sim
about 7 hours ago
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!

  4 Comments

Show 1 older comment
Matt J
on 8 Oct 2019
Because the ulterior motive is to partition the graph into non-overlapping polygons.
Sim
on 9 Oct 2019
I found also this idea/method "Polygons From Set of Line segments", explained in
and based on Ferreira A., Fonseca M.J., Jorge J.A. (2003) Polygon detection from a set of lines
The basic idea can be summarised as: "Finding small polygons is the same as searching for a Minimum Cycle Basis"
Screen Shot 2019-10-09 at 2.40.33 PM.png
% Pseudocode of the algorithm
% Minimum basis cycle [3]
% Initialize empty sets F,P
% P=All-Pairs-Shortest-Paths(G)
% for each v ∈ V
% for each (x,y) ∈ E
% if Px,v ∩ Pv,y = {v}
% C=Px,v ∪ Pv,y ∪ (x,y)
% add C to F
% Order-By-Length
% return Select-Cycles(F)
% Polygons from cycles [4]
% Initialize empty set P
% for each cycle C in F
% p=new polygon
% for each vertex v ∈ V
% add vertex v to p
% add polygon p to set P
% return P
Sim
on 9 Oct 2019
@Steven Lord : Kindly Matt J gave the answer... In this moment, I would just need to know the "cycles" corresponding to the polygons which compose my network...

Sign in to comment.

2 Answers

Answer by Matt J
on 8 Oct 2019
Edited by Matt J
on 8 Oct 2019
 Accepted Answer

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

  31 Comments

Sim
on 22 Oct 2019
Thanks a lot Matt J for this clever analysis!
You are rigth about the usage of
polyshape(______,'Simplify',true);
....now I need to think a bit about how to handle with those intersections... Btw, jigsaw class is an excellent tool, and I am really grateful for your help!
Matt J
15 minutes ago
I finally got around to posting it on the FEX
though I renamed the class yet again to spatialgraph2D. At some point, I'll get around to expanding its capabilities.
Sim
about 7 hours ago
Cool!! I am sure it will be very useful to many people :) ..Hopefully I will cite you soon :)

Sign in to comment.


Answer by darova
on 7 Oct 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 Comments

Sim
on 7 Oct 2019
Thanks Darova!
darova
on 8 Oct 2019
Here is an example. Any ideas how to remove branches?
See the attached script
Sim
on 9 Oct 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!

Sign in to comment.