upgrade of spkg networkx-1.2.p2 to 1.6

[dkrenn]

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 attachment: trac_12806_doctest_fixes.patch, attachment: trac_12806.reviewer.patch and attachment: trac_12806-docbuild-and-links-alt.patch

CC: @kini @kiwifb @sagetrac-brunellus @nathanncohen

Component: graph theory

Keywords: spkg networkx graphs

Author: Daniel Krenn, Javier López Peña

Reviewer: Keshav Kini, Karl-Dieter Crisman

Merged: sage-5.2.beta1

Issue created by migration from https://trac.sagemath.org/ticket/12806

[dkrenn]

comment:1

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

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

[dkrenn]

Author: Daniel Krenn

[sagetrac-jlopez]

comment:5

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.

[sagetrac-jlopez]

comment:6

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.

[sagetrac-jlopez]

comment:7

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.

[sagetrac-jlopez]

comment:8

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.

[sagetrac-jlopez]

comment:10

Attachment: trac_12806_doctest_fixes.patch.gz

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.