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 )
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)
Change History (19)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Cc brunellus added
comment:3 Changed 8 years ago by
comment:4 Changed 8 years ago by
- 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
comment:5 follow-up: ↓ 7 Changed 8 years ago by
- Status changed from needs_review to needs_info
comment:6 Changed 8 years ago by
- Keywords sd35.5 added
comment:7 in reply to: ↑ 5 Changed 8 years ago by
- 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
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
- 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
- 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
- Milestone set to sage-pending
comment:12 Changed 8 years ago by
- 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
comment:13 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:14 Changed 8 years ago by
(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
- 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
- Milestone changed from sage-pending to sage-5.0
comment:17 Changed 8 years ago by
- Merged in set to sage-5.0.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
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.