upgrade of networx spkg (to get Bellman-Ford algorithm)

[Daniel Krenn]

At the moment networkx-1.2.p2.spkg is included in Sage. Networkx 1.2 is
now over 20 month old and networkx 1.6 is available. Does anyone plan
upgrading this?

Background: I wanted to implement Bellman-Ford algorithm (finding
(shortest) paths in weighted graphs which can have negative weights).
There is an two year old ticket, see [#8714], where some code is given,
which I planned to use. But I saw, that networkx 1.6 has already a
Bellman-Ford algorithm, so I think that one should be used.

If one upgrades the networkx-spkg, then I will write an interface for
Bellman-Ford in generic_graph.py (and therefore resolve #8714)

Daniel

[#8714] http://trac.sagemath.org/sage_trac/ticket/8714

[Daniel Krenn]

[Dima Pasechnik]

Why wouldn't you try to do the upgrade? :-)
This looks relatively straightforward - the biggest issue is to figure
out what to do with two Sage patches that the spkg applies now.
The patches are for
readwrite/gml.py
and
readwrite/tests/test_gml.py
(to provide some kind of matplotlib interface)

Dmitrii
>
> Daniel
>
> [#8714] http://trac.sagemath.org/sage_trac/ticket/8714
>

[Daniel Krenn]

Am 2012-03-31 19:36, schrieb Dima Pasechnik:
> On 2012-03-31, Daniel Krenn <kr...@aon.at> wrote:
>> At the moment networkx-1.2.p2.spkg is included in Sage. Networkx 1.2 is
>> now over 20 month old and networkx 1.6 is available. Does anyone plan
>> upgrading this?

> Why wouldn't you try to do the upgrade? :-)
> This looks relatively straightforward - the biggest issue is to figure
> out what to do with two Sage patches that the spkg applies now.
> The patches are for
> readwrite/gml.py
> and
> readwrite/tests/test_gml.py
> (to provide some kind of matplotlib interface)

Ok, maybe it is easier than I thought. I'll give it a try.

Daniel

[Daniel Krenn]

I upgraded the package, available at [1]. The upgrading was really easy;
all patches were already included into 1.6, so obsolete.

But now some doctests in graphs are failing, see output below. It seems
that sometimes the output-format has changed (more or less output is
given), but sometimes also the values changed...

Daniel

[1] http://www.math.tugraz.at/~krenn/whatever/networkx-1.6.spkg

Parts of the doctest on sage.graphs:

**********************************************************************
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/devel/sage-main/sage/graphs/digraph.py",
line 2355:
sage: networkx.topological_sort_recursive(N) is None
Expected:
True
Got:
False

**********************************************************************
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/devel/sage-main/sage/graphs/graph.py",
line 3106:
sage: (graphs.ChvatalGraph()).centrality_betweenness()
Expected:
{0: 0.069696969696969688, 1: 0.069696969696969688, 2:
0.060606060606060601, 3: 0.060606060606060601, 4: 0.069696969696969688,
5: 0.069696969696969688, 6:
0.060606060606060601, 7: 0.060606060606060601, 8: 0.060606060606060601,
9: 0.060606060606060601, 10: 0.060606060606060601, 11: 0.060606060606060601}
Got:
{0: 0.0, 1: 0.0, 2: 0.19999999999999998, 3: 0.0, 4:
0.19999999999999998, 5: 0.0, 6: 0.0, 7: 0.14545454545454545, 8: 0.0, 9:
0.21818181818181817, 10: 0.0, 11: 0.0}

**********************************************************************
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/devel/sage-main/sage/graphs/graph.py",
line 3108:
sage: (graphs.ChvatalGraph()).centrality_betweenness(normalized=False)
Exception raised:
Traceback (most recent call last):
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/local/bin/ncadoctest.py",
line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/local/bin/sagedoctest.py",
line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename,
compileflags)
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/local/bin/ncadoctest.py",
line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_27[3]>", line 1, in <module>

(graphs.ChvatalGraph()).centrality_betweenness(normalized=False)###line
3108:
sage: (graphs.ChvatalGraph()).centrality_betweenness(normalized=False)
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/local/lib/python/site-packages/sage/graphs/graph.py",
line 3118, in centrality_betweenness
return
networkx.betweenness_centrality(self.networkx_graph(copy=False), normalized)
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/local/lib/python2.6/networkx/algorithms/centrality/betweenness.py",
line 118, in betweenness_centrality
k=k)
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/local/lib/python2.6/networkx/algorithms/centrality/betweenness.py",
line 315, in _rescale
scale=scale*n/k
ZeroDivisionError: float division

**********************************************************************
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/devel/sage-main/sage/graphs/graph.py",
line 3114:
sage: D.centrality_betweenness()
Expected:
{0: 0.16666666666666666, 1: 0.16666666666666666, 2: 0.0, 3: 0.0}
Got:
{0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3: 0.0}

**********************************************************************
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/devel/sage-main/sage/graphs/generic_graph.py",
line 10294:
sage: (graphs.FruchtGraph()).clustering_coeff(weights=True)
Expected:
({0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3:
0.33333333333333331, 4: 0.33333333333333331, 5: 0.33333333333333331, 6:
0.33333333333333331, 7: 0.33333333333333331, 8: 0.0, 9:
0.33333333333333331, 10: 0.33333333333333331, 11: 0.0}, {0:
0.083333333333333329, 1: 0.083333333333333329, 2: 0.083333333333333329,
3: 0.083333333333333329, 4: 0.083333333333333329, 5:
0.083333333333333329, 6: 0.083333333333333329, 7: 0.083333333333333329,
8: 0.083333333333333329, 9: 0.083333333333333329, 10:
0.083333333333333329, 11: 0.083333333333333329})
Got:
{0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0, 3:
0.33333333333333331, 4: 0.33333333333333331, 5: 0.33333333333333331, 6:
0.33333333333333331, 7: 0.33333333333333331, 8: 0.0, 9:
0.33333333333333331, 10: 0.33333333333333331, 11: 0.0}

**********************************************************************
File
"/local/data/krenn/sage-dev/Sage-4.8-amd64-clean/devel/sage-main/sage/graphs/generic_graph.py",
line 10298:
sage:
(graphs.FruchtGraph()).clustering_coeff(nbunch=[0,1,2],weights=True)
Expected:
({0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0}, {0:
0.33333333333333331, 1: 0.33333333333333331, 2: 0.33333333333333331})
Got:
{0: 0.33333333333333331, 1: 0.33333333333333331, 2: 0.0}

**********************************************************************
sage -t devel/sage/sage/graphs/graph_generators.py
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***

[François Bissey]

There is a lot of stuff there. In sage-on-gentoo I remember we had to lock
networkx to 1.2 because in 1.3+ they had changed some interface that was
breaking some doctests. In 1.3 this broke doctests:
API Changes
minimum_spanning_tree() now returns a NetworkX Graph (a tree or forest)

But I cannot associate with any of the failing doctests you mention. However
I think the API changes introduced in 1.5 are spot on with some of your
doctest:
http://networkx.lanl.gov/reference/api_1.5.html
I think some may be from the changes in 1.6:
http://networkx.lanl.gov/reference/api_1.6.html

The changes from 1.3 and 1.4 are on this page
http://networkx.lanl.gov/reference/news.html
But not as many details.
In short because of all the changes we will need to do a certain amount of
patching in sage before we can ship 1.6

Francois

[Dima Pasechnik]

On 2012-04-03, François Bissey <francoi...@canterbury.ac.nz> wrote:
> On Tue, 03 Apr 2012 23:38:32 Daniel Krenn wrote:
>> Am 2012-04-01 12:25, schrieb Daniel Krenn:
>> > Am 2012-03-31 19:36, schrieb Dima Pasechnik:
>> >> On 2012-03-31, Daniel Krenn <kr...@aon.at> wrote:
>> >>> At the moment networkx-1.2.p2.spkg is included in Sage. Networkx 1.2
>> >>> is
>> >>> now over 20 month old and networkx 1.6 is available. Does anyone
>> >>> plan
>> >>> upgrading this?
>> >>
>> >> Why wouldn't you try to do the upgrade? :-)
>> >> This looks relatively straightforward - the biggest issue is to figure
>> >> out what to do with two Sage patches that the spkg applies now.
>> >> The patches are for
>> >> readwrite/gml.py
>> >> and
>> >> readwrite/tests/test_gml.py
>> >> (to provide some kind of matplotlib interface)
>> >
>> > Ok, maybe it is easier than I thought. I'll give it a try.
>>
>> I upgraded the package, available at [1]. The upgrading was really easy;
>> all patches were already included into 1.6, so obsolete.

Please open a track ticket on this.
Thanks,
Dima

[Daniel Krenn]

Am 2012-04-04 00:43, schrieb Dima Pasechnik:

> On 2012-04-03, Fran�ois Bissey <francoi...@canterbury.ac.nz> wrote:
>> On Tue, 03 Apr 2012 23:38:32 Daniel Krenn wrote:
>>> I upgraded the package, available at [1]. The upgrading was really easy;
>>> all patches were already included into 1.6, so obsolete.
>
> Please open a track ticket on this.
> Thanks,
> Dima

Done, see [http://trac.sagemath.org/sage_trac/ticket/12806 #12806].

[Javier López Peña]

The failing tests in graph.py are due to a minor 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.

Cheers,

J