# pgRouting Manual (3.3)

## pgr_strongComponents

- Supported versions: Latest (3.3) 3.2 3.1 3.0

- Unsupported versions: 2.6 2.5

# 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:

- 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

- Components - Family of functions

- The queries use the Sample Data network.

- Boost: Strong components

- wikipedia: Strongly connected component

Indices and tables

- Index

- Search Page