Opened 10 years ago

Closed 10 years ago

#14000 closed enhancement (fixed)

Speedup in GenericGraph.relabel() and two new options

Reported by: Nathann Cohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.8
Component: graph theory Keywords: graphs, relabelling
Cc: Christian Stump, Frédéric Chapoton Merged in: sage-5.8.beta2
Authors: Nathann Cohen Reviewers: Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

Because of some weird graphs built by ennemies of The Good Graph People, it seems that most of the work done by GenericGraph?.relabel() is totally useless. This patch adds two optional arguments to this method, which let the users enable/disable tests.

--- Apply:

  1. trac_14000.patch
  2. trac_14000-doctests.patch

Attachments (2)

trac_14000.patch (7.1 KB) - added by Nathann Cohen 10 years ago.
trac_14000-doctests.patch (2.0 KB) - added by Nathann Cohen 10 years ago.

Download all attachments as: .zip

Change History (17)

Changed 10 years ago by Nathann Cohen

Attachment: trac_14000.patch added

comment:1 Changed 10 years ago by Nathann Cohen

Cc: Christian Stump Frédéric Chapoton added
Status: newneeds_review

comment:2 in reply to:  1 Changed 10 years ago by Anne Schilling

Nathann, you need to put in some tests that show how the code works with the new inputs set to False. Also, please post a timing comparison before and after the patch.

Thanks,

Anne

comment:3 Changed 10 years ago by Nathann Cohen

O_o

Well... The code works the same way. It just does not check some things internally... The output does not change O_o

Nathann

comment:4 in reply to:  3 Changed 10 years ago by Anne Schilling

I know, but it is still good to put in a test that checks that it works the same ;-)

Replying to ncohen:

O_o

Well... The code works the same way. It just does not check some things internally... The output does not change O_o

Nathann

comment:5 Changed 10 years ago by Nathann Cohen

Yep yep I'm doing it right now, but the point is that I am not totally sure that it does not produce a memory leak somewhere O_o

Nathann

Changed 10 years ago by Nathann Cohen

Attachment: trac_14000-doctests.patch added

comment:6 Changed 10 years ago by Nathann Cohen

A timing, just for the show :

Before :

sage: g = graphs.KneserGraph(11,4)
sage: %time g.relabel()           
CPU times: user 0.37 s, sys: 0.00 s, total: 0.37 s
Wall time: 0.37 s

After :

sage: g = graphs.KneserGraph(11,4)
sage: %time g.relabel()           
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s

Ready for review again ! ;-)

Nathann

comment:7 Changed 10 years ago by Anne Schilling

Authors: Nathann Cohen
Description: modified (diff)
Keywords: graphs relabelling added

comment:8 in reply to:  5 ; Changed 10 years ago by Anne Schilling

Replying to ncohen:

Yep yep I'm doing it right now, but the point is that I am not totally sure that it does not produce a memory leak somewhere O_o

What does this mean? Do you mean disabling the option is at the user's own risk?

comment:9 in reply to:  8 ; Changed 10 years ago by Nathann Cohen

What does this mean? Do you mean disabling the option is at the user's own risk?

Precisely ! I wrote that in the doctest itself :

"Checking that all vertices have an image can require some time, and this feature can be disabled (at your own risk)"

If you "rename" the vertices of a graph in such a way that two vertices end up having the same name at the end of the procedure, I can totally imagine that some data will be lost on the way :-P

Nathann

comment:10 in reply to:  9 ; Changed 10 years ago by Anne Schilling

Ok, then I am happy with your patch!

Anne

comment:11 Changed 10 years ago by Anne Schilling

Status: needs_reviewpositive_review

comment:12 Changed 10 years ago by Anne Schilling

Reviewers: Anne Schilling

comment:13 in reply to:  10 Changed 10 years ago by Nathann Cohen

Ok, then I am happy with your patch!

Cool. Thanks for reviewing it ! :-D

Nathann

comment:14 Changed 10 years ago by Jeroen Demeyer

Description: modified (diff)

comment:15 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.8.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.