夏季代码课程的第一周即将结束，我在 NetworkX 中实现了两个新的但相关的功能。在这篇文章中，我将讨论我是如何实现它们的，一些挑战以及我如何测试它们。这两个新功能是生成树迭代器和生成树状图迭代器。
树状图迭代器是我将在我的 GSoC 项目中直接使用的功能，但我认为先实现生成树迭代器是个好主意，因为它更容易实现，并且我可以在需要时直接参考研究论文。这两个功能之间的分区方案是相同的，因此一旦我弄清楚了生成树，我所学到的东西就可以直接应用到树状图迭代器中，然后我就可以专注于修改 Edmonds 算法以尊重分区。
生成树迭代器#
这是第一个新功能。它遵循 Sörensen 和 Janssens 在 2005 年发表的一篇题为“An Algorithm to Generate all Spanning Trees of a Graph in Order of Increasing Cost”的论文中详细介绍的算法，该论文可以在 这里 [2] 找到。
现在，我需要调整算法的实现，因为我想实现一个 Python 迭代器，这样其他人就可以编写
for tree in nx.SpanningTreeIterator(G):
pass并且该循环将返回生成树，从成本最低的开始，一直到成本最高的。
为了实现此功能，我的第一步是确保一旦我知道图的边分区是什么，我就可以找到一个尊重分区的最小生成树。作为简要提醒，边分区创建了两个不相交的边集，其中一个边集必须出现在生成的生成树中，而另一个边集不能出现在生成树中。既不包含也不排除在生成树中的边称为开放边。
实现此目的最简单的算法是克鲁斯卡尔算法。包含的边首先全部添加到生成树中，然后算法可以使用开放边连接由包含边创建的组件。
这在 NetworkX 中很容易实现。NetworkX 中的克鲁斯卡尔算法是一个生成器，它使用一个排序的边列表一次返回一个最小生成树中的边。我所要做的就是更改排序过程，以便包含的边始终位于该列表的前面，然后算法将始终选择它们，而不管生成树的权重如何。
此外，由于图的一般生成树是分区树，其中分区没有包含或排除的边，因此我能够将正常的克鲁斯卡尔实现转换为我分区尊重实现的包装器，以减少冗余代码。
至于分区过程本身，这被证明有点棘手，主要是因为我自己的 Python 经验有限。（我从日历年的开始才开始使用 Python）为了实现分区方案，我需要一个有序的数据结构并选择了 PriorityQueue 类。这很方便，但对于具有相同最小生成树权重的元素，它尝试比较保存边数据的字典，这不是受支持的操作。因此，我实现了一个数据类，其中只有生成树的权重是可比较的。这意味着对于生成树权重的平局，具有该权重的最旧分区将首先被考虑。
一旦实现细节确定下来，我就开始进行测试。在撰写本文时，我已经在 Sörensen 和 Janssens 论文中的示例图上测试了 SpanningTreeIterator。该图是
它有八棵生成树，权重范围从 17 到 23，如下所示。
由于该图只有几棵生成树，因此很容易明确地测试迭代器返回的每个图是否都是序列中的下一个图。迭代器也可以向后工作，因此调用
for tree in nx.SpanningTreeIterator(G, minimum=False):
pass从最大生成树开始，一直到最小生成树。
生成树迭代器的代码可以在这里找到 这里，从大约第 761 行开始。
树状图迭代器#
树状图迭代器是我 GSoC 项目真正需要的，正如预期的那样，它实现起来更复杂。在我最初题为 查找所有最小树状图 的帖子中，我讨论了 Edmonds 算法 [1] 需要处理的情况，并建议对 desired_edge 方法进行更改。
这些更改很容易进行，但并非像我最初认为的那样只是需要进行的更改。Edmonds 1967 年论文中的原始图如下所示
在我的第一次测试中，它仅限于我创建的随机分区的最小生成树状图，结果非常接近。下面，蓝色边是包含边，红色边是被排除边。
最初的最小生成树状图如下所示。
虽然 $(3, 0)$ 边被正确排除，$(2, 3)$ 边被包含，但 $(6, 2)$ 不存在于树状图中（显示为虚线边）。追踪此问题很麻烦，但 Edmonds 算法的工作方式是，如果包含 $(6, 2)$ 边，则会存在一个循环，该循环会在算法移动到下一个迭代时折叠成单个顶点。一旦该循环折叠成一个顶点，它仍然必须选择如何访问该顶点，并且选择基于之前的最佳边（这是 [1] 中的步骤 I1）。然后，当算法展开循环时，它将删除边，该边
- 完全包含在循环内，并且
- 指向作为循环“访问点”的顶点。
在本例中，将是下一张图片中以红色显示的 $(6, 2)$。从视觉上表示，具有传入边的循环将如下所示
并且它将折叠成一个新顶点 $N$，从中将选择权重为 12 的传入边。
在此示例中，我们希望禁止算法选择权重为 12 的边，以便在重建循环时，包含边 $(6, 2)$ 仍然存在。一旦我们将其中一个传入边设为包含边，我们就可以从树状图的定义中得知，我们无法从任何其他边到达该顶点。它们实际上都被排除了，因此一旦我们找到一个指向顶点的包含边，我们就可以将所有其他传入边都排除。
回到示例，折叠的顶点 $N$ 将排除权重为 12 的边，并将选择权重为 13 的边。
此时，迭代器将找到 236 个树状图，成本范围从 96 到 125。我认为我非常接近完成，并且我知道最小生成树状图的成本为 96，直到我检查最大生成树状图的权重是什么：131。
这意味着我在将有效树状图添加到优先级队列之前就删除了包含有效树状图的分区。ArborescenceIterator 中的 check_partition 方法正在执行以下操作
- 计算每个顶点的包含和排除传入边的数量。
- 将所有包含边保存到一个列表中，以检查是否存在循环。
- 如果存在多个包含边或所有边都被排除，则返回
False。 - 如果存在一个包含边，则将所有其他边排除。
与其尝试调试我认为是好方法的内容，我决定更改我的过程。我将最后一个要点移到了 write_partition 方法中，然后停止使用 check_partition 方法。如果边分区没有生成树状图，partition_spanning_arborescence 函数将返回 None，我将丢弃该分区。这种方法在计算上更密集，但它将返回的生成树状图的数量从 236 增加到 680，并且范围扩展到正确的 96 - 131。
但是我如何知道它是否没有跳过该范围内的树状图？由于 680 个树状图太多，无法明确检查，我决定编写另一个测试用例。此用例将检查树状图的数量是否正确，以及序列是否从未减少。
为了检查树状图的数量，我决定采用蛮力方法。有
$$ \binom{18}{8} = 43,758 $$
边可能组合成树状图。这是一个很大的组合，比我想手动检查的要多，所以我编写了一个简短的 Python 脚本。
from itertools import combinations
import networkx as nx
edgelist = [
(0, 2),
(0, 4),
(1, 0),
(1, 5),
(2, 1),
(2, 3),
(2, 5),
(3, 0),
(3, 4),
(3, 6),
(4, 7),
(5, 6),
(5, 8),
(6, 2),
(6, 8),
(7, 3),
(7, 6),
(8, 7),
]
combo_count = 0
arbor_count = 0
for combo in combinations(edgelist, 8):
combo_count += 1
combo_test = nx.DiGraph()
combo_test.add_edges_from(combo)
if nx.is_arborescence(combo_test):
arbor_count += 1
print(
f"There are {combo_count} possible combinations of eight edges which "
f"could be an arboresecnce."
)
print(f"Of those {combo_count} combinations, {arbor_count} are arborescences.")此脚本的输出是
There are 43758 possible combinations of eight edges which could be an arboresecnce.
Of those 43758 combinations, 680 are arborescences.
所以现在我知道图中有多少个树状图，并且它与迭代器返回的数量匹配。因此，我相信迭代器工作良好。
迭代器代码位于 这里，从大约第 783 行开始。它可以像生成树迭代器一样使用。
附件 是迭代器的一个示例输出，详细说明了测试图的所有 680 个树状图。由于 Jekyll 不允许我上传 txt 文件，我不得不将其转换为 127 页的 pdf，以显示显示所有树状图的 6800 行输出。
参考文献#
[1] J. Edmonds，Optimum Branchings，美国国家标准局研究杂志，1967 年，第 71B 卷，第 233-240 页，https://archive.org/details/jresv71Bn4p233
[2] G.K. Janssens，K. Sörensen，An algorithm to generate all spanning trees in order of increasing cost，Pesquisa Operacional，2005-08，第 25 卷（2），第 219-229 页，https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en