pgr_contraction

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

Boost Graph Inside

Availability

• Version 3.0.0

  • Result 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

• Contraction - Family of functions

Indices and tables

• Index

• Search Page