Networkx maximal_independent_set reproducibility

Question

How can I get reproducible results in a Jupyter Notebook (Python3)?

Defining a seed for the main random generators seems to be not enough, see MWE below:

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

Gives the same result in each run in the loop.

However, when restarting the kernel and running the cells again, results change to another subset.

Results are reproducible within the same notebook run. However, when I restart the kernel, results change in a second run (see updated question) — simon, Dec 01 '20 at 12:36

score 2 · Accepted Answer · answered Dec 01 '20 at 14:43

The short answer for your question is: In the current implementation it is not reproducible - if taking restarts of kernel into account.

Long Answer

You need to use 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.

Debugging - based on the implementation

What is the cause of the problem. First observation, it's not the random generator. That is correctly instantiated and has the same state over multiple runs (At the beginning and after the end - check with seed.getstate(). The problematic calls within the maximal_independent_set are all set operations. For your mwe, for example:

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

As you see, multiple runs result into different sets (with respect to order). The same holds for the other seed, especially, available_nodes. Hence, fixing the selected list id by fixing the random number generator does not ensure reproducibility, since the sorting of the elements within the list can be different.

Thanks Sparky05. Indeed, by preserving the order when casting from sets to lists in the source code the reproducibility is achieved. — simon, Dec 01 '20 at 15:26

Networkx maximal_independent_set reproducibility

1 Answers1

Long Answer

Debugging - based on the implementation