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 removed - Official function
- Return columns change:
- Version 2.5.0
- New experimental function
Support
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 | TEXT |
Inner query as described bellow. |
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 | 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 |
Result Columns¶
Returns set of (seq, component, node)
Column | Type | Description |
---|---|---|
seq | INT |
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. |
See Also¶
- Components - Family of functions
- The queries use the Sample Data network.
- Boost: Connected components
- wikipedia: Connected component
Indices and tables