30 views (last 30 days)

Christine Tobler
on 11 Jan 2021

The biconncomp function will split the edges of a graph into its biconnected components. If the output of biconncomp is a vector of all ones, that graph is two-connected.

Otherwise, here's some code that will extract each biconnected component as an individual graph as follows:

s = [1 1 2 2 3 4 4 5 6 6 7 7 8];

t = [2 3 3 4 4 5 7 6 7 10 8 9 9];

G = graph(s,t);

p = plot(G);

bins = biconncomp(G);

for binNr = 1:max(bins)

st = G.Edges.EndNodes;

Gbin = subgraph(G, unique(st(bins == binNr, :)));

figure;

plot(Gbin)

end

Keep in mind: For a graph without node names in MATLAB, nodes are numbered through 1, 2, ..., [number of nodes]. This means that the subgraph command can assign a new node index (e.g., if G has three nodes, subgraph(G, [1 3]) will return a graph where the previous node 3 is now node 2). You can avoid this by using node names.

Image Analyst
on 11 Jan 2021

Visualization (for other people):

s = [1 1 2 2 3 4 4 5 6 6 7 7 8];

t = [2 3 3 4 4 5 7 6 7 10 8 9 9];

G = graph(s,t);

subplot(2, 3, 1);

p = plot(G);

bins = biconncomp(G);

for binNr = 1:max(bins)

st = G.Edges.EndNodes;

Gbin = subgraph(G, unique(st(bins == binNr, :)));

subplot(2, 3, binNr + 1);

plot(Gbin)

caption = sprintf('Bin #%d', binNr);

title(caption, 'FontSize', 15);

end

g = gcf;

g.WindowState = 'maximized';

Christine Tobler
on 12 Jan 2021

If a graph is 3- or 4- connected, this means it is also two-connected (biconnected). The biconncomp function only answer the question of whether a graph is two-connected or how it can be split into biconnected components.

MATLAB doesn't have functionality for computing k-connectivity except for k=1 (conncomp) and k=2 (biconncomp). For the 3-connected case I think you're looking for, a quick wikipedia search suggests you might need to look at the concept of SPQR trees. An algorithm is described on that page, with reference to papers for details.

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

Start Hunting!
## 0 Comments

Sign in to comment.