Supported versions: latest (3.8) main dev

pgr_contractionLinear - 提议中

pgr_contractionLinear — 执行图收缩并返回收缩后的顶点和边线。

可用性

• Version 3.8.0

  • 新提议的函数。

描述

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

主要特点是：

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

• 不返回完整的收缩图。

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

• 返回值包括：

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

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

• 返回值的排序如下：

  • 列 id 升序排列。

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

Boost 图内部

签名

pgr_contractionLinear(Edges SQL, [options])

options: [directed, forbidden]

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

示例:

无向图上的线性收缩。

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)

• 绿色节点为线性节点，不属于收缩图的一部分。

  • 所有相邻边线均不纳入收缩图。

• 红线将成为收缩图的新边线。

参数

参数	类型	描述
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		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	当前边线的权重值。

其他示例

线性边

无向图

节点连接两条（或多条）"线性 "边，当

• 相邻顶点的数量为2。

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

• 相邻顶点的数量为2。

• 线性是对称的。

线性不对称

有向图

线性不对称的图形。

当图形作为有向图处理时，线性并不对称，因此图形无法收缩。

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)

无向图

当把同一图形作为无向图处理时，线性是对称的，因此图形可以收缩。

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)

三条边可以用一条无向边代替

• 边线 $1-3$。

  • 成本： $4$.

  • 边上的收缩顶点: $\{2\}$.

线性是对称的

有向图

线性对称的图形。

当图形作为有向图处理时，线性并不对称，因此图形无法收缩。

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)

四条边可以用两条有向边代替。

• 边线 $1-3$。

  • 成本： $4$.

  • 边上的收缩顶点: $\{2\}$.

• 边线 $3-1$.

  • 成本： $6$.

  • 边上的收缩顶点: $\{2\}$.

无向图

当把同一图形作为无向图处理时，线性是对称的，因此图形可以收缩。

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)

四条边线可替换为一条无向边。

• 边线 $1-3$。

  • 成本： $4$.

  • 边上的收缩顶点: $\{2\}$.

逐步线性收缩

线性收缩将在没有更多线性边时停止。例如，在下图中存在线性边

收缩顶点 $3$,

• 顶点 $3$ 已从图中移除

• 边线 $2\to 3$ 和 $w\to z$ 已从图中移除。

• 插入一条新边 $2\to 4$ ，用红色表示。

收缩顶点 $2$：

• 顶点 $2$ 已从图形中移除

• 从图中删除边 $1\to 2$ 和 $2\to 3$ 。

• 插入一条新边 $1\to 3$ ，用红色表示。

边线 $1\to 3$ 包含成本值及被收缩节点信息。

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)

创建收缩图

创建收缩图的步骤

添加额外的列。

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

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

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)

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

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

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)

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

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