# pgRouting Manual (3.6)

## pgr_contraction

# `pgr_contraction`

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

Boost Graph Inside

Availability

- Version 3.0.0

  - Result columns change: `seq` is removed

  - Name change from `pgr_contractGraph`

  - Bug fixes

  - Official function

- Version 2.3.0

  - New experimental function

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

  - column `id` descending when type is `e`

## Signatures

Summary

The pgr_contraction function has the following signature:

pgr_contraction(Edges SQL, contraction order, [options])
options: `[ max_cycles, forbidden_vertices, directed]`
Returns set of `(type, id, contracted_vertices, source, target, cost)`

Example:

  Making a dead end and linear contraction in that order on an undirected graph.

    SELECT * FROM pgr_contraction(
      'SELECT id, source, target, cost, reverse_cost FROM edges',
      ARRAY[1, 2], directed => false);
     type | id | contracted_vertices | source | target | cost
    ------+----+---------------------+--------+--------+------
     v    |  4 | {2}                 |     -1 |     -1 |   -1
     v    |  7 | {1,3}               |     -1 |     -1 |   -1
     v    | 14 | {13}                |     -1 |     -1 |   -1
     e    | -1 | {5,6}               |      7 |     10 |    2
     e    | -2 | {8,9}               |      7 |     12 |    2
     e    | -3 | {17}                |     12 |     16 |    2
     e    | -4 | {15}                |     10 |     16 |    2
    (7 rows)

## Parameters

Parameter | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below.

contraction Order

`ARRAY[` ANY-INTEGER `]`

Ordered contraction operations.

- 1 = Dead end contraction

- 2 = Linear contraction

### Optional parameters

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

`directed`

`BOOLEAN`

`true`

- When `true` the graph is considered Directed

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

### Contraction optional parameters

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

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

  - Column `id` has a positive value

- `e` when the row is an edge.

  - Column `id` has a negative value

`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 type, id, contracted_vertices FROM pgr_contraction(
      'SELECT id, source, target, cost, reverse_cost FROM edges',
      ARRAY[1]);
     type | id | contracted_vertices
    ------+----+---------------------
     v    |  4 | {2}
     v    |  6 | {5}
     v    |  7 | {1,3}
     v    |  8 | {9}
     v    | 14 | {13}
    (5 rows)

Example:

  Only linear contraction

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

## See Also

- Contraction - Family of functions

Indices and tables

- Index

- Search Page