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 isv
column
id
descending when type ise
Signatures¶
Summary
The pgr_contraction function has the following signature:
[ max_cycles, forbidden_vertices, directed]
(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 as described below. 

contraction Order 

Ordered contraction operations.

Optional Parameters¶
Column 
Type 
Default 
Description 





Contraction optional parameters¶
Column 
Type 
Default 
Description 



Empty 
Identifiers of vertices forbidden for contraction. 


\(1\) 
Number of times the contraction operations on 
Inner Queries¶
Edges SQL¶
Column 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge ( 


ANYNUMERICAL 
1 
Weight of the edge (

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



All numbers on this column are



Array of contracted vertex identifiers. 









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