Opened 5 years ago

Closed 5 years ago

#15704 closed enhancement (fixed)

Stupid waste of time in graphs 1

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: graph theory Keywords:
Cc: azi Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 297b1b3 (Commits) 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 5 years ago by ncohen

  • Branch set to u/ncohen/15604
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by ncohen

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

comment:3 Changed 5 years ago by git

  • Commit set to ce049ba02d81d3208fb33ac54579d6690468a636

Branch pushed to git repo; I updated commit sha1. New commits:

ce049batrac 15704: Stupid waste of time in graphs 1

comment:4 follow-up: Changed 5 years ago by kcrisman

I think you should have something documenting what happens with the old "bad" behavior. I assume it raises a well-formed 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 2-tuples, which I assume is still supported.

comment:5 in reply to: ↑ 4 Changed 5 years ago by ncohen

Yo !

I think you should have something documenting what happens with the old "bad" behavior. I assume it raises a well-formed 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)
<ipython-input-4-edffa551e119> in <module>()
----> 1 g.add_edges([(Integer(0),Integer(1)),(Integer(0),Integer(1),Integer(1))])

/home/ncohen/.Sage/local/lib/python2.7/site-packages/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 5 years ago by ncohen

  • Branch changed from u/ncohen/15604 to u/ncohen/15704
  • Commit ce049ba02d81d3208fb33ac54579d6690468a636 deleted

comment:7 Changed 5 years ago by git

  • Commit set to 037c189e6cb6eeadfd18e5433a860e2b8c7a784f

Branch pushed to git repo; I updated commit sha1. New commits:

ce049batrac 15704: Stupid waste of time in graphs 1
037c189trac #15704: Adding a doctest

comment:8 Changed 5 years ago by ncohen

A commit to haul what we sow.

Nathann

comment:9 Changed 5 years ago by git

  • Commit changed from 037c189e6cb6eeadfd18e5433a860e2b8c7a784f to 4056325aec3ed5f2f7a275b78ccc2b558dfe9f70

Branch pushed to git repo; I updated commit sha1. New commits:

4056325Heeeeeeeeeeeeeeeeee

comment:10 Changed 5 years ago by ncohen

OOps. Perhaps I should change the commit message :-PPPP

comment:11 Changed 5 years ago by git

  • Commit changed from 4056325aec3ed5f2f7a275b78ccc2b558dfe9f70 to 499e287061a2b9ba8a686dc3ec0ab6bb6ed177a6

Branch pushed to git repo; I updated commit sha1. New commits:

ce049batrac 15704: Stupid waste of time in graphs 1
037c189trac #15704: Adding a doctest
499e287trac #15704: Changing add_edge to _backend.add_edge in the (Di)Graph constructor

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 5 years ago by vdelecroix

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 follow-up: Changed 5 years ago by ncohen

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 5 years ago by vdelecroix

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 follow-up: Changed 5 years ago by 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 ?...

Nathann

comment:17 in reply to: ↑ 16 Changed 5 years ago by vdelecroix

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

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 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Then leeeeet's go!

Vincent

comment:20 Changed 5 years ago by ncohen

Thaaaaaanks !

Nathann

comment:21 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:22 Changed 5 years ago by vbraun

Reviewer name

comment:23 Changed 5 years ago by ncohen

  • Reviewers set to Vincent Delecroix

comment:24 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

doctest failures after merge

comment:25 Changed 5 years ago by ncohen

turns out some combinat code was feeding the function with non-uniform 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 5 years ago by git

  • Commit changed from 499e287061a2b9ba8a686dc3ec0ab6bb6ed177a6 to 297b1b3c2ee4bf868cc43f529ec04dc99230fc1d

Branch pushed to git repo; I updated commit sha1. New commits:

f66f5f2Merge branch 'u/ncohen/15704' of trac.sagemath.org:sage into tmp
297b1b3trac #15704: Broken doctests

comment:27 Changed 5 years ago by ncohen

  • Status changed from needs_work to positive_review

Passes all long tests.

comment:28 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/15704 to 297b1b3c2ee4bf868cc43f529ec04dc99230fc1d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.