numpy - Networkx maximal_independent_set 再现性

Question

如何在 Jupyter Notebook (Python3) 中获得可重现的结果？
为主要随机生成器定义种子似乎还不够，请参阅下面的 MWE:

import numpy as np
import random
import os 

random.seed(0)
np.random.seed(0)
os.environ['PYTHONHASHSEED']=str(0)

import networkx
from networkx.algorithms.mis import maximal_independent_set

G = networkx.Graph()
G.add_edges_from([ ('A', 'B'), ('B', 'C'), ('C', 'D'), ('D','E'), ('E','F'), ('A','E'), ('B','E') ])

for i in range(0,10):
   print( maximal_independent_set(G, seed=0) )

在循环中的每次运行中给出相同的结果。
但是，当重新启动内核并再次运行单元时，结果会更改为另一个子集。

Answer 1

您的问题的简短回答是:在当前的实现中，它是不可重现的——如果考虑到内核的重启。
长答案
您需要使用 OrderedGraph 并重新实现函数 maximal_independent_set使用 OrderedSet(请参阅 Does Python have an ordered set? )可以确保您正在寻找的可重复性。作为 OrderedSets 的替代方案，您可以通过排序来确保从集合到列表的强制转换的顺序，参见 here .
调试——基于implementation
问题的原因是什么。首先观察，它不是随机生成器。这是正确实例化的并且在多次运行中具有相同的状态(在开始和结束之后 - 检查 seed.getstate() 。maximal_independent_set 中的问题调用都是 set 操作。对于您的 mwe，例如:

neighbors = set.union(*[set(G.adj[v]) for v in nodes])
# next line added for simple debugging:
print(nodes, neighbors, G.adj["D"])
# Output 1: ['D', 'A', 'F']
# {'D'} {'E', 'C'} OrderedDict([('C', OrderedDict()), ('E', OrderedDict())])
# ['D', 'F', 'B']
# {'D'} {'C', 'E'} OrderedDict([('C', OrderedDict()), ('E', OrderedDict())])

如您所见，多次运行会导致不同的集合(相对于顺序)。这同样适用于其他种子，尤其是 available_nodes .因此，通过固定随机数生成器来固定所选列表 id 并不能确保可重复性，因为列表中元素的排序可能不同。