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 ANY-INTEGER and ANY-NUMERICAL
- 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

Boost Graph Inside

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	`ANY-INTEGER`		Identifier of the edge.
source	`ANY-INTEGER`		Identifier of the first end point vertex of the edge.
target	`ANY-INTEGER`		Identifier of the second end point vertex of the edge.
cost	`ANY-NUMERICAL`		Weight of the edge (source, target) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost	`ANY-NUMERICAL`	-1	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:	SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:	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[ANY-INTEGER]`	Ordered contraction operations. 1 = Dead end contraction 2 = Linear contraction
forbidden_vertices	`ARRAY[ANY-INTEGER]`	(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`	When `true` the graph is considered as Directed. When `false` the graph is considered as Undirected.

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`	Type of the id. ‘v’ when id is an identifier of a vertex. ‘e’ when id is an identifier of an edge.
id	`BIGINT`	Identifier of: the vertex when type = ‘v’. The vertex belongs to the edge_table passed as a parameter. the edge when type = ‘e’. The id is a decreasing sequence starting from -1. Representing a pseudo id as is not incorporated into the edge_table.
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

pgRouting Manual (2.3)