pgr_strongComponents

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

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)

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

• Components - Family of functions

• The queries use the Sample Data network.

• Boost: Strong components

• wikipedia: Strongly connected component

Indices and tables

• Index

• Search Page