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

  • Version 3.0.0

    • Return columns change:

      • n_seq is removed

      • seq changed type to BIGINT

    • Official function

  • Version 2.5.0

    • New experimental function

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