pgr_strongComponents — Strongly connected components of a directed graph using Tarjan’s algorithm based on DFS.
Boost Graph Inside
Availability
n_seq is removedseq changed type to BIGINTSupport
A strongly connected component of a directed graph is a set of vertices that are all reachable from each other.
The main characteristics are:
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 edge_table'
);
seq | component | node
-----+-----------+------
1 | 1 | 1
2 | 1 | 2
3 | 1 | 3
4 | 1 | 4
5 | 1 | 5
6 | 1 | 6
7 | 1 | 7
8 | 1 | 8
9 | 1 | 9
10 | 1 | 10
11 | 1 | 11
12 | 1 | 12
13 | 1 | 13
14 | 14 | 14
15 | 14 | 15
16 | 16 | 16
17 | 16 | 17
(17 rows)
| Parameter | Type | Default | Description |
|---|---|---|---|
| Edges SQL | TEXT |
Inner query as described below. |
| edges SQL: | an SQL query of a directed graph, which should return a set of rows with the following columns: |
|---|
| 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 (target, source),
|
Where:
| ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
|---|---|
| ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Returns set of (seq, component, node)
| Column | Type | Description |
|---|---|---|
| seq | BIGINT |
Sequential value starting from 1. |
| component | BIGINT |
Component identifier. It is equal to the minimum node identifier in the component. |
| node | BIGINT |
Identifier of the vertex that belongs to component. |
Indices and tables