Unsupported versions:2.6 2.5 2.4 2.3
pgr_contraction
¶
pgr_contraction
— Performs graph contraction and returns the contracted
vertices and edges.
Availability
Version 3.8.0
New signature:
Previously compulsory parameter Contraction order is now optional with name
methods
.New name and order of optional parameters.
Deprecated signature pgr_contraction(text,bigint[],integer,bigint[],boolean)
Version 3.0.0
Result columns change:
seq
is removedName change from
pgr_contractGraph
Bug fixes
Function promoted to official.
Version 2.3.0
New experimental function.
Description¶
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.
The main Characteristics are:
Process is done only on edges with positive costs.
Does not return the full contracted graph.
Only changes on the graph are returned.
The returned values include:
The new edges generated by linear contraction.
The modified vertices generated by dead end contraction.
The returned values are ordered as follows:
column
id
ascending when its a modified vertex.column
id
with negative numbers descending when its a new edge.
Currently there are two types of contraction methods included in this function:
Dead End Contraction. See pgr_contractionDeadEnd - Proposed.
Linear Contraction. See pgr_contractionLinear - Proposed.
Signatures¶
[directed, methods, cycles, forbidden]
(type, id, contracted_vertices, source, target, cost)
- Example:
Dead end and linear contraction in that order on an undirected graph.
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges', false);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 4 | {2} | -1 | -1 | -1
v | 7 | {1,3} | -1 | -1 | -1
v | 14 | {13} | -1 | -1 | -1
e | -1 | {5,6} | 7 | 10 | 2
e | -2 | {8,9} | 7 | 12 | 2
e | -3 | {17} | 12 | 16 | 2
e | -4 | {15} | 10 | 16 | 2
(7 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
Optional parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
Contraction optional parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
|
Ordered contraction operations.
|
|
|
Number of times the contraction methods will be performed. |
|
|
|
|
Identifiers of vertices forbidden for contraction. |
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result columns¶
Returns set of (type, id, contracted_vertices, source, target, cost)
The function returns a single row. The columns of the row are:
Column |
Type |
Description |
---|---|---|
|
|
Type of the row.
|
|
|
All numbers on this column are
|
|
|
Array of contracted vertex identifiers. |
|
|
|
|
|
|
|
|
|
Additional Examples¶
Only dead end contraction¶
SELECT type, id, contracted_vertices FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges',
methods => ARRAY[1]);
type | id | contracted_vertices
------+----+---------------------
v | 4 | {2}
v | 6 | {5}
v | 7 | {1,3}
v | 8 | {9}
v | 14 | {13}
(5 rows)
Only linear contraction¶
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges',
methods => ARRAY[2]);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
e | -1 | {3} | 1 | 7 | 2
e | -2 | {3} | 7 | 1 | 2
(2 rows)
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 cycles
times through the methods
.
<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.
Construction of the graph in the database¶
The original graph:

The results do not represent the contracted graph. They represent the changes that need to be done to the graph after applying the contraction methods.
Observe that vertices, for example,
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges', false);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 4 | {2} | -1 | -1 | -1
v | 7 | {1,3} | -1 | -1 | -1
v | 14 | {13} | -1 | -1 | -1
e | -1 | {5,6} | 7 | 10 | 2
e | -2 | {8,9} | 7 | 12 | 2
e | -3 | {17} | 12 | 16 | 2
e | -4 | {15} | 10 | 16 | 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:¶
Add additional columns¶
Adding extra columns to the edges and vertices tables. In this documentation the following will be used:
Column. |
Description |
---|---|
|
The vertices set belonging to the vertex/edge |
|
On the vertex table
|
|
On the edge table
|
ALTER TABLE vertices
ADD is_contracted BOOLEAN DEFAULT false,
ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edges
ADD is_new BOOLEAN DEFAULT false,
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 edges', false);
SELECT 7
Update the edges and vertices tables¶
Use is_contracted
column to indicate the vertices that are contracted.
UPDATE vertices
SET is_contracted = true
WHERE id IN (SELECT unnest(contracted_vertices) FROM contraction_results);
UPDATE 10
Fill contracted_vertices
with the information from the results that belong
to the vertices.
UPDATE vertices
SET contracted_vertices = contraction_results.contracted_vertices
FROM contraction_results
WHERE type = 'v' AND vertices.id = contraction_results.id;
UPDATE 3
Insert the new edges generated by pgr_contraction.
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
The contracted graph¶
Vertices that belong to the contracted graph.
SELECT id FROM vertices WHERE is_contracted = false ORDER BY id;
id
----
4
7
10
11
12
14
16
(7 rows)
Edges that belong to the contracted graph.
WITH
vertices_in_graph AS (SELECT id FROM vertices WHERE is_contracted = false)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edges
WHERE
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
AND
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target)
ORDER BY id;
id | source | target | cost | reverse_cost | contracted_vertices
----+--------+--------+------+--------------+---------------------
5 | 10 | 11 | 1 | -1 |
8 | 7 | 11 | 1 | 1 |
9 | 11 | 16 | 1 | 1 |
11 | 11 | 12 | 1 | -1 |
19 | 7 | 10 | 2 | -1 | {5,6}
20 | 7 | 12 | 2 | -1 | {8,9}
21 | 12 | 16 | 2 | -1 | {17}
22 | 10 | 16 | 2 | -1 | {15}
(8 rows)
Visually:

Using the contracted graph¶
Depending on the final application the graph is to be prepared.
In this example the final application will be to calculate the cost from two
vertices in the original graph by using the contracted graph with pgr_dijkstraCost
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.
The final application should consider all of those cases.
Create a view (or table) of the contracted graph:
DROP VIEW IF EXISTS contracted_graph;
NOTICE: view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
SELECT id,source, target, cost, reverse_cost, contracted_vertices FROM edges
WHERE
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
AND
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target);
CREATE VIEW
Create the function that will use the contracted graph.
CREATE OR REPLACE FUNCTION path_cost(source BIGINT, target BIGINT)
RETURNS SETOF FLOAT AS
$BODY$
SELECT agg_cost FROM pgr_dijkstraCost(
/* The inner query */
'WITH
cul_de_sac AS (
SELECT contracted_vertices || id as v
FROM vertices WHERE ' || $1 ||' = ANY(contracted_vertices)
OR ' || $2 ||' = ANY(contracted_vertices)),
linears_to_expand AS (
SELECT id, contracted_vertices
FROM edges WHERE is_new AND (' || $1 ||' = ANY(contracted_vertices)
OR '|| $2 ||' = ANY(contracted_vertices))
),
additional_vertices AS (
SELECT * FROM cul_de_sac UNION SELECT contracted_vertices FROM linears_to_expand)
SELECT id, source, target, cost, reverse_cost
FROM edges, additional_vertices WHERE source = ANY(v) OR target = ANY(v)
UNION
SELECT id, source, target, cost, reverse_cost
FROM contracted_graph LEFT JOIN linears_to_expand c USING (id) WHERE c.id IS NULL',
source, target, false);
$BODY$ LANGUAGE SQL;
CREATE FUNCTION
Case 1: Both source and target belong to the contracted graph.
SELECT * FROM path_cost(10, 12);
path_cost
-----------
2
(1 row)
Case 2: Source and/or target belong to an edge that has contracted vertices.
SELECT * FROM path_cost(15, 12);
path_cost
-----------
3
(1 row)
Case 3: Source and/or target belong to a vertex that has been contracted.
SELECT * FROM path_cost(15, 1);
path_cost
-----------
5
(1 row)
See Also¶
Indices and tables