我在初步文章中所做的繁重工作在这里确实得到了回报！仅仅一天，我就实现了 sample_spanning_tree 及其两个辅助函数。
基尔霍夫定理#
这个函数实现起来非常容易。它完全遵循伪代码，并且在开始编写 sample_spanning_tree 之前就已经与 spanning_tree_distribution 一起工作了。
sample_spanning_tree#
这个函数比我最初预期的要困难。函数主体代码只需要进行少量调整即可适应 Python 的特性，例如 shuffle 是就地操作且返回 None，以及集合的一些细节。例如，在对 prepare_graph 进行调用之前，我将边 e 添加到 U 中，然后将 if 语句改为反向来从 U 中移除 e。这两部分的功能是相同的。我遇到的问题都源于连续收缩多个节点以及这对图的影响。
顺便说一句，NetworkX 中的 contracted_edge 函数是 contracted_node 的包装器，后者有一个 copy 关键字参数，前者函数假设该参数为 True。将此功能扩展到 contracted_edge 是一个微不足道的更改，但最终我使用了 contracted_node，所以整个事情都变得无关紧要了。
首先回顾一下边收缩，或者在本例中是节点收缩，是如何工作的。两个节点合并成一个节点，该节点由连接原始两个节点的相同边连接。这两个节点之间的边成为自环，但在本例中，我按照 Kulkarni 的指示阻止了自环的创建。如果一个未收缩的节点与这两个收缩节点都有边相连，我们会在它们之间插入一条平行边。我在一篇名为 熵分布 的上一篇文章中，曾与 NetworkX 图类相关的 API 纠结过。
对于 NetworkX 的实现，我们会调用 nx.contracted_nodes(G, u, v)，而 u 和 v 将始终合并到 u 中，因此 v 是不再存在于图中的节点。
现在想象一下，我们有三个要收缩的边，因为它们都在 U 中，如下所示。
如果我们从左到右处理这些边，我们首先收缩节点 0 和 1。此时，{1, 2} 不再存在于 G 中，因为节点 1 本身已被移除。但是，我们仍然需要收缩新的 {0, 2} 边，它等价于旧的 {1, 2} 边。
我第一次尝试解决这个问题的方法……很混乱，效果也不好。我开发了一个 if-elif 链，用于判断收缩边的端点是否不再存在于图中，并尝试使用字典推导来强制字典始终与哪些顶点彼此等价保持最新。它没有奏效，而且非常混乱。
幸运的是，有一个更好的解决方案。我实际上在上个学期的图算法课上第一次使用了这段代码。特别是它来自连通分量算法的合并查找或不相交集数据结构（代码可以 在这里 找到，有关数据结构的更多信息可以 在这里 找到）。
基本上，我们创建了一个从节点到该节点的代表的映射。在本例中，节点的代表是仍然在 G 中的节点，但输入节点已通过一系列收缩合并到该节点中。在上面的示例中，一旦节点 1 合并到节点 0 中，0 将成为节点 1 的代表。我们递归地在 merged_nodes 字典中搜索，直到找到一个不在字典中的节点，这意味着它仍然是它自己的代表，因此在图中。这将使我们能够稍后处理代表节点合并到另一个节点的情况。最后，我们利用路径压缩，以便随着 merged_nodes 中条目数量的增加，查找时间保持良好。
一旦我发现 prepare_graph 函数试图将节点与自身收缩的错误，这个方法就运行良好。但是，该函数正在运行并返回结果，但它可能比需要的多出一到两条边，这当然意味着它不是一棵树。顺便说一下，我正在对对称分数 Held Karp 图进行测试，因此对于六个节点，每棵树应该有五条边。
我为七条边结果之一的随机数生成器设置了种子，并开始调试！回想一下，一旦我们生成一个介于 0 和 1 之间的均匀十进制数，我们就将其与
$$ \lambda_e \times \frac{K_{G \backslash {e}}}{K_G} $$
进行比较，其中 K 是对下标图应用基尔霍夫定理的结果。一个引起我注意的概率的小数部分等于 1。这意味着将 e 添加到收缩边的集合中对该边是否应该包含在最终生成树中没有影响。仔细检查发现，问题中的边 e 实际上无法被选中用于生成树，因为它不存在于 G 中，因此它不可能存在于 G \ {e} 中。
想象一下以下情况。我们有三个要收缩的边，但它们形成了一个长度为三的环。
如果我们收缩 {0, 1} 然后收缩 {0, 2}，这对 {1, 2} 意味着什么？好吧，{1, 2} 将成为顶点 0 上的自环，但我们正在删除自环，因此它不能存在。它必须有 0 的概率。然而，在函数的当前实现中，它的概率将是 λ_{{1, 2}}。因此，我必须检查是否存在我们正在考虑的边的代表边，该边在主 for 循环的当前迭代中。
解决方案是将合并查找数据结构与 G 的准备好的图一起返回，然后检查是否存在一条边，其端点位于原始边端点的两个代表上。如果是，则像往常一样使用基尔霍夫值，但如果不是，则将 G_e_total_tree_weight 设置为零，以便无法选择此边。最后，我能够从 G 中一致地采样树，但它们是否与预期概率相符？
测试 sample_spanning_tree#
我正在使用的第一个测试采样了一棵树，并检查它是否确实是树。我首先将其扩展到采样 1000 棵树，并确保它们都是树。此时，我认为该函数将始终返回一棵树，但我需要检查树的分布。
因此，在编写测试本身以检查我采样的 75 棵可能的生成树中的哪一棵的过程中，我遇到了很多困难，然后我准备检查实际的分布。首先，测试迭代所有生成树，记录边权重的乘积并规范化数据。（请记住，实际概率仅与边权重的乘积成正比）。然后我采样 50000 棵树并记录实际频率。接下来，它计算预期概率与实际频率的百分比误差。样本量如此之大是因为在 1000 棵树时百分比误差到处都是，但是，正如大数定律所规定的那样，更大的样本显示实际结果收敛到预期结果，所以我相信该函数正在工作。
话虽如此，看到所有 75 棵生成树的百分比误差收敛到小于 15% 并不是一个非常严格的测试。我可以使用百分比误差实现正式测试，或者尝试使用 scipy 创建卡方检验。
更新！（2021 年 7 月 29 日）#
今天早上，我能够使卡方检验工作起来，这绝对是正确的决定。我能够将样本量从 50,000 减少到 1200，这是一个接近最小的样本。为了运行卡方检验，您需要所有类别的预期频率至少为 5，因此我必须找到样本数量以保证概率约为 0.4% 的树的预期频率至少为 5，该数字为 1163，我将其四舍五入为 1200。
我在 0.01 的显著性水平上进行测试，因此此测试可能会毫无理由地以 1% 的概率失败，但它仍然是一个总体上良好的分布检验。
参考文献#
A. Asadpour、M. X. Goemans、A. Mardry、S. O. Ghran 和 A. Saberi，《非对称旅行商问题的 o(log n / log log n) 近似算法》，SODA '10，工业与应用数学学会，2010 年，第 379-389 页，https://dl.acm.org/doi/abs/10.5555/1873601.1873633。
V. G. Kulkarni，《生成随机组合对象》，算法杂志，11（1990），第 185-207 页。