收缩 - 函数族

Warning

下一版本的拟议功能。

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

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

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

    • 名字可能不会改变。(但仍然有可能改变)

    • 签名可能不会改变。(但仍然有可能改变)

    • 功能可能不会改变。(但仍然有可能改变)

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

    • 文档可能需要完善。

介绍

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

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

  1. 死端收缩

  2. 线性收缩

允许用户:

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

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

线性收缩

算法中,线性收缩用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;
}

节点

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;
}

节点

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;
}

收缩 \(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]
}

收缩 \(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]
}

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

另请参阅

索引和表格