pgr_strongComponents - pgRouting Manual (3.2)

Description

A strongly connected component of a directed graph is a set of vertices that are all reachable from each other.

The main characteristics are:

• The signature is for a directed graph.

• Components are described by vertices

• The returned values are ordered:

  • component ascending

  • node ascending

• Running time: \(O(V + E)\)

Signatures

pgr_strongComponents(Edges SQL)

RETURNS SET OF (seq, component, node)
OR EMPTY SET

Example :

The strong components of the graph

SELECT * FROM pgr_strongComponents(
    '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

Inner query

edges SQL :

an SQL query of a directed graph, which should return a set of rows with the following columns:

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Returns set of (seq, component, node)

See Also

• Components - Family of functions

• The queries use the Sample Data network.

• Boost: Strong components

• wikipedia: Strongly connected component

Indices and tables

• Index

• Search Page