pgr_contraction¶
pgr_contraction
— Performs graph contraction and returns the contracted vertices and edges.
Availability
Version 3.0.0
Return columns change:
seq
is removedName 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 = 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[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)
Parameters¶
Column 
Type 
Description 

Edges SQL 

SQL query as described in Inner query 
Ccontraction Order 


Optional Parameters¶
Column 
Type 
Default 
Description 

forbidden_vertices 

Empty 
Identifiers of vertices forbidden from contraction. 
max_cycles 

\(1\) 
Number of times the contraction operations on contraction_order will be performed. 
directed 



Inner query¶
Column 
Type 
Default 
Description 

id 

Identifier of the edge. 

source 

Identifier of the first end point vertex of the edge. 

target 

Identifier of the second end point vertex of the edge. 

cost 

Weight of the edge (source, target)


reverse_cost 

1 
Weight of the edge (target, source),

Where:
 ANYINTEGER
SMALLINT, INTEGER, BIGINT
 ANYNUMERICAL
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 


id 


contracted_vertices 

Array of contracted vertex identifiers. 
source 


target 


cost 


Additional Examples¶
 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)
See Also¶
Indices and tables