# pgRouting Manual (2.5)

## pgr_connectedComponents - Experimental

`pgr_connectedComponents` — Return the connected components of an undirected graph using a DFS-based approach. In particular, the algorithm implemented by Boost.Graph.

Boost Graph Inside

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 connected component of an undirected graph is a set of vertices that are all reachable from each other. This implementation can only be used with an undirected 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_connectedComponents(edges_sql)

    RETURNS SET OF (seq, component, n_seq, node)
        OR EMPTY SET

The signature is for a undirected graph.

Example: |

    SELECT * FROM pgr_connectedComponents(
        '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
ANY-NUMERICAL: | 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.

## See Also

- http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29
- The queries use the Sample Data network.

Indices and tables

- Index
- Search Page