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