收缩 - 函数族¶
Warning
下一版本的拟议功能。
它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分:
这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
名字可能不会改变。(但仍然有可能改变)
签名可能不会改变。(但仍然有可能改变)
功能可能不会改变。(但仍然有可能改变)
pgTap 测试已经完成。 但可能需要更多。
文档可能需要完善。
介绍¶
在大型图中,例如道路图或电网,图收缩可用于加速某些图算法。 收缩通过删除一些顶点和边来减小图的大小,例如,可能会添加表示原始边序列的边,从而减少图算法中使用的总时间和空间。
该实现为将来添加收缩算法提供了灵活的框架,目前它支持两种算法:
死端收缩
线性收缩
允许用户:
禁止在一组节点上收缩。
决定收缩算法的顺序并设置它们要执行的最大次数。
线性收缩¶
算法中,线性收缩用2表示。
线性¶
在无向图的情况下,当满足以下条件时,节点被视为`线性`节点
相邻顶点的数量为2。
在有向图的情况下,当满足以下条件时,节点被视为`线性`节点
相邻顶点的数量为2。
线性是对称的
无向图上的线性顶点¶
绿色节点是 线性 节点
蓝色节点具有无限数量的传入和传出边缘。
无向
![graph G {
u, w [shape=circle;style=filled;width=.4;color=deepskyblue];
v [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;
color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
w -- G -- u [dir=none, weight=1, penwidth=3];
u -- v -- w;
}](_images/graphviz-9872665dd650fbe4b56184b4e266e5e885f76331.png)
节点 |
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\)
![digraph G {
u, v, w, x, y, z [shape=circle;style=filled;width=.4;color=deepskyblue];
a, b [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;
color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
{u, v} -> G -> {x, w, y, z} [dir=none, weight=1, penwidth=3];
u -> a -> v;
w -> b -> x;
x -> b -> w [color=darkgray];
y -> c -> z -> c;
}](_images/graphviz-0da6d285bf608f2fff32cc1bdf6e36ad07471c0e.png)
节点 |
Adjacent nodes |
相邻节点数 |
是对称的吗? |
---|---|---|---|
\(a\) |
\(\{u, v\}\) |
2 |
是 |
\(b\) |
\(\{w, x\}\) |
2 |
是 |
\(c\) |
\(\{y, z\}\) |
2 |
否 |
操作:线性收缩¶
当不再有线性节点时,线性收缩将停止。 例如,在下图中,其中 \(v\) 和 \(w\) 是 线性 节点:
![digraph G {
u, z [shape=circle;style=filled;color=deepskyblue];
v, w [style=filled; color=green];
"G" [shape=tripleoctagon; style=filled;
color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, z} [dir=none, weight=1, penwidth=3];
u -> v -> w -> z;
}](_images/graphviz-2d88b57dd1d5f0b63e43ffdfe4ae05ae0ac068c5.png)
收缩 \(w\),
顶点 \(w\) 已从图中移除
从图中删除边 \(v \rightarrow w\) 和 \(w \rightarrow z\)。
插入一条新边 \(v \rightarrow z\),以红色表示。
![digraph G {
u, z [shape=circle;style=filled;color=deepskyblue];
v [style=filled; color=green];
"G" [shape=tripleoctagon; style=filled;
color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, z} [dir=none, weight=1, penwidth=3];
u -> v;
v -> z [label="{w}";color=red]
}](_images/graphviz-daa8aad1710941b016da236c5d7f49e64bf04a5f.png)
收缩 \(v\):
顶点 \(v\) 已从图中移除
从图中删除边 \(u \rightarrow v\) 和 \(v \rightarrow z\)。
插入一条新边 \(u \rightarrow z\),以红色表示。
![digraph G {
u, z [shape=circle;style=filled;color=deepskyblue];
"G" [shape=tripleoctagon; style=filled;
color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, z} [dir=none, weight=1, penwidth=3];
u -> z [label="{v, w}";color=red]
}](_images/graphviz-8b01d503d415bd6cb722eee0eb0e9f10e481f0b2.png)
边 \(u \rightarrow z\) 有收缩点的信息。
另请参阅¶
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
索引和表格