graphconncomp
(Removed) Find strongly or weakly connected components in graph
graphconncomp
has been removed. Use conncomp
instead.
Syntax
[
S
, C
]
= graphconncomp(G
)
[S
, C
]
= graphconncomp(G
, ...'Directed', DirectedValue
, ...)
[S
, C
]
= graphconncomp(G
, ...'Weak', WeakValue
, ...)
Arguments
G
| N-by-N adjacency matrix that represents a graph. Nonzero entries
in matrix G indicate the presence of an
edge. |
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 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. |
Description
Tip
For introductory information on graph theory functions, see Graph Theory Functions.
[
finds the strongly connected components of the graph represented by matrix
S
, C
]
= graphconncomp(G
)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 adjacency 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.
[
calls
S
, C
] =
graphconncomp(G
,
...'PropertyName
',
PropertyValue
, ...)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:
[
indicates whether the graph is directed or undirected. Set
S
, C
]
= graphconncomp(G
, ...'Directed', DirectedValue
, ...)directedValue
to false
for an
undirected graph. This results in the upper triangle of the 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
]
= graphconncomp(G
, ...'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.
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).