pgr_contraction
— Performs graph contraction and returns the contracted vertices and edges.
Availability
seq
is removedpgr_contractGraph
Support
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.
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[2]);
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)
Column  Type  Description 

Edges SQL  TEXT 
SQL query as described in Inner query 
Ccontraction Order  ARRAY[ANYINTEGER] 

Column  Type  Default  Description 

forbidden_vertices  ARRAY[ANYINTEGER] 
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 

Column  Type  Default  Description 

id  ANYINTEGER 
Identifier of the edge.  
source  ANYINTEGER 
Identifier of the first end point vertex of the edge.  
target  ANYINTEGER 
Identifier of the second end point vertex of the edge.  
cost  ANYNUMERICAL 
Weight of the edge (source, target)


reverse_cost  ANYNUMERICAL 
1  Weight of the edge (target, source),

Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 

ANYNUMERICAL:  SMALLINT, INTEGER, BIGINT, REAL, FLOAT 
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 

id  BIGINT 

contracted_vertices  ARRAY[BIGINT] 
Array of contracted vertex identifiers. 
source  BIGINT 

target  BIGINT 

cost  FLOAT 

Example:  Only dead end contraction 

SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[1]);
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[2]);
type  id  contracted_vertices  source  target  cost
+++++
e  1  {8}  5  7  2
e  2  {8}  7  5  2
(2 rows)