# pgRouting Manual (2.5)

## pgr_contractGraph - Experimental

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

Boost Graph Inside

Availability: 2.3.0

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

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.

## Characteristics

The main Characteristics are:
  - Process is done only on edges with positive costs.
  - There are two types of contraction methods used namely,
    - Dead End Contraction
    - Linear Contraction
  - The values returned include the added edges and contracted vertices.
  - The returned values are ordered as follows:
    - column id ascending when type = v
    - column id descending when type = e

## Signature Summary:

The pgr_contractGraph function has the following signatures:

    pgr_contractGraph(edges_sql, contraction_order)
    pgr_contractGraph(edges_sql, contraction_order, max_cycles, forbidden_vertices, directed)

    RETURNS SETOF (seq, type, id, contracted_vertices, source, target, cost)

## Signatures

### Minimal signature

    pgr_contractGraph(edges_sql, contraction_order)

Example: | Making a dead end contraction and a linear contraction.

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

### Complete signature

    pgr_contractGraph(edges_sql, contraction_order, max_cycles, forbidden_vertices, directed)

Example: | Making a dead end contraction and a linear contraction and vertex 2 is forbidden from contraction

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

### Description of the edges_sql query for dijkstra like 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

Column | Type | Description
--- | --- | ---
edges_sql | `TEXT` | SQL query as described above.

contraction_order

`ARRAY[ANY-INTEGER]`

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

forbidden_vertices | `ARRAY[ANY-INTEGER]` | (optional). Identifiers of vertices forbidden from contraction. Default is an empty array.
max_cycles | `INTEGER` | (optional). Number of times the contraction operations on contraction_order will be performed. Default is 1.

directed

`BOOLEAN`

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

## Description of the return values

RETURNS SETOF (seq, type, id, contracted_vertices, source, target, cost)

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

Column | Type | Description
--- | --- | ---
seq | `INTEGER` | Sequential value starting from 1.

type

`TEXT`

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

id

`BIGINT`

Identifier of:
  - the vertex when type = ‘v’.
    - The vertex belongs to the edge_table passed as a parameter.
  - the edge when type = ‘e’.
    - The id is a decreasing sequence starting from -1.
    - Representing a pseudo id as is not incorporated into the edge_table.

contracted_vertices | `ARRAY[BIGINT]` | Array of contracted vertex identifiers.
source | `BIGINT` | Identifier of the source vertex of the current edge id. Valid values when type = ‘e’.
target | `BIGINT` | Identifier of the target vertex of the current edge id. Valid values when type = ‘e’.
cost | `FLOAT` | Weight of the edge (source, target). Valid values when type = ‘e’.

# Examples

Example: | Only dead end contraction

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

Example: | Only linear contraction

    SELECT * FROM pgr_contractGraph(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[2]);
     seq | type | id | contracted_vertices | source | target | cost
    -----+------+----+---------------------+--------+--------+------
       1 | e    | -1 | {4}                 |      9 |      3 |    2
       2 | e    | -2 | {8}                 |      5 |      7 |    2
       3 | e    | -3 | {8}                 |      7 |      5 |    2
       4 | e    | -4 | {12}                |     11 |      9 |    2
    (4 rows)

Indices and tables

- Index
- Search Page