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) )

在循环中的每个运行中给出相同的结果。

但是，当重新启动内核并再次运行ning 单元格时，结果会更改为另一个子集。

Answer 1

您的问题的简短回答是：在当前的实现中它是不可重现的 - 如果考虑到内核的重启。

长答案

您需要使用OrderedGraph and re-implement the function maximal_independent_set using an OrderedSet (see Does Python have an ordered set?) to may ensure the reproducibility you are looking for. Alternatively to OrderedSets, you can ensure the ordering for the casts from the sets to the lists by sorting, see 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 并不能确保再现性，因为列表中元素的排序可能不同。

Networkx maximal_independent_set 再现性

Networkx maximal_independent_set reproducibility

numpy

networkx

reproducible-research

长答案

调试 - 基于 implementation