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:

  • 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

Parameter

Type

Default

Description

Edges SQL

TEXT

Inner query as described below.

Inner query

edges SQL :

an SQL query of a directed graph, 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

Result Columns

Returns set of (seq, component, node)

Column

Type

Description

seq

BIGINT

Sequential value starting from 1 .

component

BIGINT

Component identifier. It is equal to the minimum node identifier in the component.

node

BIGINT

Identifier of the vertex that belongs to component .

See Also

Indices and tables