Find cycles in an undirected graph

Question

Sim 2019-10-7

3
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph

评论： Sim 2022-6-16

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

https://ch.mathworks.com/matlabcentral/answers/425321-find-cycle-in-array

are not working for my case...

Any further idea / suggestion ?

Thanks a lot!

6 个评论
显示 4更早的评论隐藏 4更早的评论

Can Chen 2020-6-5

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?

Sim 2020-12-27

Hi Can, sorry I have just noticed your post! I am available for answering your questions. How can I contact you directly?

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2019-10-8

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#answer_395354

编辑：Matt J 2019-10-8

在 MATLAB Online 中打开

polyregions.m

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

43 个评论
显示 41更早的评论隐藏 41更早的评论

Sim 2019-10-10

在 MATLAB Online 中打开

Hi Matt, a question about the removal of "branches" in your code:

function obj = prune(obj)
%Remove dangling branches

....In case I have a small loop inside one of the dangling "branches" that we need to remove, like the loop 25-26-27, would you have some suggestion to workaround it ?

The code corresponding to that Figure, with the looped-branch is the following:

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 26 27 27];
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 27 25 28];
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 5 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 0 0.5];
xy = [x' y']
h = plot(G,'XData',xy(:,1),'YData',xy(:,2),'linewidth',2,'MarkerSize',7);
axis([-3 7 -1.5 2.5]);
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')

If I apply your code...

% Matt J Polygons/Cycles
obj=polyregions(G,x,y);
pgon=polyshape(obj);
plot(obj);
hold on
plot(pgon);
hold off
[pgon,nodeIndices]=polyshape(obj);
nodeIndices{:}

Inside the function

function [P,E]=polyshortest(obj,arg1,arg2)

I get this error:

nodeA =
    17
nodeB =
    21
P =
     []
Index exceeds array bounds.
Error in polyregions/polyshortest (line 90)
            E=G.findedge(P,[P(2:end),P(1)])
Error in polyregions/polyshape (line 118)
                [P,E]=polyshortest(obj,E0); % F4              
Error in GraphCycles (line 22)
pgon=polyshape(obj);

Thanks a lot!

Sim 2019-10-11

编辑：Sim 2019-10-11

在 MATLAB Online 中打开

Hi Matt, your solution perfectly works on this network..! Thanks a lot! :)

...However, when I try to apply this revised prune() method to my real case (a larger network), I get this error:

Index exceeds array bounds.
Error in polyregions (line 15)
              w=sqrt((x(s)-x(t)).^2 + (y(s)-y(t)).^2);
Error in polyregions/prune (line 44)
            obj=polyregions(graph(sk,tk),xp,yp);
Error in polyregions/polyshape (line 85)
            obj=prune(obj);
Error in floods (line 98)
pgon=polyshape(obj);

At a first glance, it looks like that the components of the "w" array (i.e. x(s), x(t), y(s), y(t)) cannot be computed due to

Index exceeds array bounds.

Trying to understand the reasons of this error, I have noticed that the x and y arrays, which contain the nodes coordinates, reduce their sizes when the function prune() is called. This occurs via the xp and yp arrays, that are initialised as x and y arrays, at the beginnning of the prune() function. Indeed, when we remove the "dangling branches", the xp and yp arrays are reduced:

xp(tips)=[];
yp(tips)=[];

The xp and yp arrays are then "exported" to the new "obj", at the end of the prune() function

obj=polyregions(graph(sk,tk),xp,yp);

Therefore, in the following/remaining part of the code, the updated graph (without dangling branches) contains the reduced x and y arrays.

Now, if we change the last line of the prune() function as

obj=polyregions(graph(sk,tk),obj.x,obj.y);

where obj.x and obj.y have the original x and y arrays, the code runs further, and almost at the very end, where pgon is calculated

U=union(pgon) %#ok<*LTARG>
if ~U.NumHoles, return; end
hgon=holes(U)
pgon=[pgon,hgon]
for i=1:numel(hgon)
    [~,P]=ismember(hgon(i).Vertices,[x(:),y(:)],'rows')
    nodeIndices{end+1}=P.' %#ok<*AGROW>
end

....and exactly there I get this error:

U = 
  polyshape with properties:
      Vertices: [349×2 double]
    NumRegions: 1
      NumHoles: 15
hgon = 
  15×1 polyshape array with properties:
    Vertices
    NumRegions
    NumHoles
Error using horzcat
Dimensions of arrays being concatenated are not consistent.
Error in polyregions/polyshape (line 117)
            pgon=[pgon,hgon]
Error in floods (line 98)
pgon=polyshape(obj);   

Am I doing something wrong?

Thanks a lot!

Matt J 2019-10-11

编辑：Matt J 2019-10-11

在 MATLAB Online 中打开

jigsaw.m

I think the attached version (rename to jigsaw.m) may fix it, but it would help to have your G,x,y attached in a .mat file for testing purposes. In the meantime, the test below verifies that scrambling the order of the node labeling doesn't interfere with things.

L=randperm(28);
Li(L)=1:28;
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 26 27 27];
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 27 25 28];
G = graph(L(s),L(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 5 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 0 0.5]);
x=x(Li); y=y(Li);
obj=jigsaw(G,x,y);
plot(obj)
[pgon,cycles]=polyshape(obj);
hold on;
plot(pgon);
hold off

>> cycles{:}
ans =
     3    16    12    19    20    17    11
ans =
     4    26     5    14    28    15    10    18
ans =
     5    14    28    22     8    23
ans =
     8    22    28    15    20    19    12
ans =
    13    25    20    15

Sim 2019-10-11

在 MATLAB Online 中打开

Hi Matt, I really really appreciate your huge help!!

...I sent you a private message/email since my data are confidential.. If you have not receive it, I can re-send it... :)

In general, is MATLAB "preserving" confidential data/material if we exchange data using this official channel (with private message/email) ?!

....I think we are getting very close to the perfect code for my case / real network... I mean, your code "somehow" works for my real network only if I comment "pgon" at the end of your code, in order to avoid the previous error

            U=union(pgon); %#ok<*LTARG>
            if ~U.NumHoles, return; end
            
            hgon=holes(U);
            % pgon=[pgon,hgon]
            
            for i=1:numel(hgon)
             [~,P]=ismember(hgon(i).Vertices,[x(:),y(:)],'rows');
             nodeIndices{end+1}=P.' %#ok<*AGROW>
            end

...this is the previous error....

Error using horzcat
Dimensions of arrays being concatenated are not consistent.
Error in polyregions/polyshape (line 117)
            pgon=[pgon,hgon]

.....but doing this, some polygons are not "detected".............. Btw, very thankful for your huge support!! Really grateful!

Sim 2019-10-11

编辑：Sim 2019-10-14

在 MATLAB Online 中打开

Perfect! Thank you very much!

I replaced

pgon=[pgon,hgon]

with

pgon=[pgon(:).',hgon(:).'];

In addition, I replaced this

nodeIndices{end+1}=lp(P.'); %#ok<*AGROW>

with

nodeIndices{end+1}=P.'; %#ok<*AGROW>

And it is now working for my real network!

Please see following the exact code I used, and that you kindly provided...

s = [ ... ];
t = [ ... ];
G = graph(s,t);
x = [ ... ];
y = [ ... ];
% Matt J Polygons/Cycles
obj=jigsaw(G,x,y);
plot(obj)
[pgon,cycles]=polyshape(obj)
hold on;
plot(pgon);
hold off

....together with the dimensions of my graph G, the final result and the elapsed time...

G = 
  graph with properties:
    Edges: [6038×1 table]
    Nodes: [3111×0 table]
pgon = 
  1×2495 polyshape array with properties:
    Vertices
    NumRegions
    NumHoles
cycles =
  1×2495 cell array
  Columns 1 through 7
    {1×3 double}    {1×23 double}   etc.......
Elapsed time is 18.913817 seconds.

If possible, I would suggest to create a "MATLAB File Exchange"....maybe with a Reference about the method you used (did you use any method from the Literature?) I partially understood what you did, but not completely... I would be curious to know if this is somehow related/connected to the "Minimum Cycle Basis" of Graph Theory... How to cite your code in research papers ? Thanks a lot for your precious help!

Sim 2019-10-12

编辑：Sim 2019-10-14

在 MATLAB Online 中打开

Thanks... By using this line of code

nodeIndices{end+1}=lp(P.');

I was getting the following error

Array indices must be positive integers or logical values.
Error in jigsaw/polyshape (line 137)
             nodeIndices{end+1}=lp(P.');
Error in program (line 94)
[pgon,cycles]=polyshape(obj)

....Then, I checked the previous line

[~,P]=ismember(hgon(i).Vertices,[x(:),y(:)],'rows');

and the three quantites inside it, i.e.

P
hgon(i).Vertices
[x(:),y(:)]

As example, I got something like this:

P =
         188
        1873
         191
           0
           0
        1902
         245
         281
           0
           0
           0
         177
         178
hgon(1).Vertices = 
 
                719206.761                262076.829
                720011.091                260159.216
                720306.696                259519.618
           720812.14899999           258050.23099999
           722903.21299998                256225.431
                726046.209                256652.186
                727673.923                255337.524
                732122.269                253113.636
           736764.74299995           256159.99799996
           728781.39999995           267902.73300001
                725492.548           269719.18599999
                722128.621                271490.111
                723849.229                268561.544
[x(:),y(:)] = 
                704726.255                    281756
                711700.953                265115.835
                712542.533                264359.824
                713410.689                263107.846
                713769.936                 262368.76
                714125.573                261718.406
                715803.539                261306.605
                717089.203                260113.503
                717635.691                259625.701
                694183.174                 253518.56
                etc...                    etc...

Then, I thought to replace this line

[~,P]=ismember(hgon(i).Vertices,[x(:),y(:)],'rows');

with (ismember with a tolerance)

[~,P]=ismembertol(hgon(i).Vertices,[x(:),y(:)],0.02,'ByRows',true)

and I did not get any error anymore... But I am just wondering why the coordinates of some "vertices" are not perfectly overlapping during the operation of "ismember", since all of those coordinates come from the same initial dataset...

In summary, I modified the very last loop of the code from this

for i=1:numel(hgon)
    [~,P]=ismember(hgon(i).Vertices,[x(:),y(:)],'rows');
    nodeIndices{end+1}=lp(P.'); %#ok<*AGROW>
end

to this:

for i=1:numel(hgon)
    [~,P]=ismembertol(hgon(i).Vertices,[x(:),y(:)],0.02,'ByRows',true)
    nodeIndices{end+1}=lp(P.'); %#ok<*AGROW>
end

and the last error disappeared....However, I am not sure if the usage of "ismembertol" is fully correct, instead of the previous "ismember"

Sim 2019-10-14

编辑：Sim 2019-10-14

在 MATLAB Online 中打开

Thats cool! It looks perfect!

I am trying the newer version of jigsaw.m on my network, by using exactly your commands

% my real network
s = [ ... ];
t = [ ... ];
G = graph(s,t);
x = [ ... ];
y = [ ... ];
% Matt J Polygons/Cycles
obj=jigsaw(G,x,y);
obj.tol
tic;
[pgon,cycles]=polyshape(obj);
toc 
hold on
plot(pgon);
hold off
% my elapsed time is
% Elapsed time is 16.687441 seconds.

..It looks like that all the polygons are well detected and the code is faster, but I have just noticed a couple of things..

my network is squeezed to the right side (right half) of the Figure window (with the previous version of jigsaw.m it did not happen.. previously, it was well centered..)
I get these warnings (repeated many times in the command window.. I dont know why..)...

Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or
unexpected results. Input data has been modified to create a well-defined polyshape. 
Warning: Output contains an empty polyshape due to duplicate vertices, intersections, or other inconsistencies. 
Warning: Boundaries with less than 3 points were removed. 

:-)

Sim 2019-10-14

在 MATLAB Online 中打开

jigsaw.m

Many thanks Matt :) I used what you kindly suggested (something similar)

dbstop in jigsaw if warning

in my list of commands... i.e. in this way...

dbstop in jigsaw if warning
obj=jigsaw(G,x,y);
obj.tol
[pgon,cycles]=polyshape(obj);
plot(obj)
hold on
plot(pgon);
hold off

....and I found out something, that I explaine here below...

Let's start from this warning

Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected
results. Input data has been modified to create a well-defined polyshape. 

which disappeares if, inside the

function [pgon,labelIndices]=polyshape(obj)

I replace this line

pgon(end+1)=polyshape(Vall(P,:),'Simplify',true);

by this one

pgon(end+1)=polyshape(Vall(P,:),'Simplify',false);

In your opinion, is this replacement a problem/issue for the calculation of polygons ?

Note: in general, I can see that the warnings disappear if I use "Simplify, false"

polyshape(..,'Simplify',false);

Let's go now to the "network squeezed towards the right side of the Figure window" and to the other warnings, which occur all together at once, as follows

Warning: Output contains an empty polyshape due to duplicate vertices, intersections, or other inconsistencies. 
Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected
results. Input data has been modified to create a well-defined polyshape. 
Warning: Boundaries with less than 3 points were removed. 

....All these warnings disappear and the picture is restored to the center as previously, if I replace the last loop of the code

for i=1:numel(hgon)
    P= knnsearch(Vall,hgon(i).Vertices); 
    pgon(end+1)=polyshape(Vall(P,:),'Simplify',true);
    labelIndices{end+1}=lp(P.'); %#ok<*AGROW>
end

with that one we used in a previous version of jigsaw.m

pgon=[pgon(:).',hgon(:).'];
for i=1:numel(hgon)
    [~,P]=ismembertol(hgon(i).Vertices,[x(:),y(:)],0.02,'ByRows',true);
    labelIndices{end+1}=lp(P.');
end  

By using the jigsaw.m code with the above mentioned modifications (see attached file too) I checked the "visual results" for both your network and mine.... At a first glance, it looks like that both networks give correct visual results, i.e. all polygons/holes are detected... However, I am aware that "ismembertol" is not the best, while the usage of "knnsearch" is a more robust solution.. but employing "knnsearch", I got many warnings and a squeezed picture which I would not know how to fix for my network/case...

Just for information, please see below the code I used - that you kindly provided - and the corresponding Figure I got with the attached (slightly) modified jigsaw.m

N=1000;
x = randn(N,1)*100;
y = randn(N,1)*100;
DT=delaunayTriangulation(x,y);
EdgeTable=table(DT.edges,'VariableNames',{'EndNodes'});
G=graph(EdgeTable);
% dbstop in jigsaw if warning
obj=jigsaw(G,x,y);
obj.tol
tic;
[pgon,cycles]=polyshape(obj);
plot(obj)
toc %Elapsed time is 16.075788 seconds.
hold on
plot(pgon);
hold off

Screen Shot 2019-10-15 at 12.35.34 AM.png

Sim 2019-10-15

在 MATLAB Online 中打开

Thanks for the reply.. Yes, I might know why I have some intersections or general inconsistencies in my case... I am trying to select and "cut" a small slice of my network to bring it here as sample/example.. but, so far, my attempts to cut and isolate a portion (some polygons) from the rest of my network failed.. In this moment, I am trying to remove all the nodes in the network with

rmnode(G,nodeIDs)

except those ones composing the polygons I would like to bring here... Actually, I also tried the other way round, just picking up the polygons I want, but it looks like MATLAB is reassigning the nodes IDs, messing up the edges... I mean, in my network, a polygon can appear as this chain of nodes IDs: 1032, 1033, 560, 1044, 1045, 1046, 799, etc.. (and the nodes IDs are not always sequential), then, when I make the graph of just those nodes IDs, in that order, MATLAB is reassigning those nodes IDs from 1, to the lenght of such a polygon, as, 1, 2, 18, 6, 7, 8, 13, ...but it assigns the edges in this order: 1, 2, 3, 4, 5, 6, ... therefore the edges are in different order than in my polygon... Well, I will find some solution :)

Matt J 2020-4-14

编辑：Matt J 2020-4-14

在 MATLAB Online 中打开

@Cheng,

The reason for the excluded polygons is that they dangle off the main mosaic by a trivial one-vertex long branch. As mentioned in the Overview of the FEX submission:

"Note that currently, graphs containing multiple connected or disconnected mosaics are outside the scope of what the class code will analyze."

This is the effect you're seeing and is the behavior that the OP wanted (though possibly Sim would not have regarded a 1-vertex long branch as a branch). In any case, you can try replacing the class' prune method with the following experimental alternative. It gives the behavior you're looking for on your two examples, but it needs to go through more extensive beta-testing before I officially release it.

function obj = prune(obj)
%Remove dangling branches
    Gp=obj.G;
    xp=obj.x;
    yp=obj.y;
    lp=obj.labels;
    
    tips=find(degree(Gp)<=1);
    
    while ~isempty(tips)
    
    Gp=rmnode(Gp,tips);
    xp(tips)=[];
    yp(tips)=[];
    lp(tips)=[];
    tips=find(degree(Gp)<=1);
    
    end
    
    obj=spatialgraph2D(Gp,xp,yp,lp);
end

Jun W 2020-12-27

编辑：Jun W 2020-12-27

在 MATLAB Online 中打开

@Matt J

Hi Matt,

Thanks for your awesome work. Could you please do a 3D version ? Here're a testing sample.

vertices = [6805.95000000000,-942.260000000000,497.960000000000;6805.95000000000,942.260000000000,497.960000000000;6862.09000000000,-946.640000000000,548.720000000000;6862.09000000000,946.640000000000,548.720000000000;6875.25000000000,-732.770000000000,503.040000000000;6875.25000000000,732.770000000000,503.040000000000;6903.34000000000,978.720000000000,617.260000000000;6917.19000000000,-1008.46000000000,847.040000000000;6917.19000000000,1008.46000000000,847.040000000000;6930.70000000000,-1007.19000000000,687.570000000000;6930.70000000000,1007.19000000000,687.570000000000;6938.81000000000,-726.260000000000,555.870000000000;6938.81000000000,726.260000000000,555.870000000000;6943.92000000000,-600.580000000000,534.310000000000;6943.92000000000,600.580000000000,534.310000000000;6953.83000000000,-827.580000000000,619.900000000000;6953.83000000000,827.580000000000,619.900000000000;6962.81000000000,-581.470000000000,570.950000000000;6962.81000000000,581.470000000000,570.950000000000;6968.29000000000,-868.050000000000,681.270000000000;6968.54000000000,-618.520000000000,597.530000000000;6968.54000000000,618.520000000000,597.530000000000;6968.55000000000,-508.330000000000,584.870000000000;6968.55000000000,508.330000000000,584.870000000000;6979.30000000000,-535.330000000000,643.970000000000;6979.30000000000,535.330000000000,643.970000000000;6980.01000000000,-650.780000000000,625.820000000000;6980.01000000000,650.780000000000,625.820000000000;6980.04000000000,-706.420000000000,620.380000000000;6980.04000000000,706.420000000000,620.380000000000;6980.28000000000,-761.010000000000,636.010000000000;6980.28000000000,761.010000000000,636.010000000000;6990.21000000000,-631.490000000000,664.060000000000;6990.21000000000,631.490000000000,664.060000000000;6990.67000000000,-776.270000000000,678.530000000000;6990.67000000000,776.270000000000,678.530000000000;7019.02000000000,-544.690000000000,770.930000000000;7019.02000000000,544.690000000000,770.930000000000];
edge_list = [9,11;11,26;26,38;9,38;37,38;25,26;25,37;8,10;8,37;10,25;3,12;3,10;10,20;12,20;1,5;1,3;5,12;31,35;16,31;16,20;20,35;29,31;12,29;12,16;27,31;33,35;27,33;27,29;21,27;12,21;5,6;12,13;6,13;18,21;14,18;12,14;25,33;21,25;18,23;23,25;18,19;15,19;14,15;24,26;23,24;19,22;19,24;22,26;28,34;22,28;26,34;13,22;13,15;28,30;13,30;28,32;34,36;32,36;30,32;17,32;13,17;7,32;11,36;7,11;2,4;2,6;4,13;7,17;4,7];

I tried on spatialgraph2D, but it's missing two pgons, 1-12-35-33-25 and 12-16-20.

Matt J 2020-12-27

编辑：Matt J 2020-12-27

Hi JUN WANG,

In 3D, what would be the criterion be for deciding which vertices form a tile? In 2D, a polygon is a tile if it doesn't overlap with any other polygons in the graph. How would that generalize to 3D?

Also, in your example, there are only 23 vertices, so it is not clear how you could have a polygon with vertex indices 1-12-35-33-25.

NA 2022-2-28

编辑：NA 2022-2-28

What is the time complexity of this algorithm?

请先登录，再进行评论。

Answer 2

darova 2019-10-7

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#answer_395137

在 MATLAB Online 中打开

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 个评论
显示 3更早的评论隐藏 3更早的评论

darova 2019-10-8

Untitled2.m

Here is an example. Any ideas how to remove branches?

See the attached script

Sim 2019-10-9

编辑：Sim 2019-10-9

在 MATLAB Online 中打开

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!

请先登录，再进行评论。

Answer 3

Sim 2022-6-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/483968-find-cycles-in-an-undirected-graph#answer_986290

编辑：Sim 2022-6-15

在 MATLAB Online 中打开

Hey @Matt J! hope this message finds you well! I am back to my post after a while :-)

... I have a quite silly question..... I was trying to use your function in a loop for, in order to get automatically the number of polygons / cycles.... However, sometimes, it happens that there are not polygons / cycles (i.e. there are only tree-like graphs) to detect, as in this example, which returns an error...

% (1) use the function "spatialgraph2D"
>> obj = spatialgraph2D(SG, SG.Nodes.X, SG.Nodes.Y)
obj = 
  spatialgraph2D with properties:
            G: [1×1 graph]
            x: [12×1 double]
            y: [12×1 double]
       labels: [1 2 3 4 5 6 7 8 9 10 11 12]
    pruneType: 'basic'
% (2) plot the graph
>> plot(obj)

% (3) calculate "polyshape" of "obj"
>> pgon = polyshape(obj)
Index in position 1 exceeds array bounds.
Error in spatialgraph2D (line 70)
                obj.tol=min(D(2,:))/1000;
Error in spatialgraph2D/pruneBranches (line 253)
            obj=spatialgraph2D(Gp,xp,yp,lp);
Error in spatialgraph2D/polyshape (line 98)
            obj=pruneBranches(obj);
            

Is there a way to workaround this error in spatialgraph2D ?

Maybe just giving an empty "pgon" or something, but not an error (otherwise the loop for breaks..) ?

All the best,

Sim

P.S.: Just for a sake of completness.... here following the edge list of my example:

>> obj.G.Edges(:,1)
ans =
11×1 table
EndNodes
________
1     6
2     3
2     9
3     8
4     7
5     6
5     7
7    11
9    10
10    11
11    12

7 个评论
显示 5更早的评论隐藏 5更早的评论

Sim 2022-6-16

编辑：Sim 2022-6-16

在 MATLAB Online 中打开

Great!

Your updated function seems to be working fine!

So, if I have understood correctly, you have set "pgon "as zero.. Thank you very much!!

...However, I got another error :-(

Error using spatialgraph2D
Input vectors x and y must have lengths equal to the number of graph nodes.
Error in spatialgraph2D/pruneBranches (line 258)
            obj=spatialgraph2D(Gp,xp,yp,lp);
Error in spatialgraph2D/polyshape (line 98)
            obj=pruneBranches(obj);
Error in Zofingen_temporal_path_activation_connected_components (line 289)
                  pgon=polyshape(obj);

I got it for this case....

>> plot(obj)

And I have also got an error just typing "plot(obj)":

Error using matlab.graphics.chart.primitive.GraphPlot
Expected XData to be an array with number of elements equal to 160.
Error in matlab.graphics.chart.primitive.GraphPlot/set.XData
Error in matlab.graphics.chart.primitive.GraphPlot
Error in graph/plot (line 112)
hObj = matlab.graphics.chart.primitive.GraphPlot('BasicGraph', ...
Error in spatialgraph2D/plot (line 182)
            h = plot(obj.G,'XData',obj.x,'YData',obj.y,'linewidth',2,'MarkerSize',7);

Do you know what I can do to fix it ? :-)

Could be possible that spatialgraph2D does not work when we have isolated nodes ? (just my hypothesis..)

Just for a sake of completeness, here you are (1) the details of "obj" and (2) the corresponding "list of edges" :-)

obj = 
  spatialgraph2D with properties:
            G: [1×1 graph]
            x: [161×1 double]
            y: [161×1 double]
       labels: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 … ]
    pruneType: 'basic'
    
    
>> obj.G
ans = 
  graph with properties:
    Edges: [164×2 table]
    Nodes: [160×0 table]
            
           
            
>> obj.G.Edges(:,1)
ans =
  164×1 table
     EndNodes 
    __________
   36
   90
   40
   80
  160
        :     
  138
  151
  148
  156
  159
	Display all 164 rows.
ans =
  164×1 table
     EndNodes 
    __________
   36
   90
   40
   80
  160
   16
   41
   27
  115
   31
   94
  146
  157
   26
  102
  145
   45
  109
  112
   42
  128
  125
  150
   59
   60
  122
   23
   64
  100
   20
   28
   84
   44
  121
  139
   75
   48
   53
   61
  135
  158
  124
  134
   73
  104
  143
  159
   98
   69
   38
  123
  125
   60
  147
   78
   93
   77
  139
   85
  103
  106
   34
  115
  143
   35
   74
   83
   47
   51
  100
  148
   48
   53
   89
   49
  113
  131
  133
   79
  156
   67
  107
  124
   55
   97
  112
  125
   61
   81
   68
   70
   79
  116
  120
  127
  157
  146
  119
  109
  133
  149
  130
   96
  119
  138
   71
   82
  144
   83
   90
  114
  136
   95
  136
  115
  155
  141
   93
  139
  157
  159
   91
   86
  141
  134
  110
  121
   98
  142
  114
   96
  156
  117
  104
  127
  138
  151
  119
  105
  155
  137
  145
  105
  116
  136
  130
  118
  122
  129
  144
  147
  146
  149
  155
  160
  131
  134
  147
  140
  138
  151
  148
  156
  159
>> 

Sim 2022-6-16

编辑：Sim 2022-6-16

Yes, I do the same, copy to the clipboard, delete from the discussion panel and paste it there with my modifications... but I think that the matlab staff already knows it, and I am confident they will fix it soon :-)

Sim 2022-6-16

@Matt J, any idea on how to solve this small issue ? :)

请先登录，再进行评论。

Find cycles in an undirected graph

6 个评论
显示 4更早的评论隐藏 4更早的评论

采纳的回答

43 个评论
显示 41更早的评论隐藏 41更早的评论

更多回答（2 个）

5 个评论
显示 3更早的评论隐藏 3更早的评论

7 个评论
显示 5更早的评论隐藏 5更早的评论

另请参阅

类别

标签

Community Treasure Hunt

Find cycles in an undirected graph

6 个评论 显示 4更早的评论隐藏 4更早的评论

采纳的回答

43 个评论 显示 41更早的评论隐藏 41更早的评论

更多回答（2 个）

5 个评论 显示 3更早的评论隐藏 3更早的评论

7 个评论 显示 5更早的评论隐藏 5更早的评论

另请参阅

类别

标签

Community Treasure Hunt

6 个评论
显示 4更早的评论隐藏 4更早的评论

43 个评论
显示 41更早的评论隐藏 41更早的评论

5 个评论
显示 3更早的评论隐藏 3更早的评论

7 个评论
显示 5更早的评论隐藏 5更早的评论