Select edges that connect subgraphs together

3 views (last 30 days)
I have a graph like this
M = [1 2; 2 3; 1 3; 4 5; 5 6; 6 7; 4 7;2 4; 5 7; 5 8;11 8; 8 9; 9 10; 10 11;4 12; 12,13; 13 14;12 14];
g = graph(M(:, 1), M(:, 2));
h = plot(g);
I want to find edges that connect subgraphs together
result should be
A = [2,4; 5 8; 4 12]
  2 Comments
Sean de Wolski
Sean de Wolski on 8 Apr 2020
So trying to verbalize the rule: return any edge whose two end nodes are connected to at least two other nodes?
(Also, your data do not include nodes 12/13/14 so [4 12] wouldn't be returned)

Sign in to comment.

Accepted Answer

Sean de Wolski
Sean de Wolski on 8 Apr 2020
This works for your sample data set (which does not include nodes 12:14 as shown in the plot. Please test test this, I'm not a graph theory expert so there may be cases where this does not work.
M = [1 2; 2 3; 1 3; 4 5; 5 6; 6 7; 4 7;2 4; 5 7; 5 8;11 8; 8 9; 9 10; 10 11];
g = graph(M(:, 1), M(:, 2));
h = plot(g);
bcg = biconncomp(g).'; % biconnected components
[count, group] = groupcounts(bcg); % How many of each?
edgeidx = ismember(bcg, group(count==1)); % Edges with one count
g.Edges(edgeidx, 1) % Extract
ans =
2×1 table
EndNodes
________
2 4
5 8

More Answers (1)

darova
darova on 8 Apr 2020

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!