pgr_contraction

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

images/boost-inside.jpeg

Boost Graph Inside

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

    • 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

Indices and tables