# pgRouting Manual (3.1)

## 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.1) 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