pgr_contractGraph - Proposed¶

pgr_contractGraph — Performs graph contraction and returns the contracted vertices and edges.

Boost Graph Inside

Availability: 2.3.0

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

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 for dijkstra like functions¶

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