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:
Works for undirected graphs.
Components are described by vertices
The returned values are ordered:
component
ascendingnode
ascending
Running time: \(O(V + E)\)
Signatures¶
(seq, component, node)
- Example:
The connected components of the graph
SELECT * FROM pgr_connectedComponents(
'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)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
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 |
---|---|---|
|
|
Sequential value starting from 1. |
|
|
Component identifier.
|
|
|
Identifier of the vertex that belongs to the |
Additional Examples¶
Connecting disconnected components¶
To get the graph connectivity:
SELECT * FROM pgr_connectedComponents(
'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 | 13
12 | 1 | 14
13 | 1 | 15
14 | 1 | 16
15 | 1 | 17
16 | 1 | 18
17 | 2 | 2
18 | 2 | 4
(18 rows)
In this example, the component \(2\) consists of vertices \(\{2, 4\}\) and both vertices are also part of the dead end result set.
This graph needs to be connected.
Note
With the original graph of this documentation, there would be 3 components as the crossing edge in this graph is a different component.
Prepare storage for connection information¶
ALTER TABLE vertices ADD COLUMN component BIGINT;
ALTER TABLE
ALTER TABLE edges ADD COLUMN component BIGINT;
ALTER TABLE
Save the vertices connection information¶
UPDATE vertices SET component = c.component
FROM (SELECT * FROM pgr_connectedComponents(
'SELECT id, source, target, cost, reverse_cost FROM edges'
)) AS c
WHERE id = node;
UPDATE 18
Save the edges connection information¶
UPDATE edges SET component = v.component
FROM (SELECT id, component FROM vertices) AS v
WHERE source = v.id;
UPDATE 20
Get the closest vertex¶
Using pgr_findCloseEdges the closest vertex to component \(1\) is vertex \(4\). And the closest edge to vertex \(4\) is edge \(14\).
SELECT edge_id, fraction, ST_AsText(edge) AS edge, id AS closest_vertex
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges WHERE component = 1$$,
(SELECT array_agg(geom) FROM vertices WHERE component = 2),
2, partial => false) JOIN vertices USING (geom) ORDER BY distance LIMIT 1;
edge_id | fraction | edge | closest_vertex
---------+----------+--------------------------------------+----------------
14 | 0.5 | LINESTRING(1.999999999999 3.5,2 3.5) | 4
(1 row)
The edge
can be used to connect the components, using the fraction
information about the edge \(14\) to split the connecting edge.
Connecting components¶
There are three basic ways to connect the components
From the vertex to the starting point of the edge
From the vertex to the ending point of the edge
From the vertex to the closest vertex on the edge
This solution requires the edge to be split.
The following query shows the three ways to connect the components:
WITH
info AS (
SELECT
edge_id, fraction, side, distance, ce.geom, edge, v.id AS closest,
source, target, capacity, reverse_capacity, e.geom AS e_geom
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges WHERE component = 1$$,
(SELECT array_agg(geom) FROM vertices WHERE component = 2),
2, partial => false) AS ce
JOIN vertices AS v USING (geom)
JOIN edges AS e ON (edge_id = e.id)
ORDER BY distance LIMIT 1),
three_options AS (
SELECT
closest AS source, target, 0 AS cost, 0 AS reverse_cost,
capacity, reverse_capacity,
ST_X(geom) AS x1, ST_Y(geom) AS y1,
ST_X(ST_EndPoint(e_geom)) AS x2, ST_Y(ST_EndPoint(e_geom)) AS y2,
ST_MakeLine(geom, ST_EndPoint(e_geom)) AS geom
FROM info
UNION
SELECT closest, source, 0, 0, capacity, reverse_capacity,
ST_X(geom) AS x1, ST_Y(geom) AS y1,
ST_X(ST_StartPoint(e_geom)) AS x2, ST_Y(ST_StartPoint(e_geom)) AS y2,
ST_MakeLine(info.geom, ST_StartPoint(e_geom))
FROM info
/*
UNION
-- This option requires splitting the edge
SELECT closest, NULL, 0, 0, capacity, reverse_capacity,
ST_X(geom) AS x1, ST_Y(geom) AS y1,
ST_X(ST_EndPoint(edge)) AS x2, ST_Y(ST_EndPoint(edge)) AS y2,
edge
FROM info */
)
INSERT INTO edges
(source, target,
cost, reverse_cost,
capacity, reverse_capacity,
x1, y1, x2, y2,
geom)
(SELECT
source, target, cost, reverse_cost, capacity, reverse_capacity,
x1, y1, x2, y2, geom
FROM three_options);
INSERT 0 2
Checking components¶
Ignoring the edge that requires further work. The graph is now fully connected as there is only one component.
SELECT * FROM pgr_connectedComponents(
'SELECT id, source, target, cost, reverse_cost FROM edges'
);
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 | 1 | 14
15 | 1 | 15
16 | 1 | 16
17 | 1 | 17
18 | 1 | 18
(18 rows)
See Also¶
The queries use the Sample Data network.
Boost: Connected components
wikipedia: Connected component
Indices and tables