pgr_contractionLinear - Proposed - pgRouting Manual (3.8)

Optional parameters

Contraction optional parameters

Edges SQL

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

ANY-NUMERICAL :

SMALLINT , INTEGER , BIGINT , REAL , FLOAT

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 \rightarrow 3\) and \(w \rightarrow z\) are removed from the graph.

• A new edge \(2 \rightarrow 4\) is inserted represented with red color.

Contracting vertex \(2\) :

• The vertex \(2\) is removed from the graph

• The edges \(1 \rightarrow 2\) and \(2 \rightarrow 3\) are removed from the graph.

• A new edge \(1 \rightarrow 3\) is inserted represented with red color.

Edge \(1 \rightarrow 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

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

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

UPDATE vertices
SET is_contracted = true
WHERE id IN (SELECT  unnest(contracted_vertices) FROM  contraction_results);
UPDATE 3

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

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 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)