pgr_strongComponents

pgr_strongComponents — Strongly connected components of a directed graph using Tarjan’s algorithm based on DFS.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

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:

  • Works for directed graphs.
  • Components are described by vertices identifiers.
  • 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 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/scc_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.

See Also

Indices and tables