Supported versions: latest (3.8) main dev

pgr_contractionDeadEnd - Proposed

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

Proposed

Warning

Proposed functions for next mayor release.

• They are not officially in the current release.

• They will likely officially be part of the next mayor release:

  • The functions make use of ANY-INTEGER and ANY-NUMERICAL

  • Name might not change. (But still can)

  • Signature might not change. (But still can)

  • Functionality might not change. (But still can)

  • pgTap tests have being done. But might need more.

  • Documentation might need refinement.

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.

A node is considered a dead end node when:

• On undirected graphs:

  • The number of adjacent vertices is 1.

• On directed graphs:

  • When there is only one adjacent vertex or

  • When all edges are incoming regardless of the number of adjacent vertices.

Boost Graph Inside

Signatures

pgr_contractionDeadEnd(Edges SQL, [options])

options: [directed, forbidden_vertices]

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

Example:

Dead end contraction on an undirected graph.

SELECT * FROM pgr_contractionDeadEnd(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  4 | {2}                 |     -1 |     -1 |   -1
 v    |  6 | {5}                 |     -1 |     -1 |   -1
 v    |  7 | {1,3}               |     -1 |     -1 |   -1
 v    |  8 | {9}                 |     -1 |     -1 |   -1
 v    | 14 | {13}                |     -1 |     -1 |   -1
(5 rows)

• The green nodes are dead end nodes.

  • Node $3$ is a dead end node after node $1$ is contracted.

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
forbidden_vertices	ARRAY[ ANY-INTEGER ]	Empty	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	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

Dead end vertex on undirected graph

The green nodes are dead end nodes.

• They have only one adjacent node.

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

Dead end vertex on directed graph

• The green nodes are dead end nodes

• The blue nodes have an unlimited number of incoming and/or outgoing edges.

Node	Adjacent nodes	Dead end	Reason
$6$	$\{1\}$	Yes	Has only one adjacent node.
$7$	$\{2\}$	Yes	Has only one adjacent node.
$8$	$\{2,3\}$	Yes	Has more than one adjacent node and all edges are incoming.
$9$	$\{4\}$	Yes	Has only one adjacent node.
$10$	$\{4,5\}$	No	Has more than one adjacent node and all edges are outgoing.
$1,2,3,4,5$	Many adjacent nodes.	No	Has more than one adjacent node and some edges are incoming and some are outgoing.

From above, nodes $\{6,7,9\}$ are dead ends because the total number of adjacent vertices is one.

When there are more than one adjacent vertex, all edges need to be all incoming edges otherwise it is not a dead end.

SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
  (1, 1, 6, 1, 1),
  (2, 2, 7, 1, -1),
  (3, 2, 8, 1, -1),
  (4, 3, 8, 1, -1),
  (5, 9, 4, 1, -1),
  (6, 10, 4, 1, 1),
  (7, 10, 5, 1, 1),
  /* Rest of the graph */
  (8, 1, 25, 1, 1), (9, 1, 26, 1, 1),
  (10, 2, 25, 1, 1), (11, 2, 26, 1, 1),
  (12, 3, 25, 1, 1), (13, 3, 26, 1, 1),
  (14, 4, 25, 1, 1), (15, 4, 26, 1, 1),
  (16, 5, 25, 1, 1), (17, 5, 26, 1, 1)) AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  1 | {6}                 |     -1 |     -1 |   -1
 v    |  2 | {7,8}               |     -1 |     -1 |   -1
 v    |  3 | {8}                 |     -1 |     -1 |   -1
 v    |  4 | {9}                 |     -1 |     -1 |   -1
(4 rows)

Step by step dead end contraction

The dead end contraction will stop until there are no more dead end nodes. For example, from the following graph where $3$ is the dead end node:

After contracting $3$, node $2$ is now a dead end node and is contracted:

After contracting $2$, stop. Node $1$ has the information of nodes that were contracted.

SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, -1),
  (2, 2, 3, 1, -1),
  /* Rest of the graph */
  (3, 1, 25, 1, 1), (4, 1, 26, 1, 1),
  (5, 25, 25, 1, 1), (6, 25, 26, 1, 1)) AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  1 | {2,3}               |     -1 |     -1 |   -1
(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 vertices ADD contracted_vertices BIGINT[];
ALTER TABLE

Save results into a table.

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

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 6

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 5

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
----+---------------
  1 | t
  2 | t
  3 | t
  5 | t
  9 | t
 13 | t
(6 rows)

The contracted graph

DROP VIEW IF EXISTS contracted_graph;
NOTICE:  view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
WITH
vertices_in_graph AS (
  SELECT id FROM vertices WHERE is_contracted = false
)
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

Using when departure and destination are in the contracted graph

SELECT *
FROM pgr_dijkstra('SELECT * FROM contracted_graph', 6, 17);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      17 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      17 |    7 |    8 |    1 |        1
   3 |        3 |         6 |      17 |   11 |   11 |    1 |        2
   4 |        4 |         6 |      17 |   12 |   13 |    1 |        3
   5 |        5 |         6 |      17 |   17 |   -1 |    0 |        4
(5 rows)

Using when departure/destination is not in the contracted graph

SELECT * FROM pgr_dijkstra(
  'WITH cul_de_sac AS (
    SELECT contracted_vertices || id as v
    FROM vertices WHERE 1 = ANY(contracted_vertices))
  SELECT id, source, target, cost, reverse_cost FROM edges, cul_de_sac
  WHERE source = ANY(v) AND target = ANY(v)

  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 |    6 |    1 |        0
   2 |        2 |         1 |      17 |    3 |    7 |    1 |        1
   3 |        3 |         1 |      17 |    7 |    8 |    1 |        2
   4 |        4 |         1 |      17 |   11 |    9 |    1 |        3
   5 |        5 |         1 |      17 |   16 |   15 |    1 |        4
   6 |        6 |         1 |      17 |   17 |   -1 |    0 |        5
(6 rows)

Using when departure and destination are not in the contracted graph

SELECT * FROM pgr_dijkstra(
  'WITH cul_de_sac AS (
    SELECT contracted_vertices || id as v
    FROM vertices WHERE 1 = ANY(contracted_vertices) OR 9 = ANY(contracted_vertices))
  SELECT id, source, target, cost, reverse_cost FROM edges, cul_de_sac WHERE source = ANY(v) AND target = ANY(v)

  UNION

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

See Also

• Contraction - Family of functions

Indices and tables

• Index

• Search Page