pgr_contractionLinear - Proposed

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

可用性

• Version 3.8.0

  • 新提议的函数。

描述

收缩通过移除部分顶点和边来减小图的大小，例如，可以添加代表原始边序列的边，从而减少图算法所用的总时间和空间。

主要特点是：

• 仅在具有正成本的边进行处理。

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

• 返回值的排序如下：

  • column id ascending when its a modified vertex.

  • column id with negative numbers descending when its a new edge.

Boost 图内部

签名

pgr_contractionLinear(Edges SQL, [options])

options: [directed, forbidden]

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

示例:

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.

参数

参数	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述。
contraction Order	ARRAY[ ANY-INTEGER ]	有序收缩操作。 1 = 死端收缩 2 = 线性收缩

可选参数

列	类型	默认	描述
directed	BOOLEAN	true	当 true 时，该图被视为有 有向 如果为 false ，则该图被视为 无向。

可选收缩参数

列	类型	默认	描述
forbidden	ARRAY[ ANY-INTEGER ]	Empty	禁止收缩的顶点标识符。
cycles	INTEGER	$1$	对 contraction_order 执行收缩操作的次数。

内部查询

Edges SQL

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		边(source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

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

该函数返回一行数据。该行的列包括：

列	类型	描述
type	TEXT	Value = e indicating the row is an edge.
id	BIGINT	A pseudo id of the edge. 此列中的所有数字都是 DISTINCT 从 -1 开始递减序列。
contracted_vertices	ARRAY[BIGINT]	收缩顶点标识符数组。
source	BIGINT	当前边的源顶点的标识符。
target	BIGINT	当前边的目标顶点的标识符。
cost	FLOAT	Weight of the current edge.

其他示例

线性边

无向图

A node connects two (or more) linear edges when

• 相邻顶点的数量为2。

在有向图的情况下，当满足以下条件时，节点被视为`线性`节点

• 相邻顶点的数量为2。

• Linearity is symmetrical.

Linearity is not symmetrical

有向图

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)

无向图

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\}$.

线性是对称的

有向图

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\}$.

无向图

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

使用 is_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)

插入由 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

收缩图

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)

另请参阅

• 收缩 - 函数族

索引和表格

• Index

• Search Page