Opened 10 years ago
Closed 10 years ago
#11181 closed defect (fixed)
edge labels should be unique
Reported by: | rlm | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.1 |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | sage-4.7.1.alpha0 |
Authors: | Robert Miller, Nathann Cohen | Reviewers: | Nathann Cohen, Christian Stump, Robert Miller |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
sage: G = Graph() sage: G.add_edge(0,1,[7]) sage: G.add_edge(0,2,[7]) sage: G.edge_label(0,1)[0] += 1 sage: G.edges() [(0, 1, [8]), (0, 2, [8])]
depends on #11182.
Attachments (2)
Change History (18)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Milestone set to sage-4.7
comment:3 Changed 10 years ago by
- Status changed from needs_review to needs_work
Changed 10 years ago by
comment:4 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:5 Changed 10 years ago by
- Reviewers set to Christian Stump
comment:6 Changed 10 years ago by
- Description modified (diff)
comment:7 follow-up: ↓ 8 Changed 10 years ago by
Hello Christian !
As there is still no sign from the patchbot (and yeah, I like to read what's happening in the graph backends) I began to review this patch....
I've got two questions though :
- The first one is about line 1597... It begins with an "else" after a "for" loop, and I really don't understand how it compiles or what it means
O_o
- I edited several areas of the code to "cache" the label of a vertex which was called several times... I can not do that for the (tricky) iterators appearing just afterwards
return iter([tuple(sorted( (vertex_label(v_int, self.vertex_ints, self.vertex_labels, self._cg), vertex_label(u_int, self.vertex_ints, self.vertex_labels, self._cg) ))) for v_int in vertices for u_int in self._cg.out_neighbors(v_int) if u_int >= v_int or u_int not in vertices for l_int in self._cg.all_arcs(v_int, u_int)])
do you think it's woth doing ? In which case I would copy the code from the lines above thise one, and remove the label-related tests....
:-)
- There is a
self.edge_labels.pop(ll_int)
in
set_edge_label
but not in
del_arc_unsafe
... Is there any reason ?:-)
Have fuuuuuuuuuun !
Nathann
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 10 years ago by
Replying to ncohen:
- The first one is about line 1597... It begins with an "else" after a "for" loop, and I really don't understand how it compiles or what it means
O_o
http://docs.python.org/release/1.5/tut/node23.html
- I edited several areas of the code to "cache" the label of a vertex which was called several times... I can not do that for the (tricky) iterators appearing just afterwards
Since those iterators construct a list anyway, there is no real reason for them to be written that way, but I didn't want to touch more code than necessary.
do you think it's woth doing ? In which case I would copy the code from the lines above thise one, and remove the label-related tests....
:-)
Very very careful! You'd do better to rearrange the current code. Each chunk of code is slightly different, of course..... This is maybe not worth it, I'm not really sure.
- There is a
self.edge_labels.pop(ll_int)
in
set_edge_label
but not in
del_arc_unsafe
... Is there any reason ?:-)
It should be in del_edge
if anywhere. Probably I just forgot to delete the edge label from the translation dictionary.
Your referee patch looks good to me, although you may post another one after reading these comments....
Thanks!
comment:9 in reply to: ↑ 8 Changed 10 years ago by
Hello again !
Okokokok ! Got it ! Tricky python :-)
I rephrase this paragraph so that it now tests whether the label is None before... As -- if I make no mistake -- the id 0 never appears in the dictionary, being always identified with None, and so it's useless to read the whole list of labels.
Since those iterators construct a list anyway, there is no real reason for them to be written that way, but I didn't want to touch more code than necessary.
Well, in the end I edited them. I tried to pay attention, and the doctests still pass, which is also a good sign ! If you can summon the energy to re-check it... :-)
It should be in
del_edge
if anywhere. Probably I just forgot to delete the edge label from the translation dictionary.
I added them !
Your referee patch looks good to me, although you may post another one after reading these comments....
And here it is... I also tried the following on the Sage without uour patches applied :
sage: def test(): ....: for u,v in g.edges(labels = False): ....: g.delete_edge(u,v) ....: g.add_edge(u,v) sage: g = graphs.CompleteGraph(200) sage: %timeit test() 5 loops, best of 3: 538 ms per loop
With the patches applied
5 loops, best of 3: 495 ms per loop
Well.. Not much, but better this way :-)
Nathann
Changed 10 years ago by
comment:10 follow-up: ↓ 11 Changed 10 years ago by
- Reviewers changed from Christian Stump to Nathann Cohen, Christian Stump
Salut,
to me, the patch and the review patch look fine! Thanks for the work.
One minor thing:
The code for iterator_edges, iterator_in_edges, and iterator_out_edges looks like most of it is redundant. Also, I don't understand why the multiple edges are not important in iterator_edges but is checked in both others.
Best, Christian
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 10 years ago by
Replying to stumpc5:
I was just checking how to simplify the code in the iterators: what is the advantage of returning an iterator after having constructed the complete list already? (Unfortunately, yield is not - yet - available in cython...).
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 10 years ago by
Nathann,
Thanks for your work on this. I'll have a look tomorrow.
Christian,
Replying to stumpc5:
I was just checking how to simplify the code in the iterators: what is the advantage of returning an iterator after having constructed the complete list already? (Unfortunately, yield is not - yet - available in cython...).
The particular block of code in question was written by Jason Grout, I think. It might be to be consistent with the NetworkX backends. Also, I think he was trying to write code to eventually be replaced by something which did yield, once Cython supported it. It certainly doesn't do any harm as it is.
comment:13 in reply to: ↑ 12 Changed 10 years ago by
Replying to rlm:
The particular block of code in question was written by Jason Grout, I think. It might be to be consistent with the NetworkX backends. Also, I think he was trying to write code to eventually be replaced by something which did yield, once Cython supported it. It certainly doesn't do any harm as it is.
I was just looking at it as Nathann did some changes in there. But I am totally fine with just leaving it as it is...
comment:14 Changed 10 years ago by
- Reviewers changed from Nathann Cohen, Christian Stump to Nathann Cohen, Christian Stump, Robert Miller
- Status changed from needs_review to positive_review
comment:15 Changed 10 years ago by
- Milestone changed from sage-4.7 to sage-4.7.1
comment:16 Changed 10 years ago by
- Merged in set to sage-4.7.1.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
I will look at the patch as soon as the buildbot shows its results.
Christian