Opened 7 years ago

Last modified 7 years ago

#14000 closed enhancement

Speedup in GenericGraph.relabel() and two new options — at Version 7

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.8
Component: graph theory Keywords: graphs, relabelling
Cc: stumpc5, chapoton Merged in:
Authors: Nathann Cohen Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by aschilling)

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: trac_14000.patch

trac_14000-doctests.patch

Change History (9)

Changed 7 years ago by ncohen

comment:1 follow-up: Changed 7 years ago by ncohen

  • Cc stumpc5 chapoton added
  • Status changed from new to needs_review

comment:2 in reply to: ↑ 1 Changed 7 years ago by aschilling

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 follow-up: Changed 7 years ago by 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:4 in reply to: ↑ 3 Changed 7 years ago by aschilling

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

Nathann

Changed 7 years ago by ncohen

comment:6 Changed 7 years ago by ncohen

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 7 years ago by aschilling

  • Authors set to Nathann Cohen
  • Description modified (diff)
  • Keywords graphs relabelling added
Note: See TracTickets for help on using tickets.