MATLAB: Find cycles in an undirected graph

connected pointsgraph theorypolygonsset of pointsspatialgraph2d

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 is the Sergii Iglin 's idea, that I found in https://ch.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox
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 is the Christine Tobler 's idea that I found in https://ch.mathworks.com/matlabcentral/answers/353565-are-there-matlab-codes-to-compute-cycle-spaces-of-graphs
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
https://ch.mathworks.com/matlabcentral/answers/425321-find-cycle-in-array
are not working for my case…
Any further idea / suggestion ?
Thanks a lot!

Best 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
Related Question