pgr_contractionHierarchies - Experimental

pgr_contractionHierarchies — Performs graph contraction according to the contraction hierarchies method and returns the contracted vertices and shortcut edges created.

Availability

• Version 3.8.0

  • New experimental function

Description

The contraction hierarchies method builds, from an initial order of the vertices, a hierarchical order, giving priority to some vertices during the processing of label fixing of shortest paths algorithms. Furthermore, the contraction hierarchies algorithm adds shortcut edges in the graph, that helps the shortest paths algorithm to follow the created hierarchical graph structure.

The idea of the hierarchy is to put at a high priority level vertices that belong to the long distance network (highways for example in a road network) and to a low level of priority nodes that belong to the short distance network (arterials or secondary roads for example in road networks).

The contraction hierarchies algorithm makes the assumption that there is already a valuable vertices order that is used to initialize the contraction process. As in most cases there is no valuable initial node ordering, we use the order given by vertices ID. Then, the contraction process is made on the basis of this first order to give the final hierarchy.

The basic idea is to keep the vertices in a priority queue sorted by some estimate of how attractive is their contraction. The implemented case uses the metric called edge difference, which corresponds to the difference between the number of shortcuts produced by a vertex contraction and the number of incident edges in the graph before contraction (#shortcuts - #incident edges).

Finally, the aim is to reduce the explored part of the graph, when using a bidirectional Dijkstra-like algorithm. The vertices order is used to feed the oriented search. The search is made without losing optimality.

Finding an optimal vertices ordering for contraction is a difficult problem. Nevertheless, very simple local heuristics work quite well, according to Geisberger et al. [2]. The principle here is to a priori estimate the value of the edge difference and to contract the node at the top of the queue only if the new value of the metric keeps it at the top of the queue. Otherwise, it is reinserted in the queue, at its right place corresponding to the new metric value.

The process is done on graphs having only edges with positive costs.

It is necessary to remember that there are no deleted vertices with this function. At the end, the graph keeps every vertex it had, but has some added edges, corresponding to shortcuts. The vertices which have been contracted, to build the shortcut edges, are kept and hierarchically ordered.

As for the other contraction methods, it does not return the full contracted graph, only the changes. They are here of two types:

• added shortcut edges, with negative identifiers;

• contracted nodes with an order.

Boost Graph Inside

Signatures

Summary

The pgr_contractionHierarchies function has the following signature:

pgr_contractionHierarchies(Edges SQL, [options])

options: [directed, forbidden]

Returns set of (type, id, contracted_vertices, source, target, cost, metric, vertex_order)

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Edges SQL as described below.

Optional parameters

Column	Type	Default	Description
directed	BOOLEAN	true	When true the graph is considered Directed When false the graph is considered as Undirected.

Contraction hierarchies optional parameters

Column	Type	Default	Description
forbidden	ARRAY[ ANY-INTEGER ]	Empty	Identifiers of vertices forbidden for contraction.
directed	BOOLEAN	$1$	True if the graph is directed, False otherwise.

Inner Queries

Edges SQL

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)
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

Result columns

Returns set of (type, id, contracted_vertices, source, target, cost, metric, vertex_order)

The function returns many rows (one per vertex and one per shortcut edge created). The columns of the rows are:

Column	Type	Description
type	TEXT	Type of the id. v when the row is a vertex. Column id has a positive value e when the row is an edge. Column id has a negative value
id	BIGINT	All numbers on this column are DISTINCT When type = ‘v’. Identifier of the modified vertex. When type = ‘e’. Decreasing sequence starting from -1. Representing a pseudo id as is not incorporated in the set of original edges.
contracted_vertices	ARRAY[BIGINT]	Array of contracted vertex identifiers.
source	BIGINT	When type = ‘v’: $-1$ When type = ‘e’: Identifier of the source vertex of the current edge (source, target).
target	BIGINT	When type = ‘v’: $-1$ When type = ‘e’: Identifier of the target vertex of the current edge (source, target).
cost	FLOAT	When type = ‘v’: $-1$ When type = ‘e’: Weight of the current edge (source, target).
metric	BIGINT	When type = ‘v’: $-1$ When type = ‘e’: Weight of the current edge (source, target).
vertex_order	BIGINT	When type = ‘v’: $-1$ When type = ‘e’: Weight of the current edge (source, target).

Examples

On an undirected graph

The following query shows the original data involved in the contraction operation on an undirected graph.

SELECT id, source, target, cost FROM edges ORDER BY id;
 id | source | target | cost
----+--------+--------+------
  1 |      5 |      6 |    1
  2 |      6 |     10 |   -1
  3 |     10 |     15 |   -1
  4 |      6 |      7 |    1
  5 |     10 |     11 |    1
  6 |      1 |      3 |    1
  7 |      3 |      7 |    1
  8 |      7 |     11 |    1
  9 |     11 |     16 |    1
 10 |      7 |      8 |    1
 11 |     11 |     12 |    1
 12 |      8 |     12 |    1
 13 |     12 |     17 |    1
 14 |      8 |      9 |    1
 15 |     16 |     17 |    1
 16 |     15 |     16 |    1
 17 |      2 |      4 |    1
 18 |     13 |     14 |    1
(18 rows)

The original graph:

Example:

building contraction hierarchies on the whole graph

SELECT * FROM pgr_contractionHierarchies(
  'SELECT id, source, target, cost FROM edges',
  directed => false);
 type | id | contracted_vertices | source | target | cost | metric | vertex_order
------+----+---------------------+--------+--------+------+--------+--------------
 v    |  1 | {}                  |     -1 |     -1 |   -1 |     -1 |            3
 v    |  2 | {}                  |     -1 |     -1 |   -1 |     -1 |           10
 v    |  3 | {}                  |     -1 |     -1 |   -1 |     -1 |            4
 v    |  4 | {}                  |     -1 |     -1 |   -1 |      0 |           15
 v    |  5 | {}                  |     -1 |     -1 |   -1 |     -1 |           14
 v    |  6 | {}                  |     -1 |     -1 |   -1 |     -1 |            6
 v    |  7 | {}                  |     -1 |     -1 |   -1 |     -1 |            5
 v    |  8 | {}                  |     -1 |     -1 |   -1 |     -1 |            9
 v    |  9 | {}                  |     -1 |     -1 |   -1 |     -2 |            2
 v    | 10 | {}                  |     -1 |     -1 |   -1 |     -1 |            7
 v    | 11 | {}                  |     -1 |     -1 |   -1 |     -1 |            8
 v    | 12 | {}                  |     -1 |     -1 |   -1 |     -2 |            1
 v    | 13 | {}                  |     -1 |     -1 |   -1 |     -1 |           11
 v    | 14 | {}                  |     -1 |     -1 |   -1 |      0 |           16
 v    | 15 | {}                  |     -1 |     -1 |   -1 |     -1 |           13
 v    | 16 | {}                  |     -1 |     -1 |   -1 |     -1 |           12
 v    | 17 | {}                  |     -1 |     -1 |   -1 |      0 |           17
 e    | -1 | {7}                 |     11 |      8 |    2 |     -1 |           -1
 e    | -2 | {7,8}               |     11 |      9 |    3 |     -1 |           -1
 e    | -3 | {8}                 |     12 |      9 |    2 |     -1 |           -1
 e    | -4 | {11}                |     12 |     16 |    2 |     -1 |           -1
(21 rows)

The results do not represent the contracted graph. They represent the changes done to the graph after applying the contraction algorithm and give the vertex order built by the algorithm, by ordering vertices according to the edge difference metric. As a consequence, vertices are all represented in the result (except of course forbidden ones). Only shortcut built by the algorithm are represented in the result.

After computing the contraction hierarchies, an order is now given to the vertices,

in order to be used with a specific Dijkstra algorithm (implementation coming in a future version), which speeds up the search.

We obtain the contracted graph above:

We can see without surprise that the vertices belonging to the shortcuts have a tendency to have a high priority level in the resulting vertices order.

On an undirected graph with forbidden vertices

Example:

building contraction with a set of forbidden vertices

SELECT * FROM pgr_contractionHierarchies(
  'SELECT id, source, target, cost FROM edges',
  directed => false,
  forbidden => ARRAY[6]);
 type | id  | contracted_vertices | source | target | cost | metric | vertex_order
------+-----+---------------------+--------+--------+------+--------+--------------
 v    |   1 | {}                  |     -1 |     -1 |   -1 |     -1 |            4
 v    |   2 | {}                  |     -1 |     -1 |   -1 |     -1 |            8
 v    |   3 | {}                  |     -1 |     -1 |   -1 |     -1 |            5
 v    |   4 | {}                  |     -1 |     -1 |   -1 |      0 |           15
 v    |   5 | {}                  |     -1 |     -1 |   -1 |     -1 |           12
 v    |   7 | {}                  |     -1 |     -1 |   -1 |      0 |           13
 v    |   8 | {}                  |     -1 |     -1 |   -1 |     -1 |            7
 v    |   9 | {}                  |     -1 |     -1 |   -1 |     -3 |            1
 v    |  10 | {}                  |     -1 |     -1 |   -1 |     -1 |            6
 v    |  11 | {}                  |     -1 |     -1 |   -1 |      0 |           14
 v    |  12 | {}                  |     -1 |     -1 |   -1 |     -2 |            2
 v    |  13 | {}                  |     -1 |     -1 |   -1 |     -1 |            9
 v    |  14 | {}                  |     -1 |     -1 |   -1 |      0 |           16
 v    |  15 | {}                  |     -1 |     -1 |   -1 |     -1 |           11
 v    |  16 | {}                  |     -1 |     -1 |   -1 |     -2 |            3
 v    |  17 | {}                  |     -1 |     -1 |   -1 |     -1 |           10
 e    |  -1 | {7}                 |      6 |     11 |    2 |     -1 |           -1
 e    |  -2 | {7}                 |      6 |      8 |    2 |     -1 |           -1
 e    |  -3 | {7}                 |     11 |      8 |    2 |     -1 |           -1
 e    |  -4 | {7,8}               |      6 |      9 |    3 |     -1 |           -1
 e    |  -5 | {7,8}               |     11 |      9 |    3 |     -1 |           -1
 e    |  -6 | {8}                 |     12 |      9 |    2 |     -1 |           -1
 e    |  -7 | {7,11}              |      6 |     12 |    3 |     -1 |           -1
 e    |  -8 | {7,11}              |      6 |     16 |    3 |     -1 |           -1
 e    |  -9 | {11}                |     12 |     16 |    2 |     -1 |           -1
 e    | -10 | {7,11,12}           |      6 |     17 |    4 |     -1 |           -1
(26 rows)

Contraction process steps details

Shortcut building process

A vertex v is contracted by adding shortcuts replacing former paths of the form (u, v, w) by an edge (u, w). The shortcut (u, w) is only needed when (u, v, w) is the only shortest path between u and w.

When all shortcuts have been added for a given vertex v, the incident edges of v are removed and another vertex is contracted with the remaining graph.

The procedure is destructive for the graph and a copy is made to be able to manipulate it again as a whole. The contraction process adds all discovered shortcuts to the edge set E and attributes a metric to each contracted vertex. This metric is giving what is called the contraction hierarchy.

Initialize the queue with a first vertices order

For each vertex v of the graph, a contraction of v is built:

Node	Adjacent nodes
$v$	$\{p,r,u\}$
$p$	$\{u,v\}$
$u$	$\{p,v,w\}$
$r$	$\{v,w\}$
$w$	$\{r,u\}$

Adjacent edges are removed.

Shortcuts are built from predecessors of v to successors of v if and only if the path through v corresponds to the only shortest path between the predecessor and the successor of v in the graph. The edge difference metric here takes the value of -2.

Then the following vertex is contracted. The process goes on until each node of the graph has been contracted. At the end, there are no more edges in the graph, which has been destroyed by the process.

This first contraction will give a vertices order, given by ordering them in ascending order on the metric (edge difference). A total vertices order is built. If u < v, then u is less important than v. The algorithm keeps the vertices into a queue in this order.

A hierarchy will now be constructed by contracting again the vertices in this order.

Build the final vertex order

Once the first order built, the algorithm uses it to browse the graph once again. For each vertex taken in the queue, the algorithm simulates contraction and calculates its edge difference. If the computed value is greater than the one of the next vertex to be contracted, then the algorithm puts it back in the queue (heuristic approach). Otherwise it contracts it permanently.

Add shortcuts to the initial graph

At the end, the algorithm takes the initial graph (before edges deletions) and adds the shortcut edges to it. It gives you the contracted graph, ready to use with a specialized Dijkstra algorithm, which takes into account the order of the nodes in the hierarchy.

Use the contraction

Build the contraction

SELECT * INTO contraction_results
FROM pgr_contractionHierarchies(
  'SELECT id, source, target, cost FROM edges',
  directed => false);
SELECT 21

Add shortcuts and hierarchy in the existing tables

Add new columns in the vertices and edges tables to store the results:

ALTER TABLE edges
  ADD is_new BOOLEAN DEFAULT false,
  ADD contracted_vertices BIGINT[];
ALTER TABLE

ALTER TABLE vertices
  ADD metric INTEGER,
  ADD vertex_order INTEGER;
ALTER TABLE

Update and insert the results in the two tables.

INSERT INTO edges(source, target, cost, reverse_cost, contracted_vertices, is_new)
  SELECT source, target, cost, -1, contracted_vertices, true
  FROM contraction_results
  WHERE type = 'e';
INSERT 0 4

UPDATE vertices
  SET metric = c.metric, vertex_order = c.vertex_order
  FROM contraction_results c
  WHERE c.type = 'v' AND c.id = vertices.id;
UPDATE 17

Use a Dijkstra shortest path algorithm on it

Then you can use any Dijkstra-like algorithm, waiting for the adapted one which will take into account the built vertices hierarchy. For example:

SELECT * FROM pgr_bdDijkstra(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  1, 17
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    1 |    6 |    1 |        0
   2 |        2 |    3 |    7 |    1 |        1
   3 |        3 |    7 |    8 |    1 |        2
   4 |        4 |   11 |   11 |    1 |        3
   5 |        5 |   12 |   13 |    1 |        4
   6 |        6 |   17 |   -1 |    0 |        5
(6 rows)

See Also

• Contraction - Family of functions

Indices and tables

• Index

• Search Page