pgr_strongComponents
¶
pgr_strongComponents
— Strongly connected components of a directed graph
using Tarjan’s algorithm based on DFS.
Availability
- Version 3.0.0
- Return columns change:
n_seq
is removedseq
changed type toBIGINT
- Official function
- Return columns change:
- Version 2.5.0
- New experimental function
Description¶
A strongly connected component of a directed graph is a set of vertices that are all reachable from each other.
The main characteristics are:
- Works for directed graphs.
- Components are described by vertices identifiers.
- The returned values are ordered:
component
ascendingnode
ascending
- Running time: \(O(V + E)\)
Signatures¶
pgr_strongComponents(Edges SQL) RETURNS SET OF (seq, component, node) OR EMPTY SET
Example: | The strong components of the graph |
---|
SELECT * FROM pgr_strongComponents(
'SELECT id, source, target, cost, reverse_cost FROM edges'
);
seq | component | node
-----+-----------+------
1 | 1 | 1
2 | 1 | 3
3 | 1 | 5
4 | 1 | 6
5 | 1 | 7
6 | 1 | 8
7 | 1 | 9
8 | 1 | 10
9 | 1 | 11
10 | 1 | 12
11 | 1 | 15
12 | 1 | 16
13 | 1 | 17
14 | 2 | 2
15 | 2 | 4
16 | 13 | 13
17 | 13 | 14
(17 rows)
Inner Queries¶
Edges SQL¶
Column | Type | Default | Description |
---|---|---|---|
id |
ANY-INTEGER | Identifier of the edge. | |
source |
ANY-INTEGER | Identifier of the first end point vertex of the edge. | |
target |
ANY-INTEGER | Identifier of the second end point vertex of the edge. | |
cost |
ANY-NUMERICAL | Weight of the edge (source , target ) |
|
reverse_cost |
ANY-NUMERICAL | -1 | Weight of the edge (
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Result Columns¶
Returns set of (seq, component, node)
Column | Type | Description |
---|---|---|
seq |
BIGINT |
Sequential value starting from 1. |
component |
BIGINT |
Component identifier.
|
node |
BIGINT |
Identifier of the vertex that belongs to the component . |
See Also¶
- Components - Family of functions
- The queries use the Sample Data network.
- Boost: Strong components
- wikipedia: Strongly connected component
Indices and tables