# pgRouting Manual (3.0-rc1)

## pgr_contraction

`pgr_contraction` — Performs graph contraction and returns the contracted vertices and edges.

Boost Graph Inside

Availability

- Version 3.0.0
  - Return columns change: `seq` is removed
  - Name change from `pgr_contractGraph`
  - Bug fixes
  - Official function
- Version 2.3.0
  - New experimental function

Support

- Supported versions: current(3.0)
- Unsupported versions: 2.6 2.5 2.4 2.3

## Description

Contraction reduces the size of the graph by removing some of the vertices and edges and, for example, might add edges that represent a sequence of original edges decreasing the total time and space used in graph algorithms.

The main Characteristics are:
  - Process is done only on edges with positive costs.
  - Does not return the full contracted graph
    - Only changes on the graph are returned
  - Currnetly there are two types of contraction methods
    - Dead End Contraction
    - Linear Contraction
  - The returned values include
    - the added edges by linear contraction.
    - the modified vertices by dead end contraction.
  - The returned values are ordered as follows:
    - column id ascending when type = v
    - column id descending when type = e

## Signatures

Summary

The pgr_contraction function has the following signature:

    pgr_contraction(Edges SQL, Contraction order [, max_cycles] [, forbidden_vertices] [, directed])
    RETURNS SETOF (type, id, contracted_vertices, source, target, cost)

Example: | Making a dead end contraction and a linear contraction with vertex 2 forbidden from being contracted

    SELECT * FROM pgr_contraction(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[1, 2], forbidden_vertices:=ARRAY[2]);
     type | id | contracted_vertices | source | target | cost
    ------+----+---------------------+--------+--------+------
     v    |  2 | {1}                 |     -1 |     -1 |   -1
     v    |  5 | {7,8}               |     -1 |     -1 |   -1
     v    | 10 | {13}                |     -1 |     -1 |   -1
     v    | 15 | {14}                |     -1 |     -1 |   -1
     v    | 17 | {16}                |     -1 |     -1 |   -1
    (5 rows)

## Parameters

Column | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | SQL query as described in Inner query

Ccontraction Order

`ARRAY[ANY-INTEGER]`

Ordered contraction operations.
  - 1 = Dead end contraction
  - 2 = Linear contraction

### Optional Parameters

Column | Type | Default | Description
--- | --- | --- | ---
forbidden_vertices | `ARRAY[ANY-INTEGER]` | Empty | Identifiers of vertices forbidden from contraction.
max_cycles | `INTEGER` | \(1\) | Number of times the contraction operations on contraction_order will be performed.

directed

`BOOLEAN`

`true`

- When `true` the graph is considered as Directed.
- When `false` the graph is considered as Undirected.

## Inner query

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 SETOF (type, id, contracted_vertices, source, target, cost)

The function returns a single row. The columns of the row are:

Column | Type | Description
--- | --- | ---

type

`TEXT`

Type of the id.
  - ‘v’ when the row is a vertex.
  - ‘e’ when the row is an edge.

id

`BIGINT`

All numbers on this column are `DISTINCT`
  - When `type` = ‘v’.
    - Identifier of the modified vertex.
  - When `type` = ‘e’.
    - Decreasing sequence starting from -1.
    - Representing a pseudo id as is not incorporated in the set of original edges.

contracted_vertices | `ARRAY[BIGINT]` | Array of contracted vertex identifiers.

source

`BIGINT`

- When `type` = ‘v’: \(-1\)
- When `type` = ‘e’: Identifier of the source vertex of the current edge (`source`, `target`).

target

`BIGINT`

- When `type` = ‘v’: \(-1\)
- When `type` = ‘e’: Identifier of the target vertex of the current edge (`source`, `target`).

cost

`FLOAT`

- When `type` = ‘v’: \(-1\)
- When `type` = ‘e’: Weight of the current edge (`source`, `target`).

## Additional Examples

Example: | Only dead end contraction

    SELECT * FROM pgr_contraction(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[1]);
     type | id | contracted_vertices | source | target | cost
    ------+----+---------------------+--------+--------+------
     v    |  2 | {1}                 |     -1 |     -1 |   -1
     v    |  5 | {7,8}               |     -1 |     -1 |   -1
     v    | 10 | {13}                |     -1 |     -1 |   -1
     v    | 15 | {14}                |     -1 |     -1 |   -1
     v    | 17 | {16}                |     -1 |     -1 |   -1
    (5 rows)

Example: | Only linear contraction

    SELECT * FROM pgr_contraction(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[2]);
     type | id | contracted_vertices | source | target | cost
    ------+----+---------------------+--------+--------+------
     e    | -1 | {8}                 |      5 |      7 |    2
     e    | -2 | {8}                 |      7 |      5 |    2
    (2 rows)

## See Also

- Contraction - Family of functions

Indices and tables

- Index
- Search Page