pgr_contraction

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

_images/boost-inside.jpeg

Boost Graph Inside

Availability

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
     [, max_cycles] [, forbidden_vertices] [, directed])
RETURNS SETOF (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 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.
    • 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)