pgr_strongComponents - Experimental

pgr_strongComponents — Return the strongly connected components of a directed graph using Tarjan’s algorithm based on DFS. In particular, the algorithm implemented by Boost.Graph.

_images/boost-inside.jpeg

Boost Graph Inside

Warning

Experimental functions

  • They are not officially of the current release.
  • They likely will not be officially be part of the next release:
    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
    • Name might change.
    • Signature might change.
    • Functionality might change.
    • pgTap tests might be missing.
    • Might need c/c++ coding.
    • May lack documentation.
    • Documentation if any might need to be rewritten.
    • Documentation examples might need to be automatically generated.
    • Might need a lot of feedback from the comunity.
    • Might depend on a proposed function of pgRouting
    • Might depend on a deprecated function of pgRouting

Synopsis

A strongly connected component of a directed graph is a set of vertices that are all reachable from each other. This implementation can only be used with a directed graph.

Characteristics

The main Characteristics are:

  • 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, n_seq, node)
    OR EMPTY SET

The signature is for a directed graph.

Example: 
SELECT * FROM pgr_strongComponents(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table'
);
 seq | component | n_seq | node
-----+-----------+-------+------
   1 |         1 |     1 |    1
   2 |         1 |     2 |    2
   3 |         1 |     3 |    3
   4 |         1 |     4 |    4
   5 |         1 |     5 |    5
   6 |         1 |     6 |    6
   7 |         1 |     7 |    7
   8 |         1 |     8 |    8
   9 |         1 |     9 |    9
  10 |         1 |    10 |   10
  11 |         1 |    11 |   11
  12 |         1 |    12 |   12
  13 |         1 |    13 |   13
  14 |        14 |     1 |   14
  15 |        14 |     2 |   15
  16 |        16 |     1 |   16
  17 |        16 |     2 |   17
(17 rows)
_images/scc_sampledata.png

Description of the Signatures

Description of the edges_sql query for components functions

edges_sql:an SQL query, 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)

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

Description of the parameters of the signatures

Parameter Type Default Description
edges_sql TEXT   SQL query as described above.

Description of the return values for connected components and strongly connected components

Returns set of (seq, component, n_seq, 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.
n_seq INT It is a sequential value starting from 1 in a component.
node BIGINT Identifier of the vertex.

See Also

Indices and tables