Stupid waste of time in graphs 1

[ncohen]

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

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

[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

[git]

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

​ce049ba

trac 15704: Stupid waste of time in graphs 1

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

[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

[git]

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

​ce049ba	trac 15704: Stupid waste of time in graphs 1
​037c189	trac #15704: Adding a doctest

[ncohen]

A commit to haul what we sow.

Nathann

[git]

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

​4056325

Heeeeeeeeeeeeeeeeee

[ncohen]

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

[git]

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

​ce049ba	trac 15704: Stupid waste of time in graphs 1
​037c189	trac #15704: Adding a doctest
​499e287	trac #15704: Changing add_edge to _backend.add_edge in the (Di)Graph constructor

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

[ncohen]

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

Nathann

[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)

[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

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

[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

[vdelecroix]

Then leeeeet's go!

Vincent

[ncohen]

Thaaaaaanks !

Nathann

[vbraun]

Reviewer name

[vbraun]

doctest failures after merge

[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

[git]

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

​f66f5f2	Merge branch 'u/ncohen/15704' of trac.sagemath.org:sage into tmp
​297b1b3	trac #15704: Broken doctests

[ncohen]

Passes all long tests.