conncomp

Create and plot an undirected graph with three connected components. Use conncomp to determine which component each node belongs to.

G = graph([1 1 4],[2 3 5],[1 1 1],6);
plot(G)

bins = conncomp(G)

bins = 1×6

     1     1     1     2     2     3

Create and plot a directed graph, and then compute the strongly connected components and weakly connected components. Weakly connected components ignore the direction of connecting edges.

s = [1 2 2 3 3 3 4 5 5 5 8 8];
t = [2 3 4 1 4 5 5 3 6 7 9 10];
G = digraph(s,t);
plot(G,'Layout','layered')

str_bins = conncomp(G)

str_bins = 1×10

     4     4     4     4     4     6     5     1     3     2

weak_bins = conncomp(G,'Type','weak')

weak_bins = 1×10

     1     1     1     1     1     1     1     2     2     2

Use the second output of conncomp to extract the largest component of a graph or to remove components below a certain size.

Create and plot a directed graph. The graph has one large component, one small component, and several components that contain only a single node.

s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = digraph(s,t,[],20);
plot(G,'Layout','layered')

Calculate the weakly connected components and specify two outputs to conncomp to get the size of each component.

[bin,binsize] = conncomp(G,'Type','weak')

bin = 1×20

     1     1     1     1     1     1     1     2     2     2     3     4     5     6     7     8     9    10    11    12

binsize = 1×12

     7     3     1     1     1     1     1     1     1     1     1     1

Use binsize to extract the largest component from the graph. idx is a logical index indicating whether each node belongs to the largest component. The subgraph function extracts the nodes selected by idx from G.

idx = binsize(bin) == max(binsize);
SG = subgraph(G, idx);
plot(SG)

A similar use of binsizes is to filter out components based on size. The procedure is similar to extracting the largest component, however in this case each node can belong to any component that meets the size requirement.

Filter out any components in G that have fewer than 3 nodes. idx is a logical index indicating whether each node belongs to a component with 3 or more nodes.

idx = binsize(bin) >= 3;
SG = subgraph(G, idx);
plot(SG)