Opened 10 years ago

Closed 8 years ago

#9362 closed defect (fixed)

Invalidate None as a vertex label.

Reported by: boothby Owned by: jason, mvngu, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords: sd35.5
Cc: brunellus Merged in: sage-5.0.beta5
Authors: Lukáš Lánský Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11739 Stopgaps:

Description (last modified by zimmerma)

The following indicates to me a huge problem:

sage: G = Graph()
sage: G.add_edge(None, 1)
sage: G.show()

the resulting plot has three vertices, one blank, one labeled "1" and the other labeled "None". The blank vertex is floating off in space, and the None and 1 vertices are bunched together.

Other places where a vertex labeled None will obviously cause problems:

spanning_trees_count, add_vertex, add_edge, delete_edge, has_edge, edge_label, eccentricity, layout_tree

this is not an exhaustive list; I merely read method definitions to look where a vertex argument defaults to None (and later uses the condition if v is None).

This indicates to me that we should not accept "None" as a valid vertex label.

Apply trac_9362_None_is_no_name.2.patch only.

Attachments (2)

trac_9362_None_is_no_name.patch (4.9 KB) - added by brunellus 8 years ago.
trac_9362_None_is_no_name.2.patch (4.6 KB) - added by brunellus 8 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 10 years ago by boothby

  • Description modified (diff)

comment:2 Changed 8 years ago by brunellus

  • Cc brunellus added

comment:3 Changed 8 years ago by dsm

It definitely makes sense to forbid None as a vertex label. add_vertex(), which it makes sense to think of as the fundamental spec, already forbids the use of None, both explicitly in the docstring ("cannot be None") and implicitly in practice because it uses the default None to mean "next unused integer". So that you can sneak it in as one through a back channel is a bad thing given the widespread use of None as a special value, just like the OP says.

comment:4 Changed 8 years ago by brunellus

  • Status changed from new to needs_review

I am not sure whether this patch catches every possible way a None-labeled vertex can sneak in, but I tried to go through the code and repair such cases.

Please, apply first the patch from #11739 before testing.

During testing I noticed that

sage: G=Graph(); G.add_edge(None, 4); G.vertices()
[0, 4]
sage: G=Graph(); G.add_edge(5, None)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/root/Sage/sageNoneVertex/devel/sage-main/sage/graphs/<ipython console> in <module>()

/root/Sage/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in add_edge(self, u, v, label)
   7556                     u, v, label = u
   7557                 except:
-> 7558                     u, v = u
   7559                     label = None
   7560         else:

TypeError: 'sage.rings.integer.Integer' object is not iterable

That is unpleasant asymmetry, don't you think? So I modified the code a little and now it works as expected.

sage: G=Graph(); G.add_edge(5, None); G.vertices()
[0, 5]

Changed 8 years ago by brunellus

comment:5 follow-up: Changed 8 years ago by zimmerma

  • Status changed from needs_review to needs_info

if #11739 is needed, please add it in the dependencies.

I thought from the summary that using None would be forbidden and would raise an exception, but comment 4 seems to still use None as a vertex. Is that wanted?

Paul Zimmermann

comment:6 Changed 8 years ago by zimmerma

  • Keywords sd35.5 added

comment:7 in reply to: ↑ 5 Changed 8 years ago by brunellus

  • Dependencies set to #11739

Replying to zimmerma:

I thought from the summary that using None would be forbidden and would raise an exception, but comment 4 seems to still use None as a vertex. Is that wanted?

Sorry that I didn't discuss this. What do you think? Using None as a special value for "create a new vertex" is consistent with add_vertex (that is especially nice in merge_vertices -- maybe that function should return a new vertex name in the [None, ...] case?), but it can make some errors harder to find. I don't have a strong opinion.

comment:8 Changed 8 years ago by brunellus

BTW: I'm not sure how slow is exception handling in Python, but isn't it little unfortunate that this is used so extensively in the add_edge function? Every call add_edge((u, v)) raises an exception that is immediately caught.

sage: G=Graph(multiedge=True)
sage: timeit("G.add_edge(1, 2)")
625 loops, best of 3: 8.21 µs per loop
sage: timeit("G.add_edge((1, 2))")
625 loops, best of 3: 12.2 µs per loop

comment:9 Changed 8 years ago by zimmerma

  • Status changed from needs_info to needs_review

ok, I agree that using None as special value in add_edge makes sense, and is consistent with add_vertex. Thus I put it back to needs review.

Paul

comment:10 Changed 8 years ago by zimmerma

  • Authors set to Lukáš Lánský
  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to positive_review

All doctests pass, and this is fine for me. Good work!

Paul

comment:11 Changed 8 years ago by jdemeyer

  • Milestone set to sage-pending

comment:12 Changed 8 years ago by brunellus

  • Status changed from positive_review to needs_work

I'm sorry -- the current version isn't compatible with changes in #11739. Would you be so kind to look at this one last time (hopefully)? :-)

Changed 8 years ago by brunellus

comment:13 Changed 8 years ago by brunellus

  • Status changed from needs_work to needs_review

comment:14 Changed 8 years ago by brunellus

(I just removed this part:

- self._nxg.add_nodes_from(vertices) 
+ for v in vertices: 
+     self.add_vertex(v) 

. #11739 takes care what happens there.)

comment:15 Changed 8 years ago by zimmerma

  • Description modified (diff)
  • Status changed from needs_review to positive_review

positive review, all doctests still pass with Sage 4.8 (except a timeout in sandpiles/sandpile.py which already happened before this patch).

Paul

comment:16 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.0

comment:17 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.