# pgr_contraction¶

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

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

## 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
• 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);
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 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).

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