pgr_contraction  pgRouting Manual (3.4)
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

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