Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5

`pgr_connectedComponents`¶

pgr_connectedComponents — Connected components of an undirected graph using a DFS-based approach.

Availability

Version 3.0.0
- Result columns change:
  - n_seq is removed
  - seq changed type to BIGINT
- Function promoted to official.
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 ascending
- node ascending
Running time: $O (V + E)$

Boost Graph Inside

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 edges'
);
 seq | component | node
-----+-----------+------
|         1 |    1
|         1 |    3
|         1 |    5
|         1 |    6
|         1 |    7
|         1 |    8
|         1 |    9
|         1 |   10
|         1 |   11
|         1 |   12
|         1 |   15
|         1 |   16
|         1 |   17
|         2 |    2
|         2 |    4
|        13 |   13
|        13 |   14
(17 rows)

Parameters¶

Parameter	Type	Description
Edges SQL	`TEXT`	Edges SQL as described below.

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 (`target`, `source`) When negative: edge (`target`, `source`) does not exist, therefore it’s not part of the graph.

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.

Has the value of the minimum node identifier in the component.

node

BIGINT

Identifier of the vertex that belongs to the component.

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 |    3
|         1 |    5
|         1 |    6
|         1 |    7
|         1 |    8
|         1 |    9
|         1 |   10
|         1 |   11
|         1 |   12
|         1 |   15
|         1 |   16
|         1 |   17
|         2 |    2
|         2 |    4
|        13 |   13
|        13 |   14
(17 rows)

There are three basic ways to connect 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.

In this example pgr_separateCrossing and pgr_separateTouching will be used.

Get the connectivity

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | node
-----+-----------+------
|         1 |    1
|         1 |    3
|         1 |    5
|         1 |    6
|         1 |    7
|         1 |    8
|         1 |    9
|         1 |   10
|         1 |   11
|         1 |   12
|         1 |   15
|         1 |   16
|         1 |   17
|         2 |    2
|         2 |    4
|        13 |   13
|        13 |   14
(17 rows)

Prepare tables

In this example: the edges table will need an additional column and the vertex table will be rebuilt completely.

ALTER TABLE edges ADD old_id BIGINT;
ALTER TABLE
DROP TABLE vertices;
DROP TABLE

Insert new edges

Using pgr_separateCrossing and pgr_separateTouching insert the results into the edges table.

INSERT INTO edges (old_id, geom)
SELECT id, geom FROM pgr_separateCrossing('SELECT * FROM edges')
UNION
SELECT id, geom FROM pgr_separateTouching('SELECT * FROM edges');
INSERT 0 6

Create the vertices table

Using pgr_extractVertices create the table.

CREATE TABLE vertices AS
SELECT * FROM pgr_extractVertices('SELECT id, geom FROM edges');
SELECT 18

Update the topology

/* -- set the source information */
UPDATE edges AS e
SET source = v.id, x1 = x, y1 = y
FROM vertices AS v
WHERE ST_StartPoint(e.geom) = v.geom;
UPDATE 24
/* -- set the target information */
UPDATE edges AS e
SET target = v.id, x2 = x, y2 = y
FROM vertices AS v
WHERE ST_EndPoint(e.geom) = v.geom;
UPDATE 24

Update other values

In this example only cost and reverse_cost are updated, where they are based on the length of the geometry and the directionality is kept using the sign function.

UPDATE edges e
  SET cost          = ST_length(e.geom)*sign(e1.cost),
      reverse_cost  = ST_length(e.geom)*sign(e1.reverse_cost)
FROM edges e1
WHERE e.cost IS NULL AND e1.id = e.old_id;
UPDATE 6

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | node
-----+-----------+------
|         1 |    1
|         1 |    2
|         1 |    3
|         1 |    4
|         1 |    5
|         1 |    6
|         1 |    7
|         1 |    8
|         1 |    9
|         1 |   10
|         1 |   11
|         1 |   12
|         1 |   13
|         1 |   14
|         1 |   15
|         1 |   16
|         1 |   17
|         1 |   18
(18 rows)

pgr_connectedComponents¶

Description¶

Signatures¶

Parameters¶

Inner Queries¶

Edges SQL¶

Result columns¶

Additional Examples¶

Connecting disconnected components¶

See Also¶

`pgr_connectedComponents`¶