pgr_contractGraph  Proposed¶
pgr_contractGraph — Performs graph contraction and returns the contracted vertices and edges.
Warning
These are proposed functions
 They are not officially of the current release.
 They likely will not be officially be part of the next release:
 The functions might not make use of ANYINTEGER and ANYNUMERICAL
 Name might change.
 Signature might change.
 Functionality might change.
 pgTap tests might be missing.
 Might need c/c++ coding.
 May lack documentation.
 Documentation if any might need to be rewritten.
 Documentation examples might need to be automatically generated.
 Might need a lot of feedback from the comunity.
 Might depend on a proposed function of pgRouting
 Might depend on a deprecated function of pgRouting
Synopsis¶
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.
Characteristics¶
 The main Characteristics are:
 Process is done only on edges with positive costs.
 There are two types of contraction methods used namely,
 Dead End Contraction
 Linear Contraction
 The values returned include the added edges and contracted vertices.
 The returned values are ordered as follows:
 column id ascending when type = v
 column id descending when type = e
Signature Summary:¶
The pgr_contractGraph function has the following signatures:
pgr_contractGraph(edges_sql, contraction_order)
pgr_contractGraph(edges_sql, contraction_order, max_cycles, forbidden_vertices, directed)
RETURNS SETOF (seq, type, id, contracted_vertices, source, target, cost)
Signatures¶
Minimal signature¶
pgr_contractGraph(edges_sql, contraction_order)
Example:  Making a dead end contraction and a linear contraction. 

SELECT * FROM pgr_contractGraph(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[1, 2]);
seq  type  id  contracted_vertices  source  target  cost
++++++
1  v  5  {7,8}  1  1  1
2  v  15  {14}  1  1  1
3  v  17  {16}  1  1  1
4  e  1  {1,2}  3  5  2
5  e  2  {4}  9  3  2
6  e  3  {10,13}  5  11  2
7  e  4  {12}  11  9  2
(7 rows)
Complete signature¶
pgr_contractGraph(edges_sql, contraction_order, max_cycles, forbidden_vertices, directed)
Example:  Making a dead end contraction and a linear contraction and vertex 2 is forbidden from contraction 

SELECT * FROM pgr_contractGraph(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[1, 2], forbidden_vertices:=ARRAY[2]);
seq  type  id  contracted_vertices  source  target  cost
++++++
1  v  2  {1}  1  1  1
2  v  5  {7,8}  1  1  1
3  v  15  {14}  1  1  1
4  v  17  {16}  1  1  1
5  e  1  {4}  9  3  2
6  e  2  {10,13}  5  11  2
7  e  3  {12}  11  9  2
(7 rows)
Description of the edges_sql query¶
edges_sql:  an SQL query, which should return a set of rows with the following columns: 

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 


reverse_cost  ANYNUMERICAL  1 

Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 

ANYNUMERICAL:  SMALLINT, INTEGER, BIGINT, REAL, FLOAT 
Description of the parameters of the signatures¶
Column  Type  Description 

edges_sql  TEXT  SQL query as described above. 
contraction_order  ARRAY[ANYINTEGER] 

forbidden_vertices  ARRAY[ANYINTEGER]  (optional). Identifiers of vertices forbidden from contraction. Default is an empty array. 
max_cycles  INTEGER  (optional). Number of times the contraction operations on contraction_order will be performed. Default is 1. 
directed  BOOLEAN 

Description of the return values¶
RETURNS SETOF (seq, type, id, contracted_vertices, source, target, cost)
The function returns a single row. The columns of the row are:
Column  Type  Description 

seq  INTEGER  Sequential value starting from 1. 
type  TEXT 

id  BIGINT 

contracted_vertices  ARRAY[BIGINT]  Array of contracted vertex identifiers. 
source  BIGINT  Identifier of the source vertex of the current edge id. Valid values when type = ‘e’. 
target  BIGINT  Identifier of the target vertex of the current edge id. Valid values when type = ‘e’. 
cost  FLOAT  Weight of the edge (source, target). Valid values when type = ‘e’. 
Examples¶
Example:  Only dead end contraction 

SELECT * FROM pgr_contractGraph(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[1]);
seq  type  id  contracted_vertices  source  target  cost
++++++
1  v  2  {1}  1  1  1
2  v  5  {7,8}  1  1  1
3  v  10  {13}  1  1  1
4  v  15  {14}  1  1  1
5  v  17  {16}  1  1  1
(5 rows)
Example:  Only linear contraction 

SELECT * FROM pgr_contractGraph(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2]);
seq  type  id  contracted_vertices  source  target  cost
++++++
1  e  1  {4}  9  3  2
2  e  2  {8}  5  7  2
3  e  3  {8}  7  5  2
4  e  4  {12}  11  9  2
(4 rows)
Indices and tables