pgr_connectedComponents¶
pgr_connectedComponents
— Connected components of an undirected graph using a DFS-based approach.
Availability
Version 3.0.0
Return columns change:
n_seq
is removedseq
changed type toBIGINT
Official function
Version 2.5.0
New experimental function
Description¶
A connected component of an undirected graph is a set of vertices that are all reachable from each other.
The main characteristics are:
The signature is for an undirected graph.
Components are described by vertices
The returned values are ordered:
component ascending
node ascending
Running time: \(O(V + E)\)
Signatures¶
pgr_connectedComponents(edges_sql)
RETURNS SET OF (seq, component, node)
OR EMPTY SET
- Example
The connected components of the graph
SELECT * FROM pgr_connectedComponents(
'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)
Parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
Edges SQL |
|
Inner query as described below. |
Inner query¶
- edges SQL
an SQL query of an undirected graph, which should return a set of rows with the following columns:
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Identifier of the edge. |
|
source |
|
Identifier of the first end point vertex of the edge. |
|
target |
|
Identifier of the second end point vertex of the edge. |
|
cost |
|
Weight of the edge (source, target)
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source),
|
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 |
|
Sequential value starting from 1. |
component |
|
Component identifier. It is equal to the minimum node identifier in the component. |
node |
|
Identifier of the vertex that belongs to component. |
See Also¶
The queries use the Sample Data network.
Boost: Connected components
wikipedia: Connected component
Indices and tables