pgr_contractGraph
— Performs graph contraction and returns the contracted vertices and edges.
Availability: 2.3.0
Warning
Experimental functions
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 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)
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)
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)
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 
Weight of the edge (source, target)


reverse_cost  ANYNUMERICAL 
1  Weight of the edge (target, source),

Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 

ANYNUMERICAL:  SMALLINT, INTEGER, BIGINT, REAL, FLOAT 
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 

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’. 
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