Bioinformatics Toolbox™

graphconncomp - Find strongly or weakly connected components in graph

Syntax

[S, C] = graphconncomp(G)

[S, C] = graphconncomp(G, ...'Directed', DirectedValue, ...)
[S, C] = graphconncomp(G, ...'Weak', WeakValue, ...)

Arguments

Description

Tip   For introductory information on graph theory functions, see Graph Theory Functions in the Bioinformatics Toolbox User's Guide.

[S, C] = graphconncomp(G) finds the strongly connected components of the graph represented by matrix G using Tarjan's algorithm. A strongly connected component is a maximal group of nodes that are mutually reachable without violating the edge directions. Input G is an N-by-N sparse matrix that represents a graph. Nonzero entries in matrix G indicate the presence of an edge.

The number of components found is returned in S, and C is a vector indicating to which component each node belongs.

Tarjan's algorithm has a time complexity of O(N+E), where N and E are the number of nodes and edges respectively.

[S, C] = graphconncomp(G, ...'PropertyName', PropertyValue, ...) calls graphconncomp with optional properties that use property name/property value pairs. You can specify one or more properties in any order. Each PropertyName must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:

[S, C] = graphconncomp(G, ...'Directed', DirectedValue, ...) indicates whether the graph is directed or undirected. Set directedValue to false for an undirected graph. This results in the upper triangle of the sparse matrix being ignored. Default is true. A DFS-based algorithm computes the connected components. Time complexity is O(N+E), where N and E are number of nodes and edges respectively.

[S, C] = graphconncomp(G, ...'Weak', WeakValue, ...) indicates whether to find weakly connected components or strongly connected components. A weakly connected component is a maximal group of nodes that are mutually reachable by violating the edge directions. Set WeakValue to true to find weakly connected components. Default is false, which finds strongly connected components. The state of this parameter has no effect on undirected graphs because weakly and strongly connected components are the same in undirected graphs. Time complexity is O(N+E), where N and E are number of nodes and edges respectively.

Note   By definition, a single node can be a strongly connected component.

Note   A directed acyclic graph (DAG) cannot have any strongly connected components larger than one.

Examples

1. Create and view a directed graph with 10 nodes and 17 edges.

   DG = sparse([1 1 1 2 2 3 3 4 5 6 7 7 8 9 9  9 9], ...
              [2 6 8 3 1 4 2 5 4 7 6 4 9 8 10 5 3],true,10,10)
   
   DG =
   
      (2,1)        1
      (1,2)        1
      (3,2)        1
      (2,3)        1
      (9,3)        1
      (3,4)        1
      (5,4)        1
      (7,4)        1
      (4,5)        1
      (9,5)        1
      (1,6)        1
      (7,6)        1
      (6,7)        1
      (1,8)        1
      (9,8)        1
      (8,9)        1
      (9,10)       1
   
   h = view(biograph(DG));

   

2. Find the number of strongly connected components in the directed graph and determine to which component each of the 10 nodes belongs.

   [S,C] = graphconncomp(DG)
   
   S =
   
        4
   
   
   C =
   
        4     4     4     1     1     2     2     4     4     3
   

3. Color the nodes for each component with a different color.

   colors = jet(S);
   for i = 1:numel(h.nodes)
     h.Nodes(i).Color = colors(C(i),:);
   end

   

References

[1] Tarjan, R.E., (1972). Depth first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160.

[2] Sedgewick, R., (2002). Algorithms in C++, Part 5 Graph Algorithms (Addison-Wesley).

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

See Also

Bioinformatics Toolbox functions: graphallshortestpaths, graphisdag, graphisomorphism, graphisspantree, graphmaxflow, graphminspantree, graphpred2path, graphshortestpath, graphtopoorder, graphtraverse

Bioinformatics Toolbox method of biograph object: conncomp

graphallshortestpaths

graphisdag