Opened 9 years ago

Closed 9 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 rlm)

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)

trac_11181.patch (16.9 KB) - added by rlm 9 years ago.
trac_11181-review.patch (10.0 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 9 years ago by rlm

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by rlm

  • Milestone set to sage-4.7

comment:3 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work

Changed 9 years ago by rlm

comment:4 Changed 9 years ago by rlm

  • Status changed from needs_work to needs_review

comment:5 Changed 9 years ago by stumpc5

  • Reviewers set to Christian Stump

I will look at the patch as soon as the buildbot shows its results.

Christian

comment:6 Changed 9 years ago by rlm

  • Description modified (diff)

comment:7 follow-up: Changed 9 years ago by ncohen

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: Changed 9 years ago by rlm

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 9 years ago by ncohen

Hello again !

http://docs.python.org/release/1.5/tut/node23.html

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 9 years ago by ncohen

comment:10 follow-up: Changed 9 years ago by stumpc5

  • 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: Changed 9 years ago by stumpc5

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: Changed 9 years ago by rlm

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 9 years ago by stumpc5

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 9 years ago by rlm

  • Authors changed from Robert Miller to Robert Miller, Nathann Cohen
  • 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 9 years ago by jdemeyer

  • Milestone changed from sage-4.7 to sage-4.7.1

comment:16 Changed 9 years ago by jdemeyer

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