Many doctests fails since the update of NetworkX !

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Hello everybody !!!

I noticed working on something quite different that many doctests were failing in Sage's graph library because of the recent update of NetworkX... The reason is easy : the default edge label is not "None" anymore but {}. Besides, dictionary are not hashable !!!

This patch fixes it !

Nathann

Component: graph theory

Author: Nathann Cohen

Reviewer: Minh Van Nguyen, Jason Grout

Merged: sage-4.4.2.rc0

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

[jasongrout]

comment:1

Apparently now, networkx has moved to having a dictionary of edge attributes, rather than a specific "label". See http://networkx.lanl.gov/reference/api_1.0.html#edge-attributes

I'm not saying we should follow the convention, but it does seem to make sense. Instead of just storing a single value, store a dict of attributes.

Why is it important that dictionaries are not hashable?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

Because I sometimes stored them as keys of dictionaries. It means I will need to forget to store the label, and just the endpoints. The other detail is that in many algorithms, the labels are used as a weight, and I you will see very often in Sage's code : weight = lambda label : 1 if label is None else label

So all these occurrences need to be replaces to label == {} in this case... Does that mean we should assume labels are ALWAYS dictionaries ? This would mean trouble... Where would we store numerical values for edges then.. a default field ?

Nathann

[jasongrout]

comment:3

A little farther down the networkx page listed, we find http://networkx.lanl.gov/reference/api_1.0.html#converting-your-existing-code-to-networkx-1-0, which says that now all algorithms (in Networkx) look for the "weight" edge attribute.

Sounds like that would be a huge change for Sage code, though...

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:4

Hi Nathann,

Thanks for uncovering this one. Not sure right now I have a good idea about what should be done.

However, is there a patch to go on this? I'm not seeing one.

Rob

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

Not yet. For the moment, my patch is a nasty one : replaces tests "is None" by "is None or == {}". I thought it may be better to settle on what we want to do with these labels, but I can upload it otherwise (somewhere on another computer at the moment) :-)

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:6

Here is a patch that does not make any choice. I replaced the "is None" by "in RR" :-)

The failing docstrings come from GraphViz ( at least on my computer ) !

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

Now also fixes the edge_coloring function from the graph_coloring module, as reported by Minh in #8781

Sorry for that !

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Attachment: trac_8892.patch.gz

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:8

Attachment: trac_8892-reviewer.patch.gz

I'm mostly happy with trac_8892.patch. I have attached a reviewer patch that deals with the part I'm not happy with, i.e. fix some typos introduced by the first patch. Apart from myself, anyone is welcome to give a final sign off on this ticket.

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Author: Nathann Cohen

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Reviewer: Minh Van Nguyen

[jasongrout]

comment:9

I sign off on your changes. Are you asking someone else to also sign off on the original patch?

[jasongrout]

comment:11

(I didn't apply your changes, but it is clear that they are cosmetic things.)

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:12

Replying to @jasongrout:

Are you asking someone else to also sign off on the original patch?

Not really. I'm OK with ncohen's patch.

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Changed reviewer from Minh Van Nguyen to Minh Van Nguyen, Jason Grout

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Merged: sage-4.4.2.rc0