Supported versions: latest (3.8) main dev

pgr_contractionDeadEnd - 提议中

pgr_contractionDeadEnd — 执行图收缩操作，并返回收缩后的顶点集与边线集。

Proposed

Warning

下一版本的提议功能。

• 它们并未正式出现在当前版本中。

• 它们可能会正式成为下一个版本的一部分：

  • 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL

  • 名字可能不会改变。（但仍然有可能改变）

  • 签名可能不会改变。（但仍然有可能改变）

  • 功能可能不会改变。（但仍然有可能改变）

  • pgTap 测试已经完成。 但可能需要更多。

  • 文档可能需要完善。

可用性

• Version 3.8.0

  • 新提议的函数。

描述

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

主要特点是：

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

• 不返回完整的收缩图。

  • 仅返回图中的变更部分。

• 返回值包括：

  • 线性收缩生成的新边线集。

  • 断头节点收缩生成的修改后顶点集。

• 返回值的排序如下：

  • 列 id 升序排列。

  • 列 id 中的负数，当它是一条新边时，负数依次递减。

在下列情况下，节点被视为断头节点：

• 在无向图上：

  • 相邻顶点的个数为1。

• 在有向图上：

  • 当只有一个相邻顶点或

  • 无论相邻顶点的数量多少，所有边都是进入的。

Boost 图内部

签名

pgr_contractionDeadEnd(Edges SQL, [options])

options: [directed, forbidden]

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

示例:

无向图的断头节点收缩。

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)

• 绿色节点为断头节点。

  • 节点 $3$ 是节点 $1$ 收缩后的死结节点。

参数

参数	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述。

可选参数

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

可选收缩参数

列	类型	默认	描述
forbidden	ARRAY[ ANY-INTEGER ]	Empty	禁止收缩的顶点标识符。

内部查询

Edges SQL

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		edge (source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：edge (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	值 = e 表示该行是一条边。
id	BIGINT	边线的伪 id。 此列中的所有数字都是 DISTINCT 从 -1 开始递减序列。
contracted_vertices	ARRAY[BIGINT]	收缩顶点标识符数组。
source	BIGINT	当前边的源顶点的标识符。
target	BIGINT	当前边的目标顶点的标识符。
cost	FLOAT	当前边线的权重值。

其他示例

无向图上的死端顶点

绿色节点为断头节点。

• 它们只有一个相邻节点。

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)

有向图上的死端顶点

• 绿色节点为断头节点

• 蓝色节点具有无限数量的传入和/或传出边缘。

节点	相邻节点	死端	Reason
$6$	$\{1\}$	是	只有一个相邻节点。
$7$	$\{2\}$	是	只有一个相邻节点。
$8$	$\{2,3\}$	是	有一个以上的相邻节点，且所有边都是传入的。
$9$	$\{4\}$	是	只有一个相邻节点。
$10$	$\{4,5\}$	No	有一个以上的相邻节点，且所有边都是向外的。
$1,2,3,4,5$	许多相邻节点。	No	有一个以上的相邻节点，有些边是入边，有些是出边。

从上面可以看出，节点 $\{6,7,9\}$ 是断头节点，因为其邻接顶点的数量为 1。

当有多个相邻顶点时，所有的边都必须是所有进入的边，否则就不是死胡同。

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)

逐步断头节点收缩

断头节点收缩将持续执行，直至图中不再存在断头节点。例如下图中 $3$ 为断头节点时的处理流程：

在收缩 $3$ 后，节点 $2$ 变成了断头节点，并被继续收缩：

收缩 $2$ 后，停止。节点 $1$ 包含已收缩节点的信息。

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)

创建收缩图

创建收缩图的步骤

添加额外的列。

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

将结果保存到表格中。

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

使用 is_contracted 列来指示收缩的顶点。

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

将属于顶点的结果信息填充至 contracted_vertices 表中。

UPDATE vertices
SET contracted_vertices = contraction_results.contracted_vertices
FROM contraction_results
WHERE type = 'v' AND vertices.id = contraction_results.id;
UPDATE 5

收缩后的顶点不包含在收缩图中。

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)

收缩图

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

当出发地和目的地位于收缩图中时使用

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)

当出发地/目的地不在收缩图中时使用

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)

当出发地和目的地均不在收缩图中时使用

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)

另请参阅

• 收缩 - 函数族

索引和表格

• Index

• Search Page