Stupid waste of time in graphs 1 #15704

nathanncohen · 2014-01-21T18:49:01Z

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

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

The text was updated successfully, but these errors were encountered:

nathanncohen · 2014-01-21T18:49:16Z

Branch: u/ncohen/15604

nathanncohen · 2014-01-21T18:59:21Z

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

sagetrac-git · 2014-01-21T18:59:44Z

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

`ce049ba`	`trac 15704: Stupid waste of time in graphs 1`

sagetrac-git · 2014-01-21T18:59:44Z

Commit: ce049ba

kcrisman · 2014-01-21T20:23:34Z

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.

nathanncohen · 2014-01-22T08:33:07Z

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

nathanncohen · 2014-01-22T08:36:11Z

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

nathanncohen · 2014-01-22T08:36:11Z

Changed commit from ce049ba to none

sagetrac-git · 2014-01-22T08:36:29Z

Commit: 037c189

sagetrac-git · 2014-01-22T08:36:29Z

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`

nathanncohen · 2014-01-22T10:27:38Z

comment:8

A commit to haul what we sow.

Nathann

sagetrac-git · 2014-01-22T10:28:20Z

Changed commit from 037c189 to 4056325

sagetrac-git · 2014-01-22T10:28:20Z

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

`4056325`	`Heeeeeeeeeeeeeeeeee`

nathanncohen · 2014-01-22T10:28:40Z

comment:10

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

sagetrac-git · 2014-01-22T10:29:21Z

Changed commit from 4056325 to 499e287

sagetrac-git · 2014-01-22T10:29:21Z

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`

videlec · 2014-04-22T14:34:38Z

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?

nathanncohen · 2014-04-23T13:52:53Z

comment:14

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

Nathann

videlec · 2014-04-23T15:11:01Z

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)

nathanncohen · 2014-04-23T15:12:40Z

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 · 2014-04-23T15:44:53Z

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

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

nathanncohen · 2014-04-23T15:53:17Z

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 · 2014-04-23T15:56:00Z

comment:19

Then leeeeet's go!

Vincent

nathanncohen · 2014-04-23T15:57:14Z

comment:20

Thaaaaaanks !

Nathann

vbraun · 2014-05-07T15:06:50Z

comment:22

Reviewer name

nathanncohen · 2014-05-07T15:53:03Z

Reviewer: Vincent Delecroix

vbraun · 2014-05-08T09:11:16Z

comment:24

doctest failures after merge

nathanncohen · 2014-05-08T09:32:47Z

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

sagetrac-git · 2014-05-08T10:03:49Z

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`

sagetrac-git · 2014-05-08T10:03:49Z

Changed commit from 499e287 to 297b1b3

nathanncohen · 2014-05-08T10:04:56Z

comment:27

Passes all long tests.

vbraun · 2014-05-12T11:34:42Z

Changed branch from u/ncohen/15704 to 297b1b3

nathanncohen mannequin added this to the sage-6.1 milestone Jan 21, 2014

nathanncohen mannequin added c: graph theory labels Jan 21, 2014

nathanncohen mannequin added the s: needs review label Jan 21, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

videlec added s: positive review and removed s: needs review labels Apr 23, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

vbraun added s: needs work and removed s: positive review labels May 8, 2014

nathanncohen mannequin added s: positive review and removed s: needs work labels May 8, 2014

vbraun removed the s: positive review label May 12, 2014

vbraun closed this as completed in da70f28 May 12, 2014

nathanncohen mannequin mentioned this issue Dec 12, 2014

Graph built from their edges are simple by default #15706

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Stupid waste of time in graphs 1 #15704

Stupid waste of time in graphs 1 #15704

nathanncohen mannequin commented Jan 21, 2014

nathanncohen mannequin commented Jan 21, 2014

nathanncohen mannequin commented Jan 21, 2014

sagetrac-git mannequin commented Jan 21, 2014

sagetrac-git mannequin commented Jan 21, 2014

kcrisman commented Jan 21, 2014

nathanncohen mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

videlec commented Apr 22, 2014

nathanncohen mannequin commented Apr 23, 2014

videlec commented Apr 23, 2014

nathanncohen mannequin commented Apr 23, 2014

videlec commented Apr 23, 2014

nathanncohen mannequin commented Apr 23, 2014

videlec commented Apr 23, 2014

nathanncohen mannequin commented Apr 23, 2014

vbraun commented May 7, 2014

nathanncohen mannequin commented May 7, 2014

vbraun commented May 8, 2014

nathanncohen mannequin commented May 8, 2014

sagetrac-git mannequin commented May 8, 2014

sagetrac-git mannequin commented May 8, 2014

nathanncohen mannequin commented May 8, 2014

vbraun commented May 12, 2014

Stupid waste of time in graphs 1 #15704

Stupid waste of time in graphs 1 #15704

Comments

nathanncohen mannequin commented Jan 21, 2014

nathanncohen mannequin commented Jan 21, 2014

nathanncohen mannequin commented Jan 21, 2014

sagetrac-git mannequin commented Jan 21, 2014

sagetrac-git mannequin commented Jan 21, 2014

kcrisman commented Jan 21, 2014

nathanncohen mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

nathanncohen mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

sagetrac-git mannequin commented Jan 22, 2014

videlec commented Apr 22, 2014

nathanncohen mannequin commented Apr 23, 2014

videlec commented Apr 23, 2014

nathanncohen mannequin commented Apr 23, 2014

videlec commented Apr 23, 2014

nathanncohen mannequin commented Apr 23, 2014

videlec commented Apr 23, 2014

nathanncohen mannequin commented Apr 23, 2014

vbraun commented May 7, 2014

nathanncohen mannequin commented May 7, 2014

vbraun commented May 8, 2014

nathanncohen mannequin commented May 8, 2014

sagetrac-git mannequin commented May 8, 2014

sagetrac-git mannequin commented May 8, 2014

nathanncohen mannequin commented May 8, 2014

vbraun commented May 12, 2014