Supported versions: latest (3.8) main dev

pgr_contractionLinear - Proposed

pgr_contractionLinear — Performs graph contraction and returns the contracted vertices and edges.

Availability

• Version 3.8.0

  • New proposed 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.

Boost Graph Inside

Signatures

pgr_contractionLinear(Edges SQL, [options])

options: [directed, max_cycles, forbidden_vertices]

Returns set of (type, id, contracted_vertices, source, target, cost)

Example:

Linear contraction on an undirected graph.

SELECT * FROM pgr_contractionLinear(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {3}                 |      1 |      7 |    2
 e    | -2 | {17}                |     12 |     16 |    2
 e    | -3 | {15}                |     10 |     16 |    2
(3 rows)

• The green nodes are linear nodes and will not be part of the contracted graph.

  • All edges adjacent will not be part of the contracted graph.

• The red lines will be new edges of the contracted graph.

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Edges SQL as described below.
contraction Order	ARRAY[ ANY-INTEGER ]	Ordered contraction operations. 1 = Dead end contraction 2 = Linear contraction

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
forbidden_vertices	ARRAY[ ANY-INTEGER ]	Empty	Identifiers of vertices forbidden for contraction.
max_cycles	INTEGER	$1$	Number of times the contraction operations on contraction_order will be performed.

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	Value = e indicating the row is an edge.
id	BIGINT	A pseudo id of the edge. All numbers on this column are DISTINCT Decreasing sequence starting from -1.
contracted_vertices	ARRAY[BIGINT]	Array of contracted vertex identifiers.
source	BIGINT	Identifier of the source vertex of the current edge.
target	BIGINT	Identifier of the target vertex of the current edge.
cost	FLOAT	Weight of the current edge.

Additional Examples

Linear edges

Undirected graph

A node connects two (or more) linear edges when

• The number of adjacent vertices is 2.

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

• The number of adjacent vertices is 2.

• Linearity is symmetrical.

Linearity is not symmetrical

Directed graph

Graph where linearity is not symmetrical.

When the graph is processed as a directed graph, linearity is not symmetrical, therefore the graph can not be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, -1),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
(0 rows)

Undirected graph

When the same graph is processed as an undirected graph, linearity is symmetrical, therefore the graph can be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, -1),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2}                 |      1 |      3 |    4
(1 row)

The three edges can be replaced by one undirected edge

• Edge $1-3$.

  • With cost: $4$.

  • Contracted vertices in the edge: $\{2\}$.

Linearity is symmetrical

Directed graph

Graph where linearity is symmetrical.

When the graph is processed as a directed graph, linearity is not symmetrical, therefore the graph can not be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, 2),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2}                 |      1 |      3 |    4
 e    | -2 | {2}                 |      3 |      1 |    6
(2 rows)

The four edges can be replaced by two directed edges.

• Edge $1-3$.

  • With cost: $4$.

  • Contracted vertices in the edge: $\{2\}$.

• Edge $3-1$.

  • With cost: $6$.

  • Contracted vertices in the edge: $\{2\}$.

Undirected graph

When the same graph is processed as an undirected graph, linearity is symmetrical, therefore the graph can be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, 2),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2}                 |      1 |      3 |    4
(1 row)

The four edges can be replaced by one undirected edge.

• Edge $1-3$.

  • With cost: $4$.

  • Contracted vertices in the edge: $\{2\}$.

Step by step linear contraction

The linear contraction will stop when there are no more linear edges. For example from the following graph there are linear edges

Contracting vertex $3$,

• The vertex $3$ is removed from the graph

• The edges $2\to 3$ and $w\to z$ are removed from the graph.

• A new edge $2\to 4$ is inserted represented with red color.

Contracting vertex $2$:

• The vertex $2$ is removed from the graph

• The edges $1\to 2$ and $2\to 3$ are removed from the graph.

• A new edge $1\to 3$ is inserted represented with red color.

Edge $1\to 3$ has the information of cost and the nodes that were contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1),
  (2, 2, 3, 1),
  (2, 3, 4, 1))
  AS edges(id,source,target,cost)$$);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2,3}               |      1 |      4 |    3
(1 row)

Creating the contracted graph

Steps for the creation of the contracted graph

Add additional columns.

ALTER TABLE vertices ADD is_contracted BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edges ADD is_new BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edges ADD contracted_vertices BIGINT[];
ALTER TABLE

Save results into a table.

SELECT * INTO contraction_results
FROM pgr_contractionLinear(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  directed => false);
SELECT 3

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 3

The contracted vertices are not part of the contracted graph.

SELECT id, is_contracted
FROM vertices WHERE is_contracted ORDER BY id;
 id | is_contracted
----+---------------
  3 | t
 15 | t
 17 | t
(3 rows)

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;
INSERT 0 3

Create the contracted graph.

CREATE VIEW contracted_graph AS
WITH
vertices_in_graph AS (
  SELECT id FROM vertices WHERE NOT is_contracted
)
SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
ORDER BY id;
CREATE VIEW

The contracted graph

SELECT * FROM contracted_graph ORDER by id;
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
  1 |      5 |      6 |    1 |            1
  2 |      6 |     10 |   -1 |            1
  4 |      6 |      7 |    1 |            1
  5 |     10 |     11 |    1 |           -1
  8 |      7 |     11 |    1 |            1
  9 |     11 |     16 |    1 |            1
 10 |      7 |      8 |    1 |            1
 11 |     11 |     12 |    1 |           -1
 12 |      8 |     12 |    1 |           -1
 14 |      8 |      9 |    1 |            1
 17 |      2 |      4 |    1 |            1
 18 |     13 |     14 |    1 |            1
 19 |      1 |      7 |    2 |           -1
 20 |     12 |     16 |    2 |           -1
 21 |     10 |     16 |    2 |           -1
(15 rows)

Using when departure and destination are in the contracted graph

SELECT *
FROM pgr_dijkstra('SELECT * FROM contracted_graph', 7, 16);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         7 |      16 |    7 |    8 |    1 |        0
   2 |        2 |         7 |      16 |   11 |    9 |    1 |        1
   3 |        3 |         7 |      16 |   16 |   -1 |    0 |        2
(3 rows)

Using when departure/destination is not in the contracted graph

SELECT * FROM pgr_dijkstra(
  'WITH in_line AS (SELECT contracted_vertices FROM edges WHERE 17 = ANY(contracted_vertices))
   SELECT id, source, target, cost, reverse_cost
   FROM edges, in_line
   WHERE source = ANY(in_line.contracted_vertices) OR target = ANY(in_line.contracted_vertices)

  UNION

  SELECT id, source, target, cost, reverse_cost FROM contracted_graph',
  1, 17);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         1 |      17 |    1 |   19 |    2 |        0
   2 |        2 |         1 |      17 |    7 |    8 |    1 |        2
   3 |        3 |         1 |      17 |   11 |    9 |    1 |        3
   4 |        4 |         1 |      17 |   16 |   15 |    1 |        4
   5 |        5 |         1 |      17 |   17 |   -1 |    0 |        5
(5 rows)

See Also

• Contraction - Family of functions

Indices and tables

• Index

• Search Page