pgr_contraction  pgRouting Manual (3.0)
pgr_contraction
pgr_contraction
 Performs graph contraction and returns the contracted vertices and edges.
Availability

Version 3.0.0

Return columns change:
seq
is removed 
Name change from
pgr_contractGraph

Bug fixes

Official function


Version 2.3.0

New experimental function

Support
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