# pgRouting Manual (3.6)

## pgr_strongComponents

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

  - Result 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