`pgr_contraction`¶

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

可用性

Version 3.8.0

New signature:
- Previously compulsory parameter Contraction order is now optional with name methods.
- New name and order of optional parameters.
Deprecated signature pgr_contraction(text,bigint[],integer,bigint[],boolean)

版本3.0.0

结果列更改：删除了 seq
pgr_contractGraph 的名称更改
Bug修复
Function promoted to official.

版本2.3.0

New experimental function.

描述¶

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

主要特点是：

仅在具有正成本的边进行处理。
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.

Currently there are two types of contraction methods included in this function:
- Dead End Contraction. See pgr_contractionDeadEnd - Proposed.
- Linear Contraction. See pgr_contractionLinear - Proposed.

Boost Graph Inside

签名¶

pgr_contraction(Edges SQL, [options])

options: [directed, methods, cycles, forbidden]

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

示例:: Dead end and linear contraction in that order on an undirected graph.

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

Number of times the contraction methods will be performed.

forbidden

BIGINT[]

ARRAY[]::BIGINT[]

禁止收缩的顶点标识符。

内部查询¶

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`	Type of the row. 当该行表示一个顶点时，列为 `v`。 Column `id` has a positive value. 当行是边时，则为 `e`。 Column `id` has a negative value.
`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)

Contracting a graph can be done with more than one operation. The order of the operations affect the resulting contracted graph, after applying one operation, the set of vertices that can be contracted by another operation changes.

This implementation cycles cycles times through the methods .

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

收缩示例数据¶

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

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

数据库中图的构建 ¶

原始图：

The results do not represent the contracted graph. They represent the changes that need to be done to the graph after applying the contraction methods.

例如，观察到顶点 \(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)

进行死端收缩操作后：

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

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

添加附加列 ¶

Adding extra columns to the edges and vertices tables. In this documentation the following will be used:

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

存储收缩信息 ¶

Store the contraction results in a table.

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

Update the edges and vertices tables ¶

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

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

Fill contracted_vertices with the information from the results that belong to the 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)

Visually:

使用收缩图¶

Depending on the final application the graph is to be prepared. In this example the final application will be to calculate the cost from two vertices in the original graph by using the contracted graph with pgr_dijkstraCost

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

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

The final application should consider all of those cases.

Create a view (or table) of the contracted graph:

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 the function that will use the contracted graph.

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

Case 2: Source and/or target belong to an edge that has contracted vertices.

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

Case 3: Source and/or target belong to a vertex that has been contracted.

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

另请参阅¶

收缩 - 函数族

索引和表格

pgr_contraction¶

描述¶

签名¶

参数¶