Find strongly or weakly connected components in biograph object
[S, C]
= conncomp(BGObj)
[S, C]
= conncomp(BGObj, ...'Directed', DirectedValue,
...)
[S, C]
= conncomp(BGObj, ...'Weak', WeakValue,
...)
BGObj | Biograph object created by biograph (object
constructor). |
DirectedValue | Property that indicates whether the graph is directed or undirected.
Enter 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 |
WeakValue | Property that 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. |
Tip
For introductory information on graph theory functions, see Graph Theory Functions.
[ finds the
strongly connected components of an N-by-N adjacency matrix extracted
from a biograph object, S, C]
= conncomp(BGObj)BGObj using Tarjan's
algorithm. A strongly connected component is a maximal group of nodes
that are mutually reachable without violating the edge directions.
The N-by-N sparse matrix represents a directed graph; all nonzero
entries in the matrix 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.
[ calls S, C]
= conncomp(BGObj, ...'PropertyName', PropertyValue,
...)conncomp 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:
[ indicates whether the graph is directed or undirected.
Set S, C]
= conncomp(BGObj, ...'Directed', DirectedValue,
...)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.
[ 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 S, C]
= conncomp(BGObj, ...'Weak', WeakValue,
...)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.
[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).
allshortestpaths | biograph | graphconncomp | isdag | isomorphism | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse