search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 478 forks source link

Stupid waste of time in graphs 1 #15704

Closed 6bdad4c1-1e26-4f2f-a442-a01a2292c181 closed 10 years ago

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

............

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

CC: @sagetrac-azi

Component: graph theory

Author: Nathann Cohen

Branch/Commit: 297b1b3

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/15704

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Branch: u/ncohen/15604

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:2

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

ce049batrac 15704: Stupid waste of time in graphs 1
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: ce049ba

kcrisman commented 10 years ago
comment:4

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.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:5

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Changed branch from u/ncohen/15604 to u/ncohen/15704

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Changed commit from ce049ba to none

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: 037c189

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:8

A commit to haul what we sow.

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 037c189 to 4056325

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

4056325Heeeeeeeeeeeeeeeeee
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:10

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 4056325 to 499e287

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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
videlec commented 10 years ago
comment:13

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?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:14

Can you provide timings for this change ? If it is not that bad it is good to have indeed.

Nathann

videlec commented 10 years ago
comment:15

Replying to @nathanncohen:

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)

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:16

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

videlec commented 10 years ago
comment:17

Replying to @nathanncohen:

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 ?...

The main question: is this function critical? Is there any piece of code that uses it intensively?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:18

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

videlec commented 10 years ago
comment:19

Then leeeeet's go!

Vincent

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:20

Thaaaaaanks !

Nathann

vbraun commented 10 years ago
comment:22

Reviewer name

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Reviewer: Vincent Delecroix

vbraun commented 10 years ago
comment:24

doctest failures after merge

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:25

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 499e287 to 297b1b3

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago
comment:27

Passes all long tests.

vbraun commented 10 years ago

Changed branch from u/ncohen/15704 to 297b1b3