MATLAB Answers

Find cycles in an undirected graph

184 views (last 30 days)
Sim
Sim on 7 Oct 2019
Edited: Cheng Ting Tsai on 8 Jun 2020
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!

  5 Comments

Show 2 older comments
Sim
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
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...
Can Chen
Can Chen on 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?

Sign in to comment.

Accepted Answer

Matt J
Matt J on 8 Oct 2019
Edited: Matt J on 8 Oct 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

  47 Comments

Cheng Ting Tsai
Cheng Ting Tsai on 20 Apr 2020
Hi, Matt~
Thanks for your attention on my case and questions.
I'll try your new version code as soon as possible.
Cheng Ting Tsai
Cheng Ting Tsai on 4 Jun 2020
Hi Matt~
Finally, I complete my real case by using your newest version "spatialgraph2D.m" on MathWorks file exchange! Really really thanks a lot. I will cite you in my research. Cheers!
By the way, there is a modest suggestion for someone who want to use "spatialgraph2D.m" for other purposes: any node in your graph needs to be linked by at least one edge!!
Take a simple case (Figure 1.) as an example:
there are 10 nodes (blue) in my graph, but there are only 7 nodes which are linked by edges. In other words, I have 3 nodes without linking as "marginal men". Now, code "spatialgraph2D.m" would not recognize these 3 marginal men as "nodes". However, because of the ID number (blue) of the last nodes is "10", G = graph(s,t) would mistankly believed that the total number of nodes is 10 ( is 7 actually). Therefore, the lable (ID number) of my nodes in x=[] and y=[] will get some trouble:
Error using spatialgraph2D (line 45)
Input vectors x and y must have lengths equal to the
number of graph nodes.
Error in loadingFiles_CY_senpai (line 845)
obj=spatialgraph2D(G,x,y);
In other words, I will get an error if my graph have nodes without linking. Therefore, renewing ID numbers (red) in my case is necessary. Hope this will help someone who is confused like me.Thanks!
[Figure 1.]
Matt J
Matt J on 5 Jun 2020
By the way, there is a modest suggestion for someone who want to use "spatialgraph2D.m" for other purposes: any node in your graph needs to be linked by at least one edge!!
No, that is not correct. Below is an example to show that spatialgraph2D will work for graphs with isolated nodes, like in the attached example.mat.
load example
hg=plot(G);
obj=spatialgraph2D(G,hg.XData,hg.YData);
mosaic(obj)

Sign in to comment.

More Answers (1)

darova
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

Show 2 older comments
darova
darova on 8 Oct 2019
Here is an example. Any ideas how to remove branches?
See the attached script
Sim
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.

Community Treasure Hunt

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

Start Hunting!