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

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

Example

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)