Opened 4 years ago

Closed 3 years ago

Last modified 3 years ago

#26326 closed enhancement (fixed)

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

Reported by: tmonteil Owned by:
Priority: major Milestone: sage-8.6
Component: packages: standard Keywords:
Cc: embray, fbissey, gh-timokau Merged in:
Authors: Thierry Monteil, Dima Pasechnik Reviewers: Volker Braun, Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 8d125d0 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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

Change History (38)

comment:1 Changed 4 years ago by tmonteil

  • Description modified (diff)

comment:2 Changed 4 years ago by tmonteil

  • Branch set to u/tmonteil/upgrade_networkx_to_2_2_and_add_self_tests

comment:3 Changed 4 years ago by git

  • Commit set to 9a7dff84fbc348fc37bd76cf454c0d7b8275580c

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

9a7dff8#26326 : add self tests to networkx

comment:4 Changed 4 years ago by tmonteil

  • Status changed from new to needs_review

comment:5 Changed 4 years ago by tmonteil

  • Status changed from needs_review to needs_work

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

comment:6 Changed 4 years ago by git

  • Commit changed from 9a7dff84fbc348fc37bd76cf454c0d7b8275580c to 68f5ad068184745b38ba6716bf967c8c956c52c5

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

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

comment:7 Changed 4 years ago by tmonteil

  • Description modified (diff)
  • Summary changed from Upgrade networkx to 2.2 and add self tests to Upgrade networkx to 2.2, add self tests, and update random seed format

comment:8 Changed 4 years ago by tmonteil

  • Cc embray added

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 ?

comment:9 follow-up: Changed 4 years ago by 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.

comment:10 in reply to: ↑ 9 Changed 4 years ago by 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.

comment:11 Changed 4 years ago by fbissey

  • Cc fbissey added

comment:12 Changed 4 years ago by gh-timokau

  • Cc gh-timokau added

comment:13 Changed 4 years ago by 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?

comment:14 follow-up: Changed 4 years ago by 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.

comment:15 in reply to: ↑ 14 Changed 4 years ago by 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

comment:16 Changed 4 years ago by gh-timokau

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

comment:17 follow-up: Changed 4 years ago by 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.

comment:18 Changed 4 years ago by git

  • Commit changed from 68f5ad068184745b38ba6716bf967c8c956c52c5 to 626485bbe5f33bf143d6dfba4de9c242f757f59b

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

54ba2a3Merge 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.

comment:19 Changed 4 years ago by tmonteil

  • Status changed from needs_work to needs_review

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

comment:20 Changed 4 years ago by 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

comment:21 Changed 4 years ago by git

  • Commit changed from 626485bbe5f33bf143d6dfba4de9c242f757f59b to db10d327ade93711da735a599a67580524e6f7b4

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

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

comment:22 Changed 4 years ago by tmonteil

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

comment:23 Changed 3 years ago by arojas

  • Status changed from needs_review to needs_work

Needs rebasing for 8.6.beta0

comment:24 Changed 3 years ago by git

  • Commit changed from db10d327ade93711da735a599a67580524e6f7b4 to c5846622cff736fa8728ef9ed5f50774fe80ddee

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

c584662Merge and fix conflict with #26871.

comment:25 Changed 3 years ago by tmonteil

  • Milestone changed from sage-8.4 to sage-8.6
  • Status changed from needs_work to needs_review

Thanks for noticing.

comment:26 Changed 3 years ago by 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

comment:27 Changed 3 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

comment:28 in reply to: ↑ 17 Changed 3 years ago by 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)

comment:29 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:30 Changed 3 years ago by git

  • Commit changed from c5846622cff736fa8728ef9ed5f50774fe80ddee to 011a4648f4677a150a8da31499123a07e1ad0700

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

comment:31 Changed 3 years ago by tmonteil

  • Status changed from needs_work to needs_review

comment:32 Changed 3 years ago by vbraun

  • Status changed from needs_review to positive_review

lets give it a try

comment:33 Changed 3 years ago by chapoton

  • Status changed from positive_review to needs_work

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

Last edited 3 years ago by chapoton (previous) (diff)

comment:34 Changed 3 years ago by dimpase

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

comment:35 Changed 3 years ago by dimpase

  • Authors changed from Thierry Monteil to Thierry Monteil, Dima Pasechnik
  • Branch changed from u/tmonteil/upgrade_networkx_to_2_2_and_add_self_tests to u/dimpase/packages/networkx22
  • Commit changed from 011a4648f4677a150a8da31499123a07e1ad0700 to 8d125d0f7bb7ce5ac347dc4fc979a134feccd11c
  • Status changed from needs_work to needs_review

New commits:

8d125d0maxint -> maxsize, for py2/3 compatibility

comment:36 Changed 3 years ago by dimpase

  • Reviewers changed from Volker Braun to Volker Braun, Dima Pasechnik
  • Status changed from needs_review to positive_review

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.

comment:37 Changed 3 years ago by vbraun

  • Branch changed from u/dimpase/packages/networkx22 to 8d125d0f7bb7ce5ac347dc4fc979a134feccd11c
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:38 Changed 3 years ago by Konrad127123

  • Commit 8d125d0f7bb7ce5ac347dc4fc979a134feccd11c deleted

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

Note: See TracTickets for help on using tickets.