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 removed

• Name 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.

Boost Graph Inside

Signatures

pgr_contraction(Edges SQL, [options])

options: [directed, methods, cycles, forbidden]

Returns set of (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	TEXT	Edges SQL as described below.

Optional parameters

Column	Type	Default	Description
directed	BOOLEAN	true	When true the graph is considered Directed When false the graph is considered as Undirected.

Contraction optional parameters

Column	Type	Default	Description
methods	INTEGER[]	ARRAY[1,2]	Ordered contraction operations. 1 = Dead end contraction 2 = Linear contraction
cycles	INTEGER	$1$	Number of times the contraction methods will be performed.
forbidden	BIGINT[]	ARRAY[]::BIGINT[]	Identifiers of vertices forbidden for contraction.

Inner Queries

Edges SQL

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the edge.
source	ANY-INTEGER		Identifier of the first end point vertex of the edge.
target	ANY-INTEGER		Identifier of the second end point vertex of the edge.
cost	ANY-NUMERICAL		Weight of the edge (source, target)
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source) When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

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	TEXT	Type of the row. v when the row is a vertex. Column id has a positive value. e when the row is an edge. Column id has a negative value.
id	BIGINT	All numbers on this column are DISTINCT When type = ‘v’. Identifier of the modified vertex. When type = ‘e’. Decreasing sequence starting from -1. Representing a pseudo id as is not incorporated in the set of original edges.
contracted_vertices	ARRAY[BIGINT]	Array of contracted vertex identifiers.
source	BIGINT	When type = ‘v’: $-1$ When type = ‘e’: Identifier of the source vertex of the current edge (source, target).
target	BIGINT	When type = ‘v’: $-1$ When type = ‘e’: Identifier of the target vertex of the current edge (source, target).
cost	FLOAT	When type = ‘v’: $-1$ When type = ‘e’: Weight of the current edge (source, target).

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, $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 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
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 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

• Contraction - Family of functions

Indices and tables

• Index

• Search Page