Contraction - Family of functions - pgRouting Manual (2.5)
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
pgr_contractGraph - Experimental
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
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
After contracting C , node B is now a Dead End node and is contracted:
Node B gets contracted
Nodes B and C belong to node 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
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.
After contracting B , a new edge gets inserted between A and C which is represented by red color.
Node C is linear node and gets contracted.
Nodes B and C belong to edge connecting A and D which is represented by red color.
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.
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
----+---------------------+---------------
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)
- 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 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 9 3 2 -1 {4} t
21 5 11 2 -1 {10,13} t
22 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)
See Also
- http://www.cs.cmu.edu/afs/cs/academic/class/15210-f12/www/lectures/lecture16.pdf
- http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
- The queries use pgr_contractGraph - Experimental function and the Sample Data network.
Indices and tables