pgr_strongComponents - Experimental¶

pgr_strongComponents — Return the strongly connected components of a directed graph using Tarjan’s algorithm based on DFS. In particular, the algorithm implemented by Boost.Graph.

Warning

Experimental functions

• They are not officially of the current release.
• They likely will not be officially be part of the next release:
• The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
• Name might change.
• Signature might change.
• Functionality might change.
• pgTap tests might be missing.
• Might need c/c++ coding.
• May lack documentation.
• Documentation if any might need to be rewritten.
• Documentation examples might need to be automatically generated.
• Might need a lot of feedback from the comunity.
• Might depend on a proposed function of pgRouting
• Might depend on a deprecated function of pgRouting

Synopsis¶

A strongly connected component of a directed graph is a set of vertices that are all reachable from each other. This implementation can only be used with a directed graph.

Characteristics¶

The main Characteristics are:

• 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, n_seq, node)
OR EMPTY SET


The signature is for a directed graph.

SELECT * FROM pgr_strongComponents(
'SELECT id, source, target, cost, reverse_cost FROM edge_table'
);
seq | component | n_seq | node
-----+-----------+-------+------
1 |         1 |     1 |    1
2 |         1 |     2 |    2
3 |         1 |     3 |    3
4 |         1 |     4 |    4
5 |         1 |     5 |    5
6 |         1 |     6 |    6
7 |         1 |     7 |    7
8 |         1 |     8 |    8
9 |         1 |     9 |    9
10 |         1 |    10 |   10
11 |         1 |    11 |   11
12 |         1 |    12 |   12
13 |         1 |    13 |   13
14 |        14 |     1 |   14
15 |        14 |     2 |   15
16 |        16 |     1 |   16
17 |        16 |     2 |   17
(17 rows)



Description of the Signatures¶

Description of the edges_sql query for components functions¶

edges_sql: an SQL query, 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 SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Description of the parameters of the signatures¶

Parameter Type Default Description
edges_sql TEXT   SQL query as described above.

Description of the return values for connected components and strongly connected components¶

Returns set of (seq, component, n_seq, node)

Column Type Description
seq INT Sequential value starting from 1.
component BIGINT Component identifier. It is equal to the minimum node identifier in the component.
n_seq INT It is a sequential value starting from 1 in a component.
node BIGINT Identifier of the vertex.