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 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
   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)
images/cc_sampledata.png

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
   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)

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
   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)

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     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

Indices and tables