收缩 - 函数族

• pgr_contraction

Proposed

Warning

下一版本的拟议功能。

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

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

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

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

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

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

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

  • 文档可能需要完善。

• pgr_contractionDeadEnd - Proposed

介绍

在大型图中，例如道路图或电网，图收缩可用于加速某些图算法。 收缩通过删除一些顶点和边来减小图的大小，例如，可能会添加表示原始边序列的边，从而减少图算法中使用的总时间和空间。

该实现为将来添加收缩算法提供了灵活的框架，目前它支持两种算法：

1. 死端收缩

2. 线性收缩

允许用户：

• 禁止在一组节点上收缩。

• 决定收缩算法的顺序并设置它们要执行的最大次数。

线性收缩

算法中，线性收缩用2表示。

线性

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

• 相邻顶点的数量为2。

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

• 相邻顶点的数量为2。

• 线性是对称的

无向图上的线性顶点

• 绿色节点是 线性 节点

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

无向

节点	Adjacent nodes	相邻节点数
\(v\)	\(\{u, w\}\)	2

有向图上的线性顶点

• 绿色节点是 线性 节点

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

• The white node is not linear because the linearity is not symmetrical.

  • 它是可能去走 \(y \rightarrow c \rightarrow z\)

  • 不可能走 \(z \rightarrow c \rightarrow y\)

节点	Adjacent nodes	相邻节点数	是对称的吗？
\(a\)	\(\{u, v\}\)	2	是
\(b\)	\(\{w, x\}\)	2	是
\(c\)	\(\{y, z\}\)	2	否

操作：线性收缩

当不再有线性节点时，线性收缩将停止。 例如，在下图中，其中 \(v\) 和 \(w\) 是 线性 节点：

收缩 \(w\)，

• 顶点 \(w\) 已从图中移除

• 从图中删除边 \(v \rightarrow w\) 和 \(w \rightarrow z\)。

• 插入一条新边 \(v \rightarrow z\)，以红色表示。

收缩 \(v\)：

• 顶点 \(v\) 已从图中移除

• 从图中删除边 \(u \rightarrow v\) 和 \(v \rightarrow z\)。

• 插入一条新边 \(u \rightarrow z\)，以红色表示。

边 \(u \rightarrow z\) 有收缩点的信息。

另请参阅

• pgr_contraction

• 示例数据

• https://www.cs.cmu.edu/afs/cs/academic/class/15210-f12/www/lectures/lecture16.pdf

• https://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf

索引和表格

• Index

• Search Page