Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#9567 closed enhancement (fixed)

Networkx-1.2 spkg

Reported by: bedwards Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-4.5.3
Component: graph theory Keywords: networkx spkg graph theory
Cc: ncohen Merged in: sage-4.5.3.alpha1
Authors: Ben Edwards, Nathann Cohen Reviewers: Ben Edwards, Nathann Cohen, Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This is the updated networkx package. It includes new features, bug fixes, and a couple of API changes. More information can be found here:

http://networkx.lanl.gov/reference/news.html

Package:

http://spkg-upload.googlecode.com/files/networkx-1.1.spkg

MD5 Sum

http://spkg-upload.googlecode.com/files/networkx-1.1.spkg.md5

Attachments (4)

14602.patch (16.1 KB) - added by bedwards 9 years ago.
14602.patch.md5 (46 bytes) - added by bedwards 9 years ago.
trac_9567-networkx-1.2.patch (16.0 KB) - added by bedwards 9 years ago.
trac_9567-cycle_basis.patch (2.8 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (36)

comment:1 Changed 9 years ago by mvngu

Is this ready for review?

comment:2 Changed 9 years ago by rlm

Three files with doctest failures, most look pretty harmless, different number of arguments, etc.:

The failures were

----------------------------------------------------------------------

The following tests failed:

	sage -t --long devel/sage-main/sage/graphs/graph_generators.py # 1 doctests failed
	sage -t --long devel/sage-main/sage/graphs/generic_graph.py # 8 doctests failed
	sage -t --long devel/sage-main/sage/graphs/graph.py # 19 doctests failed
----------------------------------------------------------------------

http://sage.pastebin.com/bTMLkp1H

comment:3 Changed 9 years ago by rlm

The graph_generators.py failure looks like a new NX bug:

sage: networkx.random_powerlaw_tree(10, 2)
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)

/scratch/rlmill/sage-4.5-linux-64bit-ubuntu_8.04.4_lts-x86_64-Linux/<ipython console> in <module>()

/scratch/rlmill/sage-4.5-linux-64bit-ubuntu_8.04.4_lts-x86_64-Linux/local/lib/python/networkx/generators/random_graphs.pyc in random_powerlaw_tree(n, gamma, create_using, seed, tries)
    930 
    931     """
--> 932     from nx.generators.degree_seq import degree_sequence_tree
    933     try:
    934         s=random_powerlaw_tree_sequence(n,

ImportError: No module named nx.generators.degree_seq

comment:4 Changed 9 years ago by rlm

  • Milestone set to sage-4.5.2
  • Report Upstream changed from Reported upstream. Little or no feedback. to N/A

Several API changes:

sage: networkx.triangles?
Type:		function
Base Class:	<type 'function'>
String Form:	<function triangles at 0x4899b18>
Namespace:	Interactive
File:		/scratch/rlmill/sage-4.5-linux-64bit-ubuntu_8.04.4_lts-x86_64-Linux/local/lib/python/networkx/algorithms/cluster.py
Definition:	networkx.triangles(G, nbunch=None)
Docstring:
    <no docstring>

(triangles used to take another argument) -- cluster_triangles() in Sage will need to be updated to reflect this.

sage: networkx.clustering?
Type:		function
Base Class:	<type 'function'>
String Form:	<function clustering at 0x4899c80>
Namespace:	Interactive
File:		/scratch/rlmill/sage-4.5-linux-64bit-ubuntu_8.04.4_lts-x86_64-Linux/local/lib/python/networkx/algorithms/cluster.py
Definition:	networkx.clustering(G, nbunch=None, weights=False)
Docstring:
    <no docstring>

this is Sage's clustering_coeff()

These are both coming from the argument with_weights disappearing in NX.

comment:5 Changed 9 years ago by rlm

No idea here:

**********************************************************************
File "/scratch/rlmill/sage-4.5-linux-64bit-ubuntu_8.04.4_lts-x86_64-Linux/devel/sage-main/sage/graphs/graph.py", line 2411:
    sage: (graphs.ChvatalGraph()).centrality_betweenness(normalized=False)
Expected:
    {0: 7.6666666666666661, 1: 7.6666666666666661, 2: 6.6666666666666661, 3: 6.6666666666666661, 4: 7.6666666666666661, 5: 7.6666666666666661, 6: 6.6666666666666661, 7: 6.6666666666666661, 8: 6.6666666666666661, 9: 6.6666666666666661, 10: 6.6666666666666661, 11: 6.6666666666666661}
Got:
    {0: 3.833333333333333, 1: 3.833333333333333, 2: 3.333333333333333, 3: 3.333333333333333, 4: 3.833333333333333, 5: 3.833333333333333, 6: 3.333333333333333, 7: 3.333333333333333, 8: 3.333333333333333, 9: 3.333333333333333, 10: 3.333333333333333, 11: 3.333333333333333}
**********************************************************************

comment:6 Changed 9 years ago by rlm

This function no longer takes a vertex as input:

sage: networkx.degree_centrality?
Type:		function
Base Class:	<type 'function'>
String Form:	<function degree_centrality at 0x87e9b0>
Namespace:	Interactive
File:		/scratch/rlmill/sage-4.5-linux-64bit-ubuntu_8.04.4_lts-x86_64-Linux/local/lib/python/networkx/algorithms/centrality/degree.py
Definition:	networkx.degree_centrality(G)
Docstring:
    <no docstring>

comment:7 Changed 9 years ago by rlm

  • Cc ncohen added
  • Status changed from new to needs_work

There are also some failures related to changes in the API of cliques functionality, but since we ship cliquer standard, which is an optimized C library for just this purpose, it seems we should be using that instead anyway.

All in all, these don't look bad at all. Not nearly as bad as upgrading to 1.0.

Ben -- If you want to submit a patch, I'd be glad to review it.

comment:8 follow-up: Changed 9 years ago by bedwards

The betweenness centrality test is a little concerning, and at a glance I am unsure about the bug in the random_powerlaw_tree, it seems that should work just fine... I'll start working on a patch. The API changes are improvements in the package, imho, returning dictionaries instead of lists, do we change the tests or is that a whole other process? Sorry, I'm new at this.

comment:9 Changed 9 years ago by ncohen

I just creaed #9569 to deal with new methods defined in NetworkX 1-1. I will also touch the "triangles" version as it looks like #9420 should make it faster to count them using our tools.

Nathann

comment:10 Changed 9 years ago by ncohen

Ok, what I just did sounds stupid. It will be way easier to solve all the bugs and expose methods in the same patch. Let's talk discuss it through emails :-)

Nathann

comment:11 in reply to: ↑ 8 Changed 9 years ago by rlm

Replying to bedwards:

The API changes are improvements in the package, imho, returning dictionaries instead of lists, do we change the tests or is that a whole other process? Sorry, I'm new at this.

We should change everything to support the new syntax, especially since it is so easy. If the pickle jar were having problems, it might mean we would have more work to do, but it seems that 1.0->1.1 involves very minimal changes.

comment:12 Changed 9 years ago by bedwards

Started working on this a bit. I think the bug is in the test for the betweenness centrality, I tested it using igraph in R, and it returns the same betweenness centrality as networkx-1.1. Also this was noted as a bug fix in the networkx change log.

comment:14 Changed 9 years ago by rlm

Ben,

Can you simply attach the patch to the ticket? Hit the attach button towards the top of the page :)

comment:15 Changed 9 years ago by bedwards

No, problem, wasn't quite sure of the protocol, here you go.

Changed 9 years ago by bedwards

Changed 9 years ago by bedwards

comment:16 Changed 9 years ago by bedwards

  • Status changed from needs_work to needs_review

comment:17 Changed 9 years ago by bedwards

networkx develops fast. Here is a new package for version 1.2. With the patch already attached above this should pass all the graphs/ tests with sage 4.5.1.

http://groups.google.com/group/sage-devel/attach/9521dbae9b6b22db/networkx-1.2.spkg?part=5

http://groups.google.com/group/sage-devel/attach/9521dbae9b6b22db/networkx-1.2.spkg.md5?part=4

comment:18 Changed 9 years ago by ncohen

Hello Ben !!!

I added a small patch containing the method cycle_basis (with a long doctest), that just calls NetworkX's. I haven't been able to properly write a cycle_space method (see http://groups.google.com/group/sage-support/browse_thread/thread/f99b59eaabf679a5/8bf34d54c183ab6b?lnk=gst&q=labelled#8bf34d54c183ab6b), so I tried to give a satisfying example in this docstring.

I give a positive review to your own patch for your patch/spkg, short of these two details :

  • I fixed some occurences of "dictionary" in my own patch
  • Your NetworkX SPKG has "uncommitted changes". Could you do a "hg commit", then upload the new version ? ( You can notice this when using the "sage -pkg" command to build spkg).

Nathann

comment:19 Changed 9 years ago by bedwards

Sorry forgot to commit, last time I built the package. Here is the newest one. Sorry about my bad spelling...

comment:21 Changed 9 years ago by ncohen

Well, then if you can review my patch and find everything to your taste, you can set this whole ticket as having received a positive review :-)

Nathann

comment:23 Changed 9 years ago by bedwards

  • Status changed from needs_review to positive_review

Nathan, you're patch looks great, and I learned a little about cycle basis! Thanks again for correcting my spelling. This one is ready.

comment:24 Changed 9 years ago by mpatel

  • Status changed from positive_review to needs_work

Should I apply exactly

to merge this ticket?

I'm changing the status to 'needs_work' for this: The first patch is missing the ticket number in the first line of its commit string. The first line itself should also be short (< 80 characters) but stand on its own, in order to keep hg log listings succinct and informative. Of course, there's no problem with extra lines that describe the changes in detail.

The second patch's commit string should perhaps be a bit more descriptive.

Also, please update the Author(s) and Reviewer(s) fields.

comment:25 Changed 9 years ago by ncohen

  • Authors changed from Ben Edwards to Ben Edwards, Nathann Cohen
  • Reviewers set to Ben Edwards, Nathann Cohen, Robert Miller

The ordering is correct...

Ben : could you update your patch ? I can not overwrite it, and that's the only thing left to do.

Nathann

comment:26 Changed 9 years ago by bedwards

Sorry, I was out of town for the weekend. Saw that sage-4.5.2 came out over the weekend, rebuilt the patch for that version, fixing my spelling as well. The appropriate order would be to merge:

http://spkg-upload.googlecode.com/files/networkx-1.2.spkg trac_9567-network-1.2.patch trac_9567-cycle_basis.patch

Nathann, maybe update yours for sage 4.5.2?

Changed 9 years ago by bedwards

comment:27 Changed 9 years ago by bedwards

Here is a new patched networkx-1.2 spkg that patches networkx to make it compatible with matplotlib.pyparsing.

http://spkg-upload.googlecode.com/files/networkx-1.2.p1.spkg

http://spkg-upload.googlecode.com/files/networkx-1.2.p1.spkg.md5

comment:28 Changed 9 years ago by ncohen

Updated !

Nathann

Changed 9 years ago by ncohen

comment:29 Changed 9 years ago by ncohen

  • Status changed from needs_work to positive_review

And back to positive review, as the fiels/descriptions have been filled :-)

Nathann

comment:30 Changed 9 years ago by mpatel

  • Merged in set to sage-4.5.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:31 Changed 9 years ago by mpatel

  • Merged in changed from sage-4.5.3.alpha0 to sage-4.5.3.alpha1

comment:32 Changed 9 years ago by mpatel

  • Summary changed from Networkx-1.1 spkg to Networkx-1.2 spkg
Note: See TracTickets for help on using tickets.