Upgrade networkx to 2.2, add self tests, and update random seed format

[tmonteil]

Note that self tests require nose which is optional only.

Also, the random seeds are not passed as integers, but as random.Random instances, see ​https://networkx.github.io/documentation/stable/release/release_2.2.html#improvements

Zipball: ​https://files.pythonhosted.org/packages/f3/f4/7e20ef40b118478191cec0b58c3192f822cace858c19505c7670961b76b2/networkx-2.2.zip

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9a7dff8

#26326 : add self tests to networkx

[tmonteil]

There are issues with random graphs provided by networkx:

sage: graphs.RandomBarabasiAlbert(50,2)
ValueError: 71598026902468055907350337076908659440L cannot be used to generate a random.Random instance

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​68f5ad0

#26326 : networkx 2.2 requires random.Random seeds, not integers

[tmonteil]

Erik, there is an issue about the nature of random seeds provided by current_randstate during doctests that is not of the same type that the ones provided during a normal session. It might come from #24508, any idea on how to fix that ?

[embray]

I see; the relevant code in networkx is here: ​https://github.com/networkx/networkx/blob/3466b800ef241cdfe76bae875fac50ac1ab54e02/networkx/utils/misc.py#L373

What I don't quite understand is why you changed this to current_python everywhere. It should still accept a plain int as the RNG seed (I don't quite like how networkx uses "seed" to mean something else, but that's another question...)

I could offer a workaround, but first I want to make sure it's really necessary to make this change in Sage, because it doesn't seem like it should be necessary. The release notes you linked to are unclear about what they thing the best practice should be.

[tmonteil]

Replying to embray:

I see; the relevant code in networkx is here: ​https://github.com/networkx/networkx/blob/3466b800ef241cdfe76bae875fac50ac1ab54e02/networkx/utils/misc.py#L373

What I don't quite understand is why you changed this to current_python everywhere. It should still accept a plain int as the RNG seed (I don't quite like how networkx uses "seed" to mean something else, but that's another question...)

The problem is that current_randstate().seed() provides longs, and apparently networkx does not like it:

sage: graphs.RandomBarabasiAlbert(50,2)
ValueError: 337906337582125808005456054818180223663L cannot be used to generate a random.Random instance

However it likes instances of random.Random objects which are provided by current_randstate().python_random().

Maybe should i use current_randstate().c_random() which is a 31bit-only integer, or current_randstate().python_random() % sys.maxint.

I guess that they do not support long because they are going to support Python 3 only.

I could offer a workaround, but first I want to make sure it's really necessary to make this change in Sage, because it doesn't seem like it should be necessary. The release notes you linked to are unclear about what they thing the best practice should be.

[saraedum]

So what's the status of this ticket now? Does this need review again or do you still want to change something here embray?

[arojas]

With this patch I'm getting lots of test suite errors on Arch:

ValueError?: <sage.cpython._py2_random.Random object at 0x561e012e8f50> cannot be used to generate a random.Random instance

Running the test code directly in Sage works fine. Using c_random() instead of python_random() makes the tests pass.

[arojas]

Replying to arojas:

With this patch I'm getting lots of test suite errors on Arch:

ValueError?: <sage.cpython._py2_random.Random object at 0x561e012e8f50> cannot be used to generate a random.Random instance

Running the test code directly in Sage works fine. Using c_random() instead of python_random() makes the tests pass.

Actually no, there are still some (fewer) failures

File "/usr/lib/python2.7/site-packages/sage/graphs/graph_plot.py", line 1286, in sage.graphs.graph_plot.GraphPlot.layout_tree
Failed example:
    T.show(layout='tree',tree_orientation='up') # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib/python2.7/site-packages/sage/doctest/forker.py", line 659, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/lib/python2.7/site-packages/sage/doctest/forker.py", line 1070, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.graph_plot.GraphPlot.layout_tree[1]>", line 1, in <module>
        T.show(layout='tree',tree_orientation='up') # indirect doctest
      File "/usr/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 19265, in show
        return self.graphplot(**plot_kwds).show(**kwds)
      File "/usr/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 18867, in graphplot
        return GraphPlot(graph=self, options=options)
      File "/usr/lib/python2.7/site-packages/sage/graphs/graph_plot.py", line 256, in __init__
        self.set_pos()
      File "/usr/lib/python2.7/site-packages/sage/graphs/graph_plot.py", line 340, in set_pos
        self._pos = self._graph.layout(**self._options)
      File "/usr/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 18187, in layout
        pos = getattr(self, "layout_%s"%layout)(dim = dim, **options)
      File "/usr/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 18443, in layout_tree
        raise RuntimeError("Cannot use tree layout on this graph: "
    RuntimeError: Cannot use tree layout on this graph: self.is_tree() returns False.

Again, running the code inside a Sage session works fine

[gh-timokau]

I'm getting the same errors as Antonio on nix.

[embray]

I guess that they do not support long because they are going to support Python 3 only.

That doesn't really make sense given that the Python 3 int type is the Python 2 long type. Probably more likely it needs to be modulo sys.max_size.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​54ba2a3	Merge branch 'u/tmonteil/upgrade_networkx_to_2_2_and_add_self_tests' of trac.sagemath.org:sage into HEAD
​626485b	#26326 : doctesting framework does not provide random.Random seeds, we use Python ints instead.

[tmonteil]

I would have preferred to rely on random.Random seeds, but let us move forward with that.

[gh-timokau]

I'm still getting:

File "/nix/store/9h32ccgbsdjbbiw5y9lvc338w5fbskkh-sage-src-8.4/src/sage/graphs/generators/degree_sequence.py", line 153, in sage.graphs.generators.degree_sequence.DegreeSequenceConfigurationModel
Failed example:
    G = graphs.DegreeSequenceConfigurationModel([1,1])
Exception raised:
    Traceback (most recent call last):
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/doctest/forker.py", line 659, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/doctest/forker.py", line 1070, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generators.degree_sequence.DegreeSequenceConfigurationModel[0]>", line 1, in <module>
        G = graphs.DegreeSequenceConfigurationModel([Integer(1),Integer(1)])
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/graphs/generators/degree_sequence.py", line 177, in DegreeSequenceConfigurationModel
        return Graph(networkx.configuration_model([int(i) for i in deg_sequence], seed=seed), loops=True, multiedges=True, sparse=True)
      File "<decorator-gen-154>", line 2, in configuration_model
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/networkx/utils/decorators.py", line 459, in _random_state
        random_state = create_py_random_state(random_state_arg)
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/networkx/utils/misc.py", line 409, in create_py_random_state
        raise ValueError(msg % random_state)
    ValueError: 138300676084728942938177272249092044107L cannot be used to generate a random.Random instance
**********************************************************************
File "/nix/store/9h32ccgbsdjbbiw5y9lvc338w5fbskkh-sage-src-8.4/src/sage/graphs/generators/degree_sequence.py", line 164, in sage.graphs.generators.degree_sequence.DegreeSequenceConfigurationModel
Failed example:
    G = graphs.DegreeSequenceConfigurationModel([3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3])
Exception raised:
    Traceback (most recent call last):
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/doctest/forker.py", line 659, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/doctest/forker.py", line 1070, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generators.degree_sequence.DegreeSequenceConfigurationModel[2]>", line 1, in <module>
        G = graphs.DegreeSequenceConfigurationModel([Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3)])
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/graphs/generators/degree_sequence.py", line 177, in DegreeSequenceConfigurationModel
        return Graph(networkx.configuration_model([int(i) for i in deg_sequence], seed=seed), loops=True, multiedges=True, sparse=True)
      File "<decorator-gen-154>", line 2, in configuration_model
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/networkx/utils/decorators.py", line 459, in _random_state
        random_state = create_py_random_state(random_state_arg)
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/networkx/utils/misc.py", line 409, in create_py_random_state
        raise ValueError(msg % random_state)
    ValueError: 41203442069597040437188274198544025403L cannot be used to generate a random.Random instance
**********************************************************************
File "/nix/store/9h32ccgbsdjbbiw5y9lvc338w5fbskkh-sage-src-8.4/src/sage/graphs/generators/degree_sequence.py", line 221, in sage.graphs.generators.degree_sequence.DegreeSequenceExpected
Failed example:
    G = graphs.DegreeSequenceExpected([1,2,3,2,3])
Exception raised:
    Traceback (most recent call last):
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/doctest/forker.py", line 659, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/doctest/forker.py", line 1070, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generators.degree_sequence.DegreeSequenceExpected[0]>", line 1, in <module>
        G = graphs.DegreeSequenceExpected([Integer(1),Integer(2),Integer(3),Integer(2),Integer(3)])
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/sage/graphs/generators/degree_sequence.py", line 235, in DegreeSequenceExpected
        return Graph(networkx.expected_degree_graph([int(i) for i in deg_sequence], seed=seed), loops=True)
      File "<decorator-gen-158>", line 2, in expected_degree_graph
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/networkx/utils/decorators.py", line 459, in _random_state
        random_state = create_py_random_state(random_state_arg)
      File "/nix/store/44zw4cgfi89wcyqg4p24yrs29hys03dj-python-2.7.15-env/lib/python2.7/site-packages/networkx/utils/misc.py", line 409, in create_py_random_state
        raise ValueError(msg % random_state)
    ValueError: 138300676084728942938177272249092044107L cannot be used to generate a random.Random instance

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​db10d32

#26326 : forgot generators/degree_sequence.py (comment 20).

[tmonteil]

Oops, my bad, i forgot that file (i remembered about two files only). Should be OK now.

[arojas]

Needs rebasing for 8.6.beta0

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c584662

Merge and fix conflict with #26871.

[tmonteil]

Thanks for noticing.

[tmonteil]

Note that Debian buster uses networkx 2.2, so i guess this should enter Sage 8.6, see ​https://packages.debian.org/buster/python-networkx

[dimpase]

Replying to embray:

I guess that they do not support long because they are going to support Python 3 only.

That doesn't really make sense given that the Python 3 int type is the Python 2 long type. Probably more likely it needs to be modulo sys.max_size.

Perhaps it's the same issue as I've noticed with networkx before, and even fixed some of it. Basically, they don't quite respect the Python's numerical tower, if it's extended, say by numpy, or Sage. See ​https://github.com/networkx/networkx/issues/2799

Basically they did dispatch on types not quite right, e.g. isinstance(foo,int) instead of isinstance(foo,numbers.Integral)

[vbraun]

Doctests fail on 32 bit: ​http://build.sagemath.org/#/builders/15/builds/10/steps/9/logs/stdio

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​38ac59f	#26326 : reorder creation of random graphs to avoid creating an empty one by bad luck on 32-bit systems.
​011a464	#26326 : 32-bit vs 64-bit doctests

[vbraun]

lets give it a try

[chapoton]

on python3:

----> 1 sys.maxint

AttributeError: module 'sys' has no attribute 'maxint'

EDIT:

sys.maxsize is the correct replacement, I think

​https://stackoverflow.com/questions/13795758/what-is-sys-maxint-in-python-3

[dimpase]

that's right, sys.maxsize works for py3 and py2. Who's going to update this?

[dimpase]

New commits:

​8d125d0

maxint -> maxsize, for py2/3 compatibility

[dimpase]

tests pass on py2.

On py3 there are 6 different formatting/ordering-induced test failures in src/sage/graphs/generators/random.py. I suppose this is for another ticket.

[Konrad127123]

This breaks building with SAGE_CHECK="yes", see #27253.