# 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

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

Example:

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