pgr_contraction

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

Boost 图内部

可用性

• 版本3.0.0

  • 结果列更改：删除了 seq

  • pgr_contractGraph 的名称更改

  • Bug修复

  • 官方 函数

• 版本2.3.0

  • 新 实验 函数

描述

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

主要特点是：

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

• 不返回完整的收缩图

  • 仅返回图上的更改

• 目前有两种类型的收缩方法

  • 死端收缩

  • 线性收缩

• 返回值包括

  • 由线性收缩添加的边。

  • 通过死端收缩修改顶点。

• 返回值的排序如下：

  • 当类型为 v``时，按列 ``id 升序

  • 当类型为 e 时，按列``id`` 降序

签名

总结

pgr_contraction 函数具有以下签名：

pgr_contraction(Edges SQL, contraction order, [options])

options: [ max_cycles, forbidden_vertices, directed]

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

示例:

在无向图上按顺序进行死端和线性收缩。

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[1, 2], directed => 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 如下所述。
contraction Order	ARRAY[ ANY-INTEGER ]	有序收缩操作。 1 = 死端收缩 2 = 线性收缩

可选参数

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

可选收缩参数

列	类型	默认	描述
forbidden_vertices	ARRAY[ ANY-INTEGER ]	Empty	禁止收缩的顶点标识符。
max_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	id 的类型。 当该行表示一个顶点时，列为 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',
  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',
  ARRAY[2]);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {3}                 |      1 |      7 |    2
 e    | -2 | {3}                 |      7 |      1 |    2
(2 rows)

另请参阅

• 收缩 - 函数族

索引和表格

• Index

• Search Page