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:
Allowing the user to:
In the algorithm, dead end contraction is represented by 1.
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.
Directed graph
Undirected graph
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:
After contracting w
, node v
is now a dead end node and is contracted:
After contracting v
, stop. Node u
has the information of nodes that were contrcted.
Node u
has the information of nodes that were contracted.
In the algorithm, linear contraction is represented by 2.
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
Directed
Undirected
Using a contra example, vertex v
is not linear because it’s not possible to
go from w
to u
via v
.
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:
After contracting w
,
w
is removed from the graphContracting v
:
v
is removed from the graphEdge \(u \rightarrow z\) has the information of nodes that were contracted.
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>
In this section, building and using a contracted graph will be shown by example.
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:
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:
After doing the linear contraction operation to the graph above:
The process to create the contraction graph on the database:
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
|
is_new | On the edge table:
|
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 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 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)
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
ORDER BY id;
id
----
3
5
6
9
11
15
17
(7 rows)
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)
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:
Using the Edges that belong to the contracted graph. on lines 10 to 19.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | CREATE OR REPLACE FUNCTION my_dijkstra(
departure BIGINT, destination BIGINT,
OUT seq INTEGER, OUT path_seq INTEGER,
OUT node BIGINT, OUT edge BIGINT,
OUT cost FLOAT, OUT agg_cost FLOAT)
RETURNS SETOF RECORD AS
$BODY$
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)
$$,
departure, destination, false);
$BODY$
LANGUAGE SQL VOLATILE;
CREATE 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)
Refining the above function to include nodes that belong to an edge.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | CREATE OR REPLACE FUNCTION my_dijkstra(
departure BIGINT, destination BIGINT,
OUT seq INTEGER, OUT path_seq INTEGER,
OUT node BIGINT, OUT edge BIGINT,
OUT cost FLOAT, OUT agg_cost FLOAT)
RETURNS SETOF RECORD AS
$BODY$
SELECT * FROM pgr_dijkstra(
$$
WITH
edges_to_expand AS (
SELECT id
FROM edge_table
WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
),
vertices_in_graph AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
UNION
SELECT unnest(contracted_vertices)
FROM edge_table
WHERE id IN (SELECT id 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)
$$,
departure, destination, false);
$BODY$
LANGUAGE SQL VOLATILE;
CREATE 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)
Refining the above function to include nodes that belong to an edge.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | CREATE OR REPLACE FUNCTION my_dijkstra(
departure BIGINT, destination BIGINT,
OUT seq INTEGER, OUT path_seq INTEGER,
OUT node BIGINT, OUT edge BIGINT,
OUT cost FLOAT, OUT agg_cost FLOAT)
RETURNS SETOF RECORD AS
$BODY$
SELECT * FROM pgr_dijkstra(
$$
WITH
edges_to_expand AS (
SELECT id
FROM edge_table
WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
),
vertices_to_expand AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
),
vertices_in_graph AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
UNION
SELECT unnest(contracted_vertices)
FROM edge_table
WHERE id IN (SELECT id FROM edges_to_expand)
UNION
SELECT unnest(contracted_vertices)
FROM edge_table_vertices_pgr
WHERE id IN (SELECT id FROM vertices_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)
$$,
departure, destination, false);
$BODY$
LANGUAGE SQL VOLATILE;
CREATE 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)
Indices and tables