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 17 Oct 2019

Ops...thanks... Please see attached the file

Debug_Data.mat

(and sorry for my late reply)

Matt J
on 21 Oct 2019 at 23:49

Using our jigsaw class, we can plot the sub-section of the graph that is triggering the warning,

load Debug_Data

N=numel(nodenums);

s=1:N;

t=circshift(s,-1);

obj=jigsaw(graph(s,t), vertices(:,1), vertices(:,2),nodenums);

obj.plot

Somewhere in your graph, you have the following, which does indeed show an intersection of two node connections.

The algorithm I use to divide the graph into sub-polygons assumes no intersections. In general, I wouldn't know how to predict behavior if you allow them.

Assuming cross-overs/intersections are supposed to be forbidden, then it is best to use,

polyshape(______,'Simplify',true);

in the code, because that will alert you that a cross-over is present when it shouldn't be.

Sim
on 22 Oct 2019 at 12:12

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!

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://in.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_753862

## Matt J (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_753953

## Sim (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_754348

## Sim (view profile)

## Direct link to this comment

https://in.mathworks.com/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#comment_754353

Sign in to comment.