Contraction - Family of functions

Introduction

In large 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:

  1. Dead end contraction

  2. 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.

Dead end contraction

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

Dead end

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

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

When the conditions are true then the Operation: Dead End Contraction can be done.

The number of adjacent vertices is 1.
  • The green nodes are dead end nodes

  • The blue nodes have an unlimited number of incoming and outgoing edges.

Directed graph

digraph G {
    u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    w, z [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -> {u, v} [dir=none, weight=1, penwidth=3];
    u -> w -> u;
    v -> z;
}

Undirected graph

graph G {
    u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    w, z [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -- {u, v} [dir=none, weight=1, penwidth=3];
    u -- w [color=black];
    u -- w [color=darkgray];
    v -- z;
}
There are no outgoing edges and has at least one incoming edge.
  • The green nodes are dead end nodes

  • The blue nodes have an unlimited number of incoming and outgoing edges.

Directed graph

digraph G {
    u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    w, z [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -> {u, v} [dir=none, weight=1, penwidth=3];
    u -> w;
    v -> w;
    v -> z;
}
There are no incoming edges and has at least one outgoing edge.
  • The green nodes are dead end nodes

  • The blue nodes have an unlimited number of incoming and outgoing edges.

  • Considering that the nodes are dead starts nodes

Directed graph

digraph G {
    u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    w, z [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    {u, v} -> G [dir=none, weight=1, penwidth=3];
    w -> u;
    w -> v;
    z -> v;
}

Operation: Dead End Contraction

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

digraph G {
    u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    w [style=filled; color=green];
    "G" [shape=tripleoctagon;style=filled;color=deepskyblue; label = "Rest of the Graph"];

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

After contracting w , node v is now a dead end node and is contracted:

digraph G {
    u [shape=circle;style=filled;width=.4;color=deepskyblue];
    v [style=filled; color=green, label="v{w}"];
    "G" [shape=tripleoctagon;style=filled;color=deepskyblue; label = "Rest of the Graph"];

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

After contracting v , stop. Node u has the information of nodes that were contrcted.

digraph G {
    u [style=filled; color=green, label="u{v,w}"];
    "G" [shape=tripleoctagon;style=filled;color=deepskyblue; label = "Rest of the Graph"];

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

Node u has the information of nodes that were contracted.

Linear contraction

In the algorithm, linear contraction is represented by 2.

Linear

In case of an undirected graph, a node is considered a linear node when

In case of a directed graph, a node is considered a linear node when

The number of adjacent vertices is 2.
  • The green nodes are linear nodes

  • The blue nodes have an unlimited number of incoming and outgoing edges.

Directed

digraph G {
    u, c, a, w [shape=circle;style=filled;width=.4;color=deepskyblue];
    v, b [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    {w, c} -> G -> {u, a} [dir=none, weight=1, penwidth=3];
    u -> v -> w;
    a -> b -> c;
    c -> b -> a[color=darkgray];
}

Undirected

graph G {
    u, w [shape=circle;style=filled;width=.4;color=deepskyblue];
    v [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    w -- G -- u [dir=none, weight=1, penwidth=3];
    u -- v -- w;
}
Linearity is symmetrical

Using a contra example, vertex v is not linear because it’s not possible to go from w to u via v .

digraph G {
    u, w, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    {w} -> G -> {u} [dir=none, weight=1, penwidth=3];
    u -> v -> w -> v;
}

Operation: Linear Contraction

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

digraph G {
    u, z [shape=circle;style=filled;color=deepskyblue];
    v, w [style=filled; color=green];
    "G" [shape=tripleoctagon; style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -> {u, z} [dir=none, weight=1, penwidth=3];
    u -> v -> w -> z;
}

After contracting w ,

  • The vertex w is removed from the graph

    • The edges \(v \rightarrow w\) and \(w \rightarrow z\) are removed from the graph.

  • A new edge \(v \rightarrow z\) is inserted represented with red color.

digraph G {
    u, z [shape=circle;style=filled;color=deepskyblue];
    v [style=filled; color=green];
    "G" [shape=tripleoctagon; style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -> {u, z} [dir=none, weight=1, penwidth=3];
    u -> v;
    v -> z [label="{w}";color=red]
}

Contracting v :

  • The vertex v is removed from the graph

    • The edges \(u \rightarrow v\) and \(v \rightarrow z\) are removed from the graph.

  • A new edge \(u \rightarrow z\) is inserted represented with red color.

digraph G {
    u, z [shape=circle;style=filled;color=deepskyblue];
    "G" [shape=tripleoctagon; style=filled;color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -> {u, z} [dir=none, weight=1, penwidth=3];
    u -> z [label="{v, w}";color=red]
}

Edge \(u \rightarrow z\) has the information of nodes that were contracted.

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 .


do max_cycles times {
    for (operation in operations_order)
     { do operation }
}

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.

Construction of the graph in the database

Original Data

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

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

The original graph:

images/undirected_sampledata_a.png
Contraction Results

The results do not represent the contracted graph. They represent the changes done to the graph after applying the contraction algorithm.

Observe that vertices, for example, \(6\) do not appear in the results because it was not affected by the contraction algorithm.

SELECT * FROM pgr_contraction(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    array[1,2], directed:=false);
 type  id  contracted_vertices  source  target  cost
------+----+---------------------+--------+--------+------
 v      5  {7,8}                    -1      -1    -1
 v     15  {14}                     -1      -1    -1
 v     17  {16}                     -1      -1    -1
 e     -1  {1,2}                     3       5     2
 e     -2  {4}                       3       9     2
 e     -3  {10,13}                   5      11     2
 e     -4  {12}                      9      11     2
(7 rows)

After doing the dead end contraction operation:

images/undirected_sampledata_b.png

After doing the linear contraction operation to the graph above:

images/undirected_sampledata_c.png

The process to create the contraction graph on the database:

Add additional columns

Adding extra columns to the edge_table and edge_table_vertices_pgr tables, where:

Column

Description

contracted_vertices

The vertices set belonging to the vertex/edge

is_contracted

On the vertex table

  • when true the vertex is contracted, its not part of the contracted graph.

  • when false the vertex is not contracted, its part of the contracted graph.

is_new

On the edge table:

  • when true the edge was generated by the contraction algorithm. its part of the contracted graph.

  • when false the edge is an original edge, might be or not part of the contracted graph.

ALTER TABLE edge_table_vertices_pgr ADD is_contracted BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edge_table_vertices_pgr ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edge_table ADD is_new BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edge_table ADD contracted_vertices BIGINT[];
ALTER TABLE
Store contraction information

Store the contraction results in a table

SELECT * INTO contraction_results
FROM pgr_contraction(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    array[1,2], directed:=false);
SELECT 7
Update the vertices and edge tables

Update the vertex table using the contraction information

Use edge_table_vertices_pgr.is_contracted to 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

The modified edge_table_vertices_pgr .

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

Update the edge table using the contraction information

Insert the new edges generated by pgr_contraction.

INSERT INTO edge_table(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

The modified edge_table .

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

The contracted graph

Vertices that belong to the contracted graph.
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
ORDER BY id;
 id
----
  3
  5
  6
  9
 11
 15
 17
(7 rows)

Edges that belong to the contracted graph.
WITH
vertices_in_graph AS (
    SELECT id
    FROM edge_table_vertices_pgr
    WHERE is_contracted = false
)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edge_table
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
ORDER BY id;
 id  source  target  cost  reverse_cost  contracted_vertices
----+--------+--------+------+--------------+---------------------
  5       3       6     1            -1 
  8       5       6     1             1 
  9       6       9     1             1 
 11       6      11     1            -1 
 19       3       5     2            -1  {1,2}
 20       3       9     2            -1  {4}
 21       5      11     2            -1  {10,13}
 22       9      11     2            -1  {12}
(8 rows)

images/undirected_sampledata_c.png

Using the contracted graph

Using the contracted graph with pgr_dijkstra

There are three cases when calculating the shortest path between a given source and target in a contracted graph:

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

  • Case 2: Source and/or target belong to an edge subgraph.

  • Case 3: Source and/or target belong to a vertex.

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

Using the Edges that belong to the contracted graph. on lines 10 to 19.

 1CREATE OR REPLACE FUNCTION my_dijkstra(
 2    departure BIGINT, destination BIGINT,
 3    OUT seq INTEGER, OUT path_seq INTEGER,
 4    OUT node BIGINT, OUT edge BIGINT,
 5    OUT cost FLOAT, OUT agg_cost FLOAT)
 6RETURNS SETOF RECORD AS
 7$BODY$
 8SELECT * FROM pgr_dijkstra(
 9    $$
10    WITH
11    vertices_in_graph AS (
12        SELECT id
13        FROM edge_table_vertices_pgr
14        WHERE is_contracted = false
15    )
16    SELECT id, source, target, cost, reverse_cost
17    FROM edge_table
18    WHERE source IN (SELECT * FROM vertices_in_graph)
19    AND target IN (SELECT * FROM vertices_in_graph)
20    $$,
21    departure, destination, false);
22$BODY$
23LANGUAGE SQL VOLATILE;
24CREATE FUNCTION

Case 1

When both source and target belong to the contracted graph, a path is found.

SELECT * FROM my_dijkstra(3, 11);
 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

When source and/or target belong to an edge subgraph then a path is not found.

In this case, the contracted graph do not have an edge connecting with node \(4\) .

SELECT * FROM my_dijkstra(4, 11);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
(0 rows)

Case 3

When source and/or target belong to a vertex then a path is not found.

In this case, the contracted graph do not have an edge connecting with node \(7\) and of node \(4\) of the second case.

SELECT * FROM my_dijkstra(4, 7);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
(0 rows)

Case 2: Source and/or target belong to an edge subgraph.

Refining the above function to include nodes that belong to an edge.

  • The vertices that need to be expanded are calculated on lines 10 to 16.

  • Adding to the contracted graph that additional section on lines 25 to 27.

 1CREATE OR REPLACE FUNCTION my_dijkstra(
 2    departure BIGINT, destination BIGINT,
 3    OUT seq INTEGER, OUT path_seq INTEGER,
 4    OUT node BIGINT, OUT edge BIGINT,
 5    OUT cost FLOAT, OUT agg_cost FLOAT)
 6RETURNS SETOF RECORD AS
 7$BODY$
 8SELECT * FROM pgr_dijkstra(
 9    $$
10    WITH
11    edges_to_expand AS (
12        SELECT id
13        FROM edge_table
14        WHERE ARRAY[$$  departure  $$]::BIGINT[] <@ contracted_vertices
15           OR ARRAY[$$  destination  $$]::BIGINT[] <@ contracted_vertices
16    ),
17
18    vertices_in_graph AS (
19        SELECT id
20        FROM edge_table_vertices_pgr
21        WHERE is_contracted = false
22
23        UNION
24
25        SELECT unnest(contracted_vertices)
26        FROM edge_table
27        WHERE id IN (SELECT id FROM edges_to_expand)
28    )
29
30    SELECT id, source, target, cost, reverse_cost
31    FROM edge_table
32    WHERE source IN (SELECT * FROM vertices_in_graph)
33    AND target IN (SELECT * FROM vertices_in_graph)
34    $$,
35    departure, destination, false);
36$BODY$
37LANGUAGE SQL VOLATILE;
38CREATE FUNCTION

Case 1

When both source and target belong to the contracted graph, a path is found.

SELECT * FROM my_dijkstra(3, 11);
 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

When source and/or target belong to an edge subgraph, now, a path is found.

The routing graph now has an edge connecting with node \(4\) .

SELECT * FROM my_dijkstra(4, 11);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     4    16     1         0
   2         2     9    22     2         1
   3         3    11    -1     0         3
(3 rows)

Case 3

When source and/or target belong to a vertex then a path is not found.

In this case, the contracted graph do not have an edge connecting with node \(7\) .

SELECT * FROM my_dijkstra(4, 7);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
(0 rows)

Case 3: Source and/or target belong to a vertex.

Refining the above function to include nodes that belong to an edge.

  • The vertices that need to be expanded are calculated on lines 18 to 23.

  • Adding to the contracted graph that additional section on lines 38 to 40.

 1CREATE OR REPLACE FUNCTION my_dijkstra(
 2    departure BIGINT, destination BIGINT,
 3    OUT seq INTEGER, OUT path_seq INTEGER,
 4    OUT node BIGINT, OUT edge BIGINT,
 5    OUT cost FLOAT, OUT agg_cost FLOAT)
 6RETURNS SETOF RECORD AS
 7$BODY$
 8SELECT * FROM pgr_dijkstra(
 9    $$
10    WITH
11    edges_to_expand AS (
12        SELECT id
13        FROM edge_table
14        WHERE ARRAY[$$  departure  $$]::BIGINT[] <@ contracted_vertices
15           OR ARRAY[$$  destination  $$]::BIGINT[] <@ contracted_vertices
16    ),
17
18    vertices_to_expand AS (
19        SELECT id
20        FROM edge_table_vertices_pgr
21        WHERE ARRAY[$$  departure  $$]::BIGINT[] <@ contracted_vertices
22           OR ARRAY[$$  destination  $$]::BIGINT[] <@ contracted_vertices
23    ),
24
25    vertices_in_graph AS (
26        SELECT id
27        FROM edge_table_vertices_pgr
28        WHERE is_contracted = false
29
30        UNION
31
32        SELECT unnest(contracted_vertices)
33        FROM edge_table
34        WHERE id IN (SELECT id FROM edges_to_expand)
35
36        UNION
37
38        SELECT unnest(contracted_vertices)
39        FROM edge_table_vertices_pgr
40        WHERE id IN (SELECT id FROM vertices_to_expand)
41    )
42
43    SELECT id, source, target, cost, reverse_cost
44    FROM edge_table
45    WHERE source IN (SELECT * FROM vertices_in_graph)
46    AND target IN (SELECT * FROM vertices_in_graph)
47    $$,
48    departure, destination, false);
49$BODY$
50LANGUAGE SQL VOLATILE;
51CREATE FUNCTION

Case 1

When both source and target belong to the contracted graph, a path is found.

SELECT * FROM my_dijkstra(3, 11);
 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

The code change do not affect this case so when source and/or target belong to an edge subgraph, a path is still found.

SELECT * FROM my_dijkstra(4, 11);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     4    16     1         0
   2         2     9    22     2         1
   3         3    11    -1     0         3
(3 rows)

Case 3

When source and/or target belong to a vertex, now, a path is found.

Now, the routing graph has an edge connecting with node \(7\) .

SELECT * FROM my_dijkstra(4, 7);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     4     3     1         0
   2         2     3    19     2         1
   3         3     5     7     1         3
   4         4     8     6     1         4
   5         5     7    -1     0         5
(5 rows)

See Also

Indices and tables