Opened 8 years ago

Last modified 7 years ago

#12806 closed defect

upgrade of spkg networkx-1.2.p2 to 1.6 — at Version 11

Reported by: dkrenn Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.2
Component: graph theory Keywords: spkg networkx graphs
Cc: kini, fbissey, brunellus, ncohen Merged in:
Authors: Daniel Krenn, Javier López Peña Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jlopez)

When upgrading the networkx package to 1.6, there arise a lot of doctest errors, see discussion on sage-devel. This ticket should contain everything that is necessary to do so.

To get the doctests passing, the following modifications have been made:

  1. Fixed the calls in graph.py to conform to the new API for betweennness_centrality. Also exposed the new options.
  2. Failing doctest in digraph.py was shocasing a bug that isn't there anymore. Fixed and documented it, and exposed the previously offending implementation to sage
  3. Two failures in graph_generators.py were due to changes in randomized methods, so just changed the tests to conform to the new output, the rest were due to a bad-parameter case that was used to raise an exception but now degenerates gracefully. Fixed the corresponding doctests to account for that.
  4. Failures in graph_generic.py were due to a change in the output of clustering coefficients for weighted graphs. Added an optional parameter to use the new output, implemented the old behaviour as it was in NetworkX 1.2, and set the old behaviour to default with a deprecation warning.

To review this ticket:

  1. Install this spkg
  2. Apply this patch

Change History (12)

comment:1 Changed 8 years ago by dkrenn

  • Authors set to Daniel Krenn

I made a package networkx-1.6, which is available here.

There are a lot of doctests failing in sage.graphs.

comment:2 Changed 8 years ago by kini

  • Cc kini added

comment:3 Changed 8 years ago by fbissey

  • Cc fbissey added

comment:4 Changed 7 years ago by brunellus

  • Cc brunellus added

comment:5 Changed 7 years ago by jlopez

The failing tests in graph.py are due to an API change in the betweenness_centrality function. They get fixed by replacing

    return networkx.betweenness_centrality(self.networkx_graph(copy=False), normalized)

in line 3252 of SAGE_ROOT/devel/sage-main/sage/graphs/graph.py by

    return networkx.betweenness_centrality(self.networkx_graph(copy=False), normalized = normalized)

I will take a look at the rest of the failing tests tomorrow and write a patch.

comment:6 Changed 7 years ago by jlopez

The failing test in digraph.py is an improvement. In older versions of NetworkX topological_sort_recursive had a problem that has since been sorted out. The failing test was showcasing a bug that is not there anymore. This is also good news since we can also expose the recursive implementation of topological sorts in sage.

comment:7 Changed 7 years ago by jlopez

All but two of the failing tests in graph_generators.py are due to extreme cases of balanced trees (degree 1, height 0), that didn't use to be allowed before and now degenerate gracefully. So this problem gets sorted out just by removing the offending doctests. As a nice side-effect, the offending tests took most of the testing time before. After removing them time for running the tests in graph_generators.py drops for me from 357s to 18s.

comment:8 Changed 7 years ago by jlopez

The two remaining doctests in graph_generators.py are due to changes in two randomized methods: a change in networkx.powerlaw_cluster_graph from using random.random to _random_subset and a rewriting of the random method expected_degree_graph. Since the functions called in the doctests have a randomized nature it is not unreasonable to expect the results to change after the randomized function is rewritten. Unless somebody complains I will just update the tests to the results with the new methods.

comment:9 Changed 7 years ago by ncohen

  • Cc ncohen added

Changed 7 years ago by jlopez

comment:10 Changed 7 years ago by jlopez

Added a patch with the necessary changes for the doctests. All tests pass in my system. To review this patch you need to install the spkg by Daniel Krenn in the first comment and then apply the patch.

comment:11 Changed 7 years ago by jlopez

  • Authors changed from Daniel Krenn to Daniel Krenn, Javier López Peña
  • Description modified (diff)
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.