Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5 2.4 2.3

`pgr_contraction`¶

pgr_contraction — 执行图收缩操作并返回收缩后的顶点和边。

可用性

Version 3.8.0

新签名：
- 之前必需的参数 Contraction order 现在已变为可选参数，并更名为 methods 。
- 可选参数的新名称和顺序。
已弃用签名 pgr_contraction(text,bigint[],integer,bigint[],boolean)

版本3.0.0

结果列更改：删除了 seq
pgr_contractGraph 的名称更改
Bug修复
函数正式发布。

版本2.3.0

新实验性功能。

描述¶

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

主要特点是：

仅在具有正成本的边进行处理。
不返回完整的收缩图。
- 仅返回图中的变更部分。
返回值包括：
- 线性收缩生成的新边线集。
- 断头节点收缩生成的修改后顶点集。
返回值的排序如下：
- 列 id 升序排列。
- 列 id 中的负数，当它是一条新边时，负数依次递减。

目前，该功能包含两种收缩方法：
- 死角收缩。参考 pgr_contractionDeadEnd - 提议中。
- 线性收缩。参考 pgr_contractionLinear - 提议中。

Boost 图内部

签名¶

pgr_contraction(Edges SQL, [options])

options: [directed, methods, cycles, forbidden]

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

示例:: 在无向图上依次执行断头节点收缩与线性收缩。

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges', false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  4 | {2}                 |     -1 |     -1 |   -1
 v    |  7 | {1,3}               |     -1 |     -1 |   -1
 v    | 14 | {13}                |     -1 |     -1 |   -1
 e    | -1 | {5,6}               |      7 |     10 |    2
 e    | -2 | {8,9}               |      7 |     12 |    2
 e    | -3 | {17}                |     12 |     16 |    2
 e    | -4 | {15}                |     10 |     16 |    2
(7 rows)

参数¶

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

可选参数¶

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

可选收缩参数¶

列

类型

默认

描述

methods

INTEGER[]

ARRAY[1,2]

有序收缩操作。

1 = 死端收缩
2 = 线性收缩

cycles

INTEGER

$1$

收缩方法的执行次数。

forbidden

BIGINT[]

ARRAY[]::BIGINT[]

禁止收缩的顶点标识符。

内部查询¶

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`	行的类型。当该行表示一个顶点时，列为 `v` 。列 `id` 为正值。当行是边时，则为 `e` 。列 `id` 的值为负数。
`id`	`BIGINT`	此列中的所有数字都是 `DISTINCT` 当 `type` = 'v' 时。修改顶点的标识符。当 `type` = 'e' 时。从 -1 开始递减序列。表示未包含在原始边集中的伪`id` 。
`contracted_vertices`	`ARRAY[BIGINT]`	收缩顶点标识符数组。
`source`	`BIGINT`	当 `type` = 'v': $- 1$ 时当 `type` = 'e' 时：当前边 (`source`, `target`) 的source顶点标识符。
`target`	`BIGINT`	当 `type` = 'v': $- 1$ 时当 `type` = 'e' 时：当前边 (`source`, `target`) 的target 顶点标识符。
`cost`	`FLOAT`	当 `type` = 'v': $- 1$ 时当 `type` = 'e' 时：当前边 (`source`, `target`) 的权重。

其他示例¶

仅死端收缩 ¶

SELECT type, id, contracted_vertices FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  methods => ARRAY[1]);
 type | id | contracted_vertices
------+----+---------------------
 v    |  4 | {2}
 v    |  6 | {5}
 v    |  7 | {1,3}
 v    |  8 | {9}
 v    | 14 | {13}
(5 rows)

仅线性收缩 ¶

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  methods => ARRAY[2]);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {3}                 |      1 |      7 |    2
 e    | -2 | {3}                 |      7 |      1 |    2
(2 rows)

循环 ¶

对图进行收缩可通过多次操作实现，操作顺序会影响最终收缩图的结果——每执行一次操作后，可被后续操作收缩的顶点集合将发生变化。

这种实现方式在 methods 中循环 cycles 次。

<input>
do max_cycles times {
    for (operation in operations_order)
     { do operation }
}
<output>

收缩示例数据¶

在本节中，将通过示例展示构建和使用收缩图。

使用无向图的示例数据
首先是死端操作，然后是线性操作。

数据库中图的构建 ¶

原始图：

结果数据并非表示收缩后的图，而是反映应用收缩方法后需对原图执行的变更操作。

例如，观察到顶点 $6$ 没有出现在结果中，因为它不受收缩算法的影响。

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges', false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  4 | {2}                 |     -1 |     -1 |   -1
 v    |  7 | {1,3}               |     -1 |     -1 |   -1
 v    | 14 | {13}                |     -1 |     -1 |   -1
 e    | -1 | {5,6}               |      7 |     10 |    2
 e    | -2 | {8,9}               |      7 |     12 |    2
 e    | -3 | {17}                |     12 |     16 |    2
 e    | -4 | {15}                |     10 |     16 |    2
(7 rows)

进行死端收缩操作后：

对上图进行线性收缩运算后：

在数据库上创建收缩图的过程：¶

添加附加列 ¶

在边表和顶点表中添加额外列。在本文档中将使用以下内容：

Column.

描述

contracted_vertices

属于顶点/边的顶点集

is_contracted

在顶点表上

当 true 时，顶点收缩，它不是收缩图的一部分。
当 false 时，顶点不收缩，它是收缩图的一部分。

is_new

在边表上

当 true 时，边缘由收缩算法生成。它是收缩图的一部分。
当 false 时，边是原始边，可能是也可能不是收缩图的一部分。

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

存储收缩信息 ¶

将收缩结果存储至数据表。

SELECT * INTO contraction_results
FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges', false);
SELECT 7

更新边线与顶点表 ¶

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

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

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

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

插入由 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
WHERE type = 'e';
INSERT 0 4

收缩图 ¶

属于收缩图的顶点。

SELECT id FROM vertices WHERE is_contracted = false ORDER BY id;
 id
----
  4
  7
 10
 11
 12
 14
 16
(7 rows)

属于收缩图的边。

WITH
vertices_in_graph AS (SELECT id FROM vertices WHERE is_contracted = false)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edges
WHERE
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
  AND
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target)
ORDER BY id;
 id | source | target | cost | reverse_cost | contracted_vertices
----+--------+--------+------+--------------+---------------------
  5 |     10 |     11 |    1 |           -1 |
  8 |      7 |     11 |    1 |            1 |
  9 |     11 |     16 |    1 |            1 |
 11 |     11 |     12 |    1 |           -1 |
 19 |      7 |     10 |    2 |           -1 | {5,6}
 20 |      7 |     12 |    2 |           -1 | {8,9}
 21 |     12 |     16 |    2 |           -1 | {17}
 22 |     10 |     16 |    2 |           -1 | {15}
(8 rows)

视觉效果：

使用收缩图¶

根据最终应用的需求，图需要进行预处理。在本示例中，最终应用是使用收缩图通过 pgr_dijkstraCost 计算原始图中两个顶点之间的成本

计算收缩图中给定源和目标之间的最短路径时，存在三种情况：

情况1：源和目标都属于收缩图。
情况 2：源和/或目标属于边缘子图。
情况 3：源和/或目标属于一个顶点。

最终应用应考虑所有这些情况。

创建收缩图的视图（或表）：

DROP VIEW IF EXISTS contracted_graph;
NOTICE:  view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
SELECT id,source, target, cost, reverse_cost, contracted_vertices FROM edges
WHERE
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
  AND
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target);
CREATE VIEW

创建使用收缩图的函数。

CREATE OR REPLACE FUNCTION path_cost(source BIGINT, target BIGINT)
RETURNS SETOF FLOAT AS
$BODY$

SELECT agg_cost FROM pgr_dijkstraCost(
  /* The inner query */
  'WITH
  cul_de_sac AS (
    SELECT contracted_vertices || id::INTEGER as v
    FROM vertices WHERE ' || $1 ||' = ANY(contracted_vertices)
    OR ' || $2 ||' = ANY(contracted_vertices)),
  linears_to_expand AS (
    SELECT id, contracted_vertices
    FROM edges WHERE is_new AND (' || $1 ||' = ANY(contracted_vertices)
      OR '|| $2 ||'  = ANY(contracted_vertices))
  ),
  additional_vertices AS (
    SELECT * FROM cul_de_sac UNION SELECT contracted_vertices FROM linears_to_expand)
  SELECT id, source, target, cost, reverse_cost
  FROM edges, additional_vertices WHERE source = ANY(v) OR target = ANY(v)

  UNION

  SELECT id, source, target, cost, reverse_cost
  FROM contracted_graph LEFT JOIN linears_to_expand c USING (id) WHERE c.id IS NULL',

  source, target, false);

$BODY$ LANGUAGE SQL;
CREATE FUNCTION

情况1：源和目标都属于收缩图。

SELECT * FROM path_cost(10, 12);
 path_cost
-----------
         2
(1 row)

情况 2：源点和/或目标点位于含收缩顶点的边线上。

SELECT * FROM path_cost(15, 12);
 path_cost
-----------
         3
(1 row)

情况 3：源点和/或目标点属于已被收缩的顶点。

SELECT * FROM path_cost(15, 1);
 path_cost
-----------
         5
(1 row)

另请参阅¶

收缩 - 函数族

索引和表格

pgr_contraction¶

描述¶

签名¶

参数¶