Contraction - Family of functions¶

Warning

Experimental 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

Introduction¶

In big graphs, like the road graphs, or electric networks, graph contraction can be used to speed up some graph algorithms. 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.

This implementation gives a flexible framework for adding contraction algorithms in the future, currently, it supports two algorithms:

Dead end contraction

Linear contraction

Allowing the user to:

Forbid contraction on a set of nodes.

Decide the order of the contraction algorithms and set the maximum number of times they are to be executed.

Note

UNDER DISCUSSION: Forbid contraction on a set of edges

Dead end contraction¶

In the algorithm, dead end contraction is represented by 1.

Dead end nodes¶

The definition of a dead end node is different for a directed and an undirected graph.

In case of a undirected graph, a node is considered a dead end node if

The number of adjacent vertices is 1.

In case of an directed graph, a node is considered a dead end node if

There are no outgoing edges and has at least one incoming edge.

There is one incoming and one outgoing edge with the same identifier.

Examples

The green node B represents a dead end node
The node A is the only node connecting to B.
Node A is part of the rest of the graph and has an unlimited number of incoming and outgoing edges.
Directed graph

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=green];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
A -> B;
}

Operation: Dead End Contraction¶

The dead end contraction will stop until there are no more dead end nodes. For example from the following graph:

Node A is connected to the rest of the graph by an unlimited number of edges.
Node B is connected to the rest of the graph with one incoming edge.
Node B is the only node connecting to C.
The green node C represents a Dead End node

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=deepskyblue];
C [style=filled; color=green];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
A -> B;
B -> C;
}

After contracting C, node B is now a Dead End node and is contracted:

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=green;label="B {C}";];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
A -> B;
}

Node B gets contracted

digraph G {
A [style=filled;color=deepskyblue;label="A {B, C}";];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
}

Nodes B and C belong to node A.

Not Dead End nodes¶

In this graph B is not a dead end node.

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=red];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

G -> A [dir=none, weight=1, penwidth=3];
B -> A;
}

Linear contraction¶

In the algorithm, linear contraction is represented by 2.

Linear nodes¶

A node is considered a linear node if satisfies the following:

The number of adjacent vertices are 2.
Should have at least one incoming edge and one outgoing edge.

Examples

The green node B represents a linear node
The nodes A and C are the only nodes connecting to B.
Node A is part of the rest of the graph and has an unlimited number of incoming and outgoing edges.
Node C is part of the rest of the graph and has an unlimited number of incoming and outgoing edges.
Directed graph

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=green];
C [style=filled;color=deepskyblue];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
G -> C [dir=none, weight=1, penwidth=3];
A -> B;
B -> C;
}

Operation: Linear Contraction¶

The linear contraction will stop until there are no more linear nodes. For example from the following graph:

Node A is connected to the rest of the graph by an unlimited number of edges.
Node B is connected to the rest of the graph with one incoming edge and one outgoing edge.
Node C is connected to the rest of the graph with one incoming edge and one outgoing edge.
Node D is connected to the rest of the graph by an unlimited number of edges.
The green nodes B and C represents Linear nodes.

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=green];
C [style=filled; color=green];
D [style=filled; color=deepskyblue];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
G -> D [dir=none, weight=1, penwidth=3];
A -> B;
B -> C;
C -> D;

}

After contracting B, a new edge gets inserted between A and C which is represented by red color.

digraph G {
A [style=filled;color=deepskyblue];
C [style=filled; color=green];
D [style=filled; color=deepskyblue];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
G -> D [dir=none, weight=1, penwidth=3];
A -> C [label="{B}";color=red]
C -> D;

}

Node C is linear node and gets contracted.

digraph G {
A [style=filled;color=deepskyblue];
D [style=filled; color=deepskyblue];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
G -> D [dir=none, weight=1, penwidth=3];
A -> D [label="{B, C}";color=red];

}

Nodes B and C belong to edge connecting A and D which is represented by red color.

Not Linear nodes¶

In this graph B is not a linear node.

digraph G {
A [style=filled;color=deepskyblue];
B [style=filled; color=red];
C [style=filled;color=deepskyblue];
"G" [shape=tripleoctagon;
style=filled;color=deepskyblue;
label = "Rest of the Graph"];

rankdir=LR;
G -> A [dir=none, weight=1, penwidth=3];
G -> C [dir=none, weight=1, penwidth=3];
A -> B;
C -> B;
}

The cycle¶

Contracting a graph, can be done with more than one operation. The order of the operations affect the resulting contracted graph, after applying one operation, the set of vertices that can be contracted by another operation changes.

This implementation, cycles max_cycles times through operations_order .

<input>
do max_cycles times {
    for (operation in operations_order)
     { do operation }
}
<output>

Contracting Sample Data¶

In this section, building and using a contracted graph will be shown by example.

The Sample Data for an undirected graph is used
a dead end operation first followed by a linear operation.

The original graph:

After doing a dead end contraction operation:

Doing a linear contraction operation to the graph above

There are five cases, in this documentation, which arise when calculating the shortest path between a given source and target. In this examples, pgr_dijkstra is used.

Case 1: Both source and target belong to the contracted graph.
Case 2: Source belongs to a contracted graph, while target belongs to a edge subgraph.
Case 3: Source belongs to a vertex subgraph, while target belongs to an edge subgraph.
Case 4: Source belongs to a contracted graph, while target belongs to an vertex subgraph.
Case 5: The path contains a new edge added by the contraction algorithm.

Construction of the graph in the database¶

Original Data

The following query shows the original data involved in the contraction operation.

Contraction Results

SELECT * FROM pgr_contractGraph(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    array[1,2], directed:=true);
 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)

The above results do not represent the contracted graph. They represent the changes done to the graph after applying the contraction algorithm. We can see that vertices like 6 and 11 do not appear in the contraction results because they were not affected by the contraction algorithm.

step 1

Adding extra columns to the edge_table and edge_table_vertices_pgr tables:

Column	Description
contracted_vertices	The vertices set belonging to the vertex/edge
is_contracted	On a vertex table: when `true` the vertex is contracted, so is not part of the contracted graph.
is_contracted	On an edge table: when `true` the edge was generated by the contraction algorithm.

Using the following queries:

ALTER TABLE edge_table ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edge_table_vertices_pgr ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edge_table ADD is_contracted BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edge_table_vertices_pgr ADD is_contracted BOOLEAN DEFAULT false;
ALTER TABLE
SET client_min_messages TO NOTICE;
SET

step 2

For simplicity, in this documentation, store the results of the call to pgr_contractGraph in a temporary table

SELECT * INTO contraction_results
FROM pgr_contractGraph(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    array[1,2], directed:=true);
SELECT 7

step 3

Update the vertex and edge tables using the results of the call to pgr_contraction

In edge_table_vertices_pgr.is_contracted indicate the vertices that are contracted.

UPDATE edge_table_vertices_pgr
SET is_contracted = true
WHERE id IN (SELECT  unnest(contracted_vertices) FROM  contraction_results);
UPDATE 10

Add to edge_table_vertices_pgr.contracted_vertices the contracted vertices belonging to the vertices.

UPDATE edge_table_vertices_pgr
SET contracted_vertices = contraction_results.contracted_vertices
FROM contraction_results
WHERE type = 'v' AND edge_table_vertices_pgr.id = contraction_results.id;
UPDATE 3

Insert the new edges generated by pgr_contractGraph.

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

step 3.1

Verify visually the updates.

On the edge_table_vertices_pgr

SELECT id, contracted_vertices, is_contracted 
FROM edge_table_vertices_pgr
ORDER BY id;
 id | contracted_vertices | is_contracted 
----+---------------------+---------------
|                     | t
|                     | t
|                     | f
|                     | t
| {7,8}               | f
|                     | f
|                     | t
|                     | t
|                     | f
|                     | t
|                     | f
|                     | t
|                     | t
|                     | t
| {14}                | f
|                     | t
| {16}                | f
(17 rows)

On the edge_table

SELECT id, source, target, cost, reverse_cost, contracted_vertices, is_contracted 
FROM edge_table
ORDER BY id;
 id | source | target | cost | reverse_cost | contracted_vertices | is_contracted 
----+--------+--------+------+--------------+---------------------+---------------
|      1 |      2 |    1 |            1 |                     | f
|      2 |      3 |   -1 |            1 |                     | f
|      3 |      4 |   -1 |            1 |                     | f
|      2 |      5 |    1 |            1 |                     | f
|      3 |      6 |    1 |           -1 |                     | f
|      7 |      8 |    1 |            1 |                     | f
|      8 |      5 |    1 |            1 |                     | f
|      5 |      6 |    1 |            1 |                     | f
|      6 |      9 |    1 |            1 |                     | f
|      5 |     10 |    1 |            1 |                     | f
|      6 |     11 |    1 |           -1 |                     | f
|     10 |     11 |    1 |           -1 |                     | f
|     11 |     12 |    1 |           -1 |                     | f
|     10 |     13 |    1 |            1 |                     | f
|      9 |     12 |    1 |            1 |                     | f
|      4 |      9 |    1 |            1 |                     | f
|     14 |     15 |    1 |            1 |                     | f
|     16 |     17 |    1 |            1 |                     | f
|      3 |      5 |    2 |           -1 | {1,2}               | t
|      9 |      3 |    2 |           -1 | {4}                 | t
|      5 |     11 |    2 |           -1 | {10,13}             | t
|     11 |      9 |    2 |           -1 | {12}                | t
(22 rows)

vertices that belong to the contracted graph are the non contracted vertices

SELECT id  FROM edge_table_vertices_pgr
WHERE is_contracted = false
ORDER BY id;
 id 
----
  3
  5
  6
  9
 11
 15
 17
(7 rows)

case 1: Both source and target belong to the contracted graph.

Inspecting the contracted graph above, vertex 3 and vertex 11 are part of the contracted graph. In the following query:

vertices_in_graph hold the vertices that belong to the contracted graph.

when selecting the edges, only edges that have the source and the target in that set are the edges belonging to the contracted graph, that is done in the WHERE clause.

Visually, looking at the original graph, going from 3 to 11: 3 -> 6 -> 11, and in the contracted graph, it is also 3 -> 6 -> 11. The results, on the contracted graph match the results as if it was done on the original graph.

SELECT * FROM pgr_dijkstra(
    $$
    WITH
    vertices_in_graph AS (
        SELECT id  FROM edge_table_vertices_pgr WHERE is_contracted = false)
    SELECT id, source, target, cost, reverse_cost 
    FROM edge_table 
    WHERE source IN (SELECT * FROM vertices_in_graph)
    AND target IN (SELECT * FROM vertices_in_graph)
    $$,
    3, 11, false);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    3 |    5 |    1 |        0
   2 |        2 |    6 |   11 |    1 |        1
   3 |        3 |   11 |   -1 |    0 |        2
(3 rows)

case 2: Source belongs to the contracted graph, while target belongs to a edge subgraph.

Inspecting the contracted graph above, vertex 3 is part of the contracted graph and vertex 1 belongs to the contracted subgraph of edge 19. In the following query:

expand1 holds the contracted vertices of the edge where vertex 1 belongs. (belongs to edge 19).
vertices_in_graph hold the vertices that belong to the contracted graph and also the contracted vertices of edge 19.
when selecting the edges, only edges that have the source and the target in that set are the edges belonging to the contracted graph, that is done in the WHERE clause.

Visually, looking at the original graph, going from 3 to 1: 3 -> 2 -> 1, and in the contracted graph, it is also 3 -> 2 -> 1. The results, on the contracted graph match the results as if it was done on the original graph.

SELECT * FROM pgr_dijkstra(
    $$
    WITH
    expand_edges AS (SELECT id, unnest(contracted_vertices) AS vertex FROM edge_table),
    expand1 AS (SELECT contracted_vertices FROM edge_table
        WHERE id IN (SELECT id FROM expand_edges WHERE vertex = 1)),
    vertices_in_graph AS (
        SELECT id  FROM edge_table_vertices_pgr WHERE is_contracted = false
        UNION
        SELECT unnest(contracted_vertices) FROM expand1)
    SELECT id, source, target, cost, reverse_cost
    FROM edge_table
    WHERE source IN (SELECT * FROM vertices_in_graph)
    AND target IN (SELECT * FROM vertices_in_graph)
    $$,
    3, 1, false);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    3 |    2 |    1 |        0
   2 |        2 |    2 |    1 |    1 |        1
   3 |        3 |    1 |   -1 |    0 |        2
(3 rows)

case 3: Source belongs to a vertex subgraph, while target belongs to an edge subgraph.

Inspecting the contracted graph above, vertex 7 belongs to the contracted subgraph of vertex 5 and vertex 13 belongs to the contracted subgraph of edge 21. In the following query:

expand7 holds the contracted vertices of vertex where vertex 7 belongs. (belongs to vertex 5)

expand13 holds the contracted vertices of edge where vertex 13 belongs. (belongs to edge 21)

vertices_in_graph hold the vertices that belong to the contracted graph, contracted vertices of vertex 5 and contracted vertices of edge 21.

when selecting the edges, only edges that have the source and the target in that set are the edges belonging to the contracted graph, that is done in the WHERE clause.

Visually, looking at the original graph, going from 7 to 13: 7 -> 8 -> 5 -> 10 -> 13, and in the contracted graph, it is also 7 -> 8 -> 5 -> 10 -> 13. The results, on the contracted graph match the results as if it was done on the original graph.

SELECT * FROM pgr_dijkstra(
    $$
    WITH

    expand_vertices AS (SELECT id, unnest(contracted_vertices) AS vertex FROM edge_table_vertices_pgr),
    expand7 AS (SELECT contracted_vertices FROM edge_table_vertices_pgr
        WHERE id IN (SELECT id FROM expand_vertices WHERE vertex = 7)),

    expand_edges AS (SELECT id, unnest(contracted_vertices) AS vertex FROM edge_table),
    expand13 AS (SELECT contracted_vertices FROM edge_table
        WHERE id IN (SELECT id FROM expand_edges WHERE vertex = 13)),

    vertices_in_graph AS (
        SELECT id  FROM edge_table_vertices_pgr WHERE is_contracted = false
        UNION
        SELECT unnest(contracted_vertices) FROM expand13
        UNION
        SELECT unnest(contracted_vertices) FROM expand7)

    SELECT id, source, target, cost, reverse_cost
    FROM edge_table
    WHERE source IN (SELECT * FROM vertices_in_graph)
    AND target IN (SELECT * FROM vertices_in_graph)
    $$,
    7, 13, false);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    7 |    6 |    1 |        0
   2 |        2 |    8 |    7 |    1 |        1
   3 |        3 |    5 |   10 |    1 |        2
   4 |        4 |   10 |   14 |    1 |        3
   5 |        5 |   13 |   -1 |    0 |        4
(5 rows)

case 4: Source belongs to the contracted graph, while target belongs to an vertex subgraph.

Inspecting the contracted graph above, vertex 3 is part of the contracted graph and vertex 7 belongs to the contracted subgraph of vertex 5. In the following query:

expand7 holds the contracted vertices of vertex where vertex 7 belongs. (belongs to vertex 5)

vertices_in_graph hold the vertices that belong to the contracted graph and the contracted vertices of vertex 5.

when selecting the edges, only edges that have the source and the target in that set are the edges belonging to the contracted graph, that is done in the WHERE clause.

Visually, looking at the original graph, going from 3 to 7: 3 -> 2 -> 5 -> 8 -> 7, but in the contracted graph, it is 3 -> 5 -> 8 -> 7. The results, on the contracted graph do not match the results as if it was done on the original graph. This is because the path contains edge 19 which is added by the contraction algorithm.

SELECT * FROM  pgr_dijkstra(
    $$
    WITH
    expand_vertices AS (SELECT id, unnest(contracted_vertices) AS vertex FROM edge_table_vertices_pgr),
    expand7 AS (SELECT contracted_vertices FROM edge_table_vertices_pgr
        WHERE id IN (SELECT id FROM expand_vertices WHERE vertex = 7)),
    vertices_in_graph AS (
        SELECT id  FROM edge_table_vertices_pgr WHERE is_contracted = false
        UNION
        SELECT unnest(contracted_vertices) FROM expand7)
    SELECT id, source, target, cost, reverse_cost
    FROM edge_table
    WHERE source IN (SELECT * FROM vertices_in_graph)
    AND target IN (SELECT * FROM vertices_in_graph)
    $$,
    3, 7, false);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    3 |   19 |    2 |        0
   2 |        2 |    5 |    7 |    1 |        2
   3 |        3 |    8 |    6 |    1 |        3
   4 |        4 |    7 |   -1 |    0 |        4
(4 rows)

case 5: The path contains an edge added by the contraction algorithm.

In the previous example we can see that the path from vertex 3 to vertex 7 contains an edge which is added by the contraction algorithm.

WITH
first_dijkstra AS (
    SELECT * FROM  pgr_dijkstra(
        $$
        WITH
        expand_vertices AS (SELECT id, unnest(contracted_vertices) AS vertex FROM edge_table_vertices_pgr),
        expand7 AS (SELECT contracted_vertices FROM edge_table_vertices_pgr
            WHERE id IN (SELECT id FROM expand_vertices WHERE vertex = 7)),
        vertices_in_graph AS (
            SELECT id  FROM edge_table_vertices_pgr WHERE is_contracted = false
            UNION
            SELECT unnest(contracted_vertices) FROM expand7)
        SELECT id, source, target, cost, reverse_cost
        FROM edge_table
        WHERE source IN (SELECT * FROM vertices_in_graph)
        AND target IN (SELECT * FROM vertices_in_graph)
        $$,
        3, 7, false))
SELECT edge, contracted_vertices
    FROM first_dijkstra JOIN edge_table
    ON (edge = id)
    WHERE is_contracted = true;
 edge | contracted_vertices 
------+---------------------
   19 | {1,2}
(1 row)

Inspecting the contracted graph above, edge 19 should be expanded. In the following query:

first_dijkstra holds the results of the dijkstra query.

edges_to_expand holds the edges added by the contraction algorithm and included in the path.

vertices_in_graph hold the vertices that belong to the contracted graph, vertices of the contracted solution and the contracted vertices of the edges added by the contraction algorithm and included in the contracted solution.

when selecting the edges, only edges that have the source and the target in that set are the edges belonging to the contracted graph, that is done in the WHERE clause.

Visually, looking at the original graph, going from 3 to 7: 3 -> 2 -> 5 -> 8 -> 7, and in the contracted graph, it is also 3 -> 2 -> 5 -> 8 -> 7. The results, on the contracted graph match the results as if it was done on the original graph.

SELECT * FROM pgr_dijkstra($$
    WITH
    -- This returns the results from case 2
    first_dijkstra AS (
        SELECT * FROM  pgr_dijkstra(
            '
            WITH
            expand_vertices AS (SELECT id, unnest(contracted_vertices) AS vertex FROM edge_table_vertices_pgr),
            expand7 AS (SELECT contracted_vertices FROM edge_table_vertices_pgr
                WHERE id IN (SELECT id FROM expand_vertices WHERE vertex = 7)),
            vertices_in_graph AS (
                SELECT id  FROM edge_table_vertices_pgr WHERE is_contracted = false
                UNION
                SELECT unnest(contracted_vertices) FROM expand7)
            SELECT id, source, target, cost, reverse_cost
            FROM edge_table
            WHERE source IN (SELECT * FROM vertices_in_graph)
            AND target IN (SELECT * FROM vertices_in_graph)
            ',
            3, 7, false)),

    -- edges that need expansion and the vertices to be expanded.
    edges_to_expand AS (
        SELECT edge, contracted_vertices
        FROM first_dijkstra JOIN edge_table
        ON (edge = id)
        WHERE is_contracted = true),

    vertices_in_graph AS (
        -- the nodes of the contracted solution
        SELECT node FROM first_dijkstra
        UNION
        -- the nodes of the expanding sections
        SELECT unnest(contracted_vertices) FROM edges_to_expand)

    SELECT id, source, target, cost, reverse_cost
    FROM edge_table
    WHERE source IN (SELECT * FROM vertices_in_graph)
    AND target IN (SELECT * FROM vertices_in_graph)
    -- not including the expanded edges
    AND id NOT IN (SELECT edge FROM edges_to_expand)
    $$,
    3, 7, false);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    3 |    2 |    1 |        0
   2 |        2 |    2 |    4 |    1 |        1
   3 |        3 |    5 |    7 |    1 |        2
   4 |        4 |    8 |    6 |    1 |        3
   5 |        5 |    7 |   -1 |    0 |        4
(5 rows)