Asked by Sim
on 7 Oct 2019

Hi, I need to find cycles in a graph, exactly as it was asked here (and apparently without fully clear/working solutions!):

- find cycle in array https://ch.mathworks.com/matlabcentral/answers/425321-find-cycle-in-array
- find a cycles in undirected graph https://ch.mathworks.com/matlabcentral/answers/421435-find-a-cycles-in-undirected-graph

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

are not working for my case...

Any further idea / suggestion ?

Thanks a lot!

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

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

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.

Opportunities for recent engineering grads.

Apply Today
## 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.