博客 - 查找所有最小树 - 科学 Python 博客

在 GSoC 第一个编码阶段开始之前，只有一件事我需要弄清楚：如何找到图的所有最小树。这在 1970 年 Held 和 Karp 论文中是 $K(\pi)$ 集合，可以根据需要细化到 $K(\pi, d)$ 或 $K_{X, Y}(\pi)$。关于我为什么要做这件事的更多信息，请参阅我的上一篇文章这里.

这是我对 NetworkX 的贡献（我希望）对 NetworkX 社区其他成员有用的地方，我将为有向旅行商问题实现 Asadpour 算法 [1]。我将要使用的研究论文是 Sörensen 和 Janssens 于 2005 年发表的题为按递增成本生成图的所有生成树的算法[4]的论文这篇论文。

基本思想是实现他们的算法，然后生成生成树，直到我们找到第一个成本大于第一个生成的生成树的生成树，我们知道它是最小生成树，因此我们找到了所有最小生成树。我知道你们在想什么，“Matt，这篇论文讨论的是生成树，而不是生成树，这有什么用呢？”。好吧，该算法的核心是将顶点划分为互斥的边，即不能出现在树中的边，必须出现在树中的边以及可以出现在树中但不一定必须出现在树中的边。一旦我们有了分区，我们就需要能够找到一个尊重分区边的最小生成树或最小生成树。

在 NetworkX 中，最小生成树是使用 Chu-Liu/Edmonds 算法生成的，该算法由 Yoeng-Jin Chu 和 Tseng-Hong Liu 于 1965 年独立开发，并由 Jack Edmonds 于 1967 年独立开发。我相信 Edmonds 算法 [2] 可以修改为要求弧线必须包含在或排除在生成的生成树之外，从而使我能够为有向图实现 Sörensen 和 Janssens 的算法。

首先，让我们探索 Sörensen 和 Janssens 论文 [4] 中讨论的分区方案是否适用于有向图。创建分区的关键思想在第 221 页和第 222 页给出，如下所示

给定一个分区的 MST，这个分区可以被拆分成一组结果分区，使得以下陈述成立

任意两个结果分区的交集为空集，

原始分区的 MST 不是任何结果分区的元素，

结果分区的并集等于原始分区，减去原始分区的 MST。

为了实现这些条件，他们使用以下最小生成树的定义来定义分区的生成

$$ s(P) = {(i_1, j_1), \dots, (i_r, j_r), (t_1, v_1), \dots, (t_{n-r-1}, v_{n-r-1}} $$

其中 $(i, j)$ 边是原始分区的包含边，而 $(t, v)$ 来自原始分区的开放边。现在，为了创建下一组分区，依次取每个 $(t, v)$ 边，并逐个引入它们，在第一个出现的边中将该边设为排除边，并在所有后续分区中设为包含边。这将产生类似以下内容的结果

$$ \begin{array}{l} P_1 = {(i_1, j_1), \dots, (i_r, j_r), (\overline{m_1, p_1}), \dots, (\overline{m_l, p_l}), (\overline{t_1, v_1})} \\\ P_2 = {(i_1, j_1), \dots, (i_r, j_r), (t_1, v_1), (\overline{m_1, p_1}), \dots, (\overline{m_l, p_l}), (\overline{t_2, v_2})} \\\ P_3 = {(i_1, j_1), \dots, (i_r, j_r), (t_1, v_1), (t_2, v_2), (\overline{m_1, p_1}), \dots, (\overline{m_l, p_l}), (\overline{t_3, v_3})} \\\ \vdots \\\ \begin{multline*} P_{n-r-1} = {(i_1, j_1), \dots, (i_r, j_r), (t_1, v_1), \dots, (t_{n-r-2}, v_{n-r-2}), (\overline{m_1, p_1}), \dots, (\overline{m_l, p_l}), \\\ (\overline{t_{n-r-1}, v_{n-r-1}})} \end{multline*} \\\ \end{array} $$

现在，如果我们将它扩展到有向图，我们的包含边和排除边变成包含弧和排除弧，但分区的生成树的定义没有改变。设 $s_a(P)$ 为分区 $P$ 的最小生成树。那么

$$ s_a(P) = {(i_1, j_1), \dots, (i_r, j_r), (t_1, v_1), \dots, (t_{n-r-1}, v_{n-r-1}} $$

$s_a(P)$ 仍然由分区的所有包含弧和该分区开放弧的子集构成。如果我们按照 Sörensen 和 Janssens 论文 [4] 中的相同方式进行分区，那么不可能存在既包含又排除给定边的生成树，这种冲突存在于所有分区组合中。

显然，原始生成树包含所有 $(t_1, v_1), \dots, (t_{n-r-1}, v_{n-r-1})$，不能是任何结果分区的元素。

最后，还有一个说法是结果分区的并集是原始分区减去原始最小生成树。说实话，这个说法让我理解了好一阵子。事实上，我写了一整段话来谈论这个说法如何没有意义，然后突然意识到它确实有意义。这里要注意的重要一点是，所有分区的并集不是包含边和排除边集合的并集（这就是我第一次出错的地方），而是生成树的子集。原始分区包含许多生成树，其中一个或多个是最小的，但分区中的每棵树都是原始图边的一个唯一子集。现在，由于每个结果分区都不能包含原始分区最小生成树的边，我们知道原始最小生成树不是结果分区并集的元素。但是，由于原始分区中所有其他未被选为最小的生成树都至少与选定最小生成树相差一条边，因此它是至少一个结果分区的成员，特别是其中一条边为排除边的那个结果分区。

所以现在我们知道，这种适用于无向图的相同分区方案也适用于有向图。我们需要修改 Edmonds 算法，以强制包含某些弧线，并排除其他弧线。首先，需要回顾一下该算法。Jack Edmonds 于 1967 年在最佳分支[2]论文的第 234 页和第 235 页上给出了该算法的原始描述，大致说来，它包含三个主要步骤。

对于每个顶点 $v$，找到具有最小权重的传入弧，并将该弧放在桶 $E^i$ 中，并将顶点放在桶 $D^i$ 中。重复此步骤，直到 (a) $E^i$ 不再满足分支条件，或者 (b) 图的所有顶点都在 $D^i$ 中。如果 (a) 发生，则转到步骤 2，否则转到步骤 3。
如果 $E^i$ 不再满足分支条件，则它一定包含一个循环。将循环中的所有顶点收缩成一个新的顶点，比如 $v_1^{i + 1}$。每个端点在循环中的边都用 $v_1^{i + 1}$ 替换，并且成本更新。使用这个新的图 $G^{i + 1}$，创建包含 $G^{i + 1}$ 和 $D^i$ 中节点的桶 $D^{i + 1}$，以及包含 $G^{i + 1}$ 和 $E^i$ 中边的桶 $E^{i + 1}$（即，删除受 $G^{i + 1}$ 创建影响的边和顶点）。返回到步骤 1 并将其应用于图 $G^{i + 1}$。
一旦达到此步骤，我们就得到了一个较小的图，我们已经为其找到了最小生成树。现在我们需要展开所有循环以返回到原始图。为此，我们需要确定节点 $v_1^{i + 1}$ 是生成树的根还是不是。
- $v_1^{i + 1}$ 是根：从 $v_1^{i + 1}$ 代表的循环中删除具有最大权重的弧线。
- $v_1^{i + 1}$ 不是根：有一个指向 $v_1^{i + 1}$ 的单一弧线，它转化为一条指向 $v_1^{i + 1}$ 代表的循环中的一个顶点的弧线。由于 $v_1^{i + 1}$ 代表一个循环，因此还有另一个完全在循环内部的弧线指向与进入循环的边相同的顶点。删除内部的弧线以打破循环。重复此操作，直到原始图恢复。

现在我们已经熟悉了最小树算法，我们可以讨论如何修改它以强制包含某些边或拒绝其他边。更改将主要位于步骤 1 中。在算法的正常运行下，在每个顶点发生的考虑可能如下所示。

Edmonds algrithm selecting edge without restrictions

其中加粗箭头由算法选择，因为它是最小的传入弧。现在，如果我们需要包含不同的边，比如权重为 6 的边，即使它从严格意义上讲不是最优的，我们也希望这种行为。在类似的情况下，如果权重为 2 的边被排除，我们也希望选择权重为 6 的边。被排除的边下方是一条虚线。

Edmonds algorithm forces to picked a non-optimal arc

但实际上，这些都是例行公事，实现起来并不难。一个更有趣的情况是，如果所有弧线都被排除，或者不止一条弧线被包含。

Edmonds algorithm which cannot pick any arc

在这种情况下，由于图没有连接，因此分区不存在生成树。Sörensen 和 Janssens 论文将这些归类为空分区，并将它们忽略。

Edmonds algorithm which must pick more then one arc

在这种情况下，事情开始变得有点棘手。根据 Edmonds 在第 233 页的定义，如果两个（或更多）包含的弧指向同一个顶点，那么它就不是一个树状图。

分支是一个森林，其边是定向的，使得每条边都指向不同的节点。树状图是一个连通的分支。

起初我认为这种情况可能导致形成循环而有效，但现在我意识到，在 Edmonds 算法的步骤 3 中，其中一条弧会自动被移除。因此，根据定义，所有包含多个指向单个顶点的包含弧的划分都是空的。虽然算法可以处理多个弧的包含，但根据树状图的定义，其中一个（或多个）弧将在算法结束时被删除。

我建议在将数据传递给 Edmonds 算法以查找树状图之前，先对这些划分进行筛选。这样，Edmonds 算法需要修改，以适应每个顶点最多包含一条包含边和任意数量的排除边的场景。修改 Edmonds 算法的关键部分位于 NetworkX 实现中的 desired_edge 函数中，该函数从 algorithms.tree.branchings 中第 391 行开始。整个函数如下所示。

def desired_edge(v):
    """
    Find the edge directed toward v with maximal weight.

    """
    edge = None
    weight = -INF
    for u, _, key, data in G.in_edges(v, data=True, keys=True):
        new_weight = data[attr]
        if new_weight > weight:
            weight = new_weight
            edge = (u, v, key, new_weight)

    return edge, weight

该函数将被修改为自动返回一个包含的弧，然后跳过考虑任何排除的弧。由于这是一个内部函数，我们可以访问传递给父函数的参数，例如类似于 partition=None 的东西，其中 partition 的值是表示弧是否包含的边属性，如果包含则为 true，如果排除则为 false。开放边不需要此属性，或者可以使用 None。还可以创建一个枚举，如果我与 GSoC 导师讨论它如何融入 NetworkX 生态系统，那么它将统一语言。使用 true 和 false 方案的 desired_edge 的修改版本将如下所示

def desired_edge(v):
    """
    Find the edge directed toward v with maximal weight.

    """
    edge = None
    weight = -INF
    for u, _, key, data in G.in_edges(v, data=True, keys=True):
        new_weight = data[attr]
        if data[partition]:
            return edge, data[attr]
        if new_weight > weight and not data[partition]:
            weight = new_weight
            edge = (u, v, key, new_weight)

    return edge, weight

使用枚举的版本可能如下所示

def desired_edge(v):
    """
    Find the edge directed toward v with maximal weight.

    """
    edge = None
    weight = -INF
    for u, _, key, data in G.in_edges(v, data=True, keys=True):
        new_weight = data[attr]
        if data[partition] is Partition.INCLUDED:
            return edge, data[attr]
        if new_weight > weight and data[partition] is not Partition.EXCLUDED:
            weight = new_weight
            edge = (u, v, key, new_weight)

    return edge, weight

一旦 Edmonds 算法被修改以能够使用划分，来自 Sörensen 和 Janssens 论文的伪代码将适用。

Input: Graph G(V, E) and weight function w
Output: Output_File (all spanning trees of G, sorted in order of increasing cost)

List = {A}
Calculate_MST(A)
while MST ≠ ∅ do
	Get partition Ps in List that contains the smallest spanning tree
	Write MST of Ps to Output_File
	Remove Ps from List
	Partition(Ps)

相应的 Partition 函数为

P1 = P2 = P
for each edge i in P do
	if i not included in P and not excluded from P then
		make i excluded from P1
		make i include in P2
		Calculate_MST(P1)
		if Connected(P1) then
			add P1 to List
		P1 = P2

我需要更改第一个代码块的格式，因为它应该是一个 Python 迭代器，以便 for 循环能够遍历所有生成树，并在成本增加时停止，从而将其限制为仅最小生成树。

参考资料#

[1] A. Asadpour, M. X. Goemans, A. Mardry, S. O. Ghran，以及 A. Saberi，关于非对称旅行商问题的 O(log n / log log n) 近似算法，运筹学，65 (2017)，p. 1043-1061，https://homes.cs.washington.edu/~shayan/atsp.pdf.

[2] J. Edmonds，最佳分支，美国国家标准局研究杂志，1967，Vol. 71B，p.233-240，https://archive.org/details/jresv71Bn4p233

[3] M. Held，R.M. Karp，旅行商问题和最小生成树，运筹学，1970-11-01，Vol.18 (6)，p.1138-1162，https://www.jstor.org/stable/169411

[4] G.K. Janssens，K. Sörensen，按递增成本生成所有生成树的算法，Pesquisa Operacional，2005-08，Vol. 25 (2)，p. 219-229，https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en