Opened 7 years ago
Closed 7 years ago
#15704 closed enhancement (fixed)
Stupid waste of time in graphs 1
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  graph theory  Keywords:  
Cc:  azi  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  297b1b3 (Commits, GitHub, GitLab)  Commit:  297b1b3c2ee4bf868cc43f529ec04dc99230fc1d 
Dependencies:  Stopgaps: 
Description
............
The point is that MY computations are never long because of the add/remove edge functions. I should pay more attention T_T
Before
sage: g = graphs.RandomGNP(1500,.4) sage: edges = g.edges(labels=False) sage: %time Graph(edges) CPU times: user 2.50 s, sys: 0.03 s, total: 2.52 s Wall time: 2.55 s Graph on 1500 vertices sage: h = Graph() sage: %time h.add_edges(edges) CPU times: user 4.90 s, sys: 0.02 s, total: 4.92 s Wall time: 4.93 s
After
sage: g = graphs.RandomGNP(1500,.4) sage: edges = g.edges(labels=False) sage: %time Graph(edges) CPU times: user 2.12 s, sys: 0.02 s, total: 2.14 s Wall time: 2.16 s Graph on 1500 vertices sage: h = Graph() sage: %time h.add_edges(edges) CPU times: user 1.48 s, sys: 0.02 s, total: 1.50 s Wall time: 1.52 s
Nathann
Change History (28)
comment:1 Changed 7 years ago by
 Branch set to u/ncohen/15604
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
comment:3 Changed 7 years ago by
 Commit set to ce049ba02d81d3208fb33ac54579d6690468a636
Branch pushed to git repo; I updated commit sha1. New commits:
ce049ba  trac 15704: Stupid waste of time in graphs 1

comment:4 followup: ↓ 5 Changed 7 years ago by
I think you should have something documenting what happens with the old "bad" behavior. I assume it raises a wellformed error that tells people exactly what to do?
Also, it's not clear from the diff whether there are now no examples of adding edges with 2tuples, which I assume is still supported.
comment:5 in reply to: ↑ 4 Changed 7 years ago by
Yo !
I think you should have something documenting what happens with the old "bad" behavior. I assume it raises a wellformed error that tells people exactly what to do?
Well, it raises the same error as u,v=1
. To be honest I was afraid of adding a try/catch around the loop for the exception is a ValueError
, and I don't it to catch a ValueError
in _backend.add_edge
if there is one.
sage: g = Graph() sage: g.add_edges([(0,1),(0,1,1)])  ValueError Traceback (most recent call last) <ipythoninput4edffa551e119> in <module>() > 1 g.add_edges([(Integer(0),Integer(1)),(Integer(0),Integer(1),Integer(1))]) /home/ncohen/.Sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in add_edges(self, edges) 8970 else: 8971 self._backend.add_edge(e0[0], e0[1], None, self._directed) > 8972 for u,v in it: 8973 self._backend.add_edge(u, v, None, self._directed) 8974 ValueError: too many values to unpack
I hope it will be explicit enough for the users, and that they will notice they feed the loop with heterogeneous data.
As for testing add_edges()
with only pairs, not only it is still supported but I think most calls to this function only feed pairs :P
I added a commit.
Nathann
comment:6 Changed 7 years ago by
 Branch changed from u/ncohen/15604 to u/ncohen/15704
 Commit ce049ba02d81d3208fb33ac54579d6690468a636 deleted
comment:7 Changed 7 years ago by
 Commit set to 037c189e6cb6eeadfd18e5433a860e2b8c7a784f
comment:8 Changed 7 years ago by
A commit to haul what we sow.
Nathann
comment:9 Changed 7 years ago by
 Commit changed from 037c189e6cb6eeadfd18e5433a860e2b8c7a784f to 4056325aec3ed5f2f7a275b78ccc2b558dfe9f70
Branch pushed to git repo; I updated commit sha1. New commits:
4056325  Heeeeeeeeeeeeeeeeee

comment:10 Changed 7 years ago by
OOps. Perhaps I should change the commit message :PPPP
comment:11 Changed 7 years ago by
 Commit changed from 4056325aec3ed5f2f7a275b78ccc2b558dfe9f70 to 499e287061a2b9ba8a686dc3ec0ab6bb6ed177a6
comment:12 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:13 Changed 7 years ago by
Hi Nathann,
my branch: u/vdelecroix/15704
I simplified the add_edges
. That way we can use the old syntax and is not much slower (as calling len
is very cheap). What do you think?
comment:14 followup: ↓ 15 Changed 7 years ago by
Can you provide timings for this change ? If it is not that bad it is good to have indeed.
Nathann
comment:15 in reply to: ↑ 14 Changed 7 years ago by
Replying to ncohen:
Can you provide timings for this change ? If it is not that bad it is good to have indeed.
Here they are. Your version
sage: g = graphs.RandomGNP(1500,.4) sage: edges = g.edges(labels=False) sage: h = Graph() sage: %time h.add_edges(edges) CPU times: user 2.21 s, sys: 32 ms, total: 2.24 s Wall time: 2.23 s
mine
sage: g = graphs.RandomGNP(1500,.4) sage: edges = g.edges(labels=False) sage: h = Graph() sage: %time h.add_edges(edges) CPU times: user 2.48 s, sys: 32 ms, total: 2.51 s Wall time: 2.51 s
(Be careful the branch is not yet merged with 6.2.rc0 and sage b
is horribly long)
comment:16 followup: ↓ 17 Changed 7 years ago by
Hmmm.... 10%... I'd vote for the first version. What do you think ? Yours handles more case, but it would mean that input is a bit messy ?...
Nathann
comment:17 in reply to: ↑ 16 Changed 7 years ago by
Replying to ncohen:
Hmmm.... 10%... I'd vote for the first version. What do you think ? Yours handles more case, but it would mean that input is a bit messy ?...
 + 10% is a lot
  the messy input was in the documentation before you removed it
The main question: is this function critical? Is there any piece of code that uses it intensively?
comment:18 Changed 7 years ago by
Well, I began to write those patches because Jernej was not able to build a Graph with Sage .... I do not think that it really is the bottleneck in any code, but if the error message is clear, I don't think anybody can really complain that Sage refuses inputs like G.add_edges([(0,1,'l'), (0,1)])
.
So well. I'd go for the most efficient way to do it, given that I do not see this being a real problem for anybody.... I don't like to know that everybody loses 10% to prevent several users from cleaning their input a bit :P
Nathann
comment:19 Changed 7 years ago by
 Status changed from needs_review to positive_review
Then leeeeet's go!
Vincent
comment:20 Changed 7 years ago by
Thaaaaaanks !
Nathann
comment:21 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:22 Changed 7 years ago by
Reviewer name
comment:23 Changed 7 years ago by
 Reviewers set to Vincent Delecroix
comment:24 Changed 7 years ago by
 Status changed from positive_review to needs_work
doctest failures after merge
comment:25 Changed 7 years ago by
turns out some combinat code was feeding the function with nonuniform input.
Testing the whole Sage code... It would be cool if I could set up a patchbot on my office's computer, really :/
Nathann
comment:26 Changed 7 years ago by
 Commit changed from 499e287061a2b9ba8a686dc3ec0ab6bb6ed177a6 to 297b1b3c2ee4bf868cc43f529ec04dc99230fc1d
comment:27 Changed 7 years ago by
 Status changed from needs_work to positive_review
Passes all long tests.
comment:28 Changed 7 years ago by
 Branch changed from u/ncohen/15704 to 297b1b3c2ee4bf868cc43f529ec04dc99230fc1d
 Resolution set to fixed
 Status changed from positive_review to closed
This is the kind of patches that breaks code everywhere in Sage. We better wait for the patchbot to say it passes tests before getting it in.
Nathann