Opened 6 years ago
Closed 6 years ago
#14000 closed enhancement (fixed)
Speedup in GenericGraph.relabel() and two new options
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: | sage-5.8.beta2 |
Authors: | Nathann Cohen | Reviewers: | Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
Attachments (2)
Change History (17)
Changed 6 years ago by
comment:1 follow-up: ↓ 2 Changed 6 years ago by
- Cc stumpc5 chapoton added
- Status changed from new to needs_review
comment:2 in reply to: ↑ 1 Changed 6 years ago by
comment:3 follow-up: ↓ 4 Changed 6 years ago by
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 6 years ago by
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 follow-up: ↓ 8 Changed 6 years ago by
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 6 years ago by
comment:6 Changed 6 years ago by
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 6 years ago by
- Description modified (diff)
- Keywords graphs relabelling added
comment:8 in reply to: ↑ 5 ; follow-up: ↓ 9 Changed 6 years ago by
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 ; follow-up: ↓ 10 Changed 6 years ago by
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 ; follow-up: ↓ 13 Changed 6 years ago by
Ok, then I am happy with your patch!
Anne
comment:11 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:12 Changed 6 years ago by
- Reviewers set to Anne Schilling
comment:13 in reply to: ↑ 10 Changed 6 years ago by
Ok, then I am happy with your patch!
Cool. Thanks for reviewing it ! :-D
Nathann
comment:14 Changed 6 years ago by
- Description modified (diff)
comment:15 Changed 6 years ago by
- Merged in set to sage-5.8.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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