pgr_contractionHierarchies - Experimental

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

Disponibilidad

  • Versión 3.8.0

    • New experimental function

Descripción

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 Adentro: Boost Graph

Firmas

Resumen

The pgr_contractionHierarchies function has the following signature:

pgr_contractionHierarchies(Edges SQL, [options])
opciones: [directed, forbidden]
Returns set of (type, id, contracted_vertices, source, target, cost, metric, vertex_order)

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas descritas más adelante.

Parámetros opcionales

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido.

Contraction hierarchies optional parameters

Columna

Tipo

x Defecto

Descripción

forbidden

ARRAY[ ANY-INTEGER ]

vacío

Identificadores de vértices prohibidos para contracción.

directed

BOOLEAN

1

True if the graph is directed, False otherwise.

Consultas Internas

SQL aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados

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:

Columna

Tipo

Descripción

type

TEXT

Type of the id.

  • v cuando la fila es un vértice.

    • Column id has a positive value

  • e cuando la fila es una arista.

    • Column id has a negative value

id

BIGINT

Todos los números de esta columna son “”DISTINTOS””

  • En caso de type = “v”.

    • Identificador del vértice modificado.

  • En caso de type = “e”.

    • Disminución de la secuencia a partir de -1.

    • Representando un pseudo id como no incorporado en el conjunto de aristas originales.

contracted_vertices

ARRAY[BIGINT]

Arreglo de identificadores de vértices contraídos.

source

BIGINT

  • En caso de type = “v”: 1

  • En caso de type = “e”: Identificador del vétice de la arista actual (source, target).

target

BIGINT

  • En caso de type = “v”: 1

  • En caso de type = “e”: Identificador del vértice objetivo de la arista actual (source, target).

cost

FLOAT

  • En caso de type = “v”: 1

  • En caso de type = “e”: Peso de la arista actual (source, target).

metric

BIGINT

  • En caso de type = “v”: 1

  • En caso de type = “e”: Peso de la arista actual (source, target).

vertex_order

BIGINT

  • En caso de type = “v”: 1

  • En caso de type = “e”: Peso de la arista actual (source, target).

Ejemplos

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)

El grafo original:

_images/sample_graph.png
Ejemplo:

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:

_images/sample_graph_with_shortcuts.png

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

Ejemplo:

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:

graph G {
    p, r, u, w [shape=circle;style=filled;width=.4;color=deepskyblue];
    v [style=filled; color=green];

    rankdir=LR;
    v -- p [dir=both, weight=10, arrowhead=vee, arrowtail=vee, label="  10"];
    v -- r [dir=both, weight=3, arrowhead=vee, arrowtail=vee, label="  3"];
    v -- u [dir=both, weight=6, arrowhead=vee, arrowtail=vee, label="  6"];
    p -- u [dir=both, weight=16, arrowhead=vee, arrowtail=vee, label="  12"];
    r -- w [dir=both, weight=5, arrowhead=vee, arrowtail=vee, label="  5"];
    u -- w [dir=both, weight=5, arrowhead=vee, arrowtail=vee, label="  5"];
    p -- r [dir=both, weight=13, arrowhead=vee, arrowtail=vee, label="  13", style="invis"];
    u -- r [dir=both, weight=9, arrowhead=vee, arrowtail=vee, label="  9", style="invis"];
}

Nodo

Nodos adyacentes

v

{p,r,u}

p

{u,v}

u

{p,v,w}

r

{v,w}

w

{r,u}

Adjacent edges are removed.

graph G {
    p, r, u, w [shape=circle;style=filled;width=.4;color=deepskyblue];
    v [style=filled; color=green];

    rankdir=LR;
    v -- p [dir=both, weight=10, arrowhead=vee, arrowtail=vee, label="  10", style="invis"];
    v -- r [dir=both, weight=3, arrowhead=vee, arrowtail=vee, label="  3", style="invis"];
    v -- u [dir=both, weight=6, arrowhead=vee, arrowtail=vee, label="  6", style="invis"];
    p -- r [dir=both, weight=13, arrowhead=vee, arrowtail=vee, label="  13", color=red, style="invis"];
    u -- r [dir=both, weight=9, arrowhead=vee, arrowtail=vee, label="  9", color=red, style="invis"];
    p -- u [dir=both, weight=16, arrowhead=vee, arrowtail=vee, label="  12"];
    r -- w [dir=both, weight=5, arrowhead=vee, arrowtail=vee, label="  5"];
    u -- w [dir=both, weight=5, arrowhead=vee, arrowtail=vee, label="  5"];
}

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.

graph G {
    p, r, u, w [shape=circle;style=filled;width=.4;color=deepskyblue];
    v [style=filled; color=green];

    rankdir=LR;
    v -- p [dir=both, weight=10, arrowhead=vee, arrowtail=vee, label="  10", style="invis"];
    v -- r [dir=both, weight=3, arrowhead=vee, arrowtail=vee, label="  3", style="invis"];
    v -- u [dir=both, weight=6, arrowhead=vee, arrowtail=vee, label="  6", style="invis"];
    p -- r [dir=both, weight=13, arrowhead=vee, arrowtail=vee, label="  13", color=red];
    u -- r [dir=both, weight=9, arrowhead=vee, arrowtail=vee, label="  9", color=red];
    p -- u [dir=both, weight=16, arrowhead=vee, arrowtail=vee, label="  12"];
    r -- w [dir=both, weight=5, arrowhead=vee, arrowtail=vee, label="  5"];
    u -- w [dir=both, weight=5, arrowhead=vee, arrowtail=vee, label="  5"];
}

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)

Ver también

Índices y tablas