#12933 closed enhancement (fixed)
Speedup in DiGraph.stronly_connected_components_digraph
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.1 |
Component: | graph theory | Keywords: | |
Cc: | nthiery | Merged in: | sage-5.1.beta5 |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Let it be said that I hate vertex labels.
Before:
sage: g = digraphs.RandomDirectedGNP(2000,.2) sage: g.strongly_connected_components_digraph() Exception: The user died of old age
After :
sage: time g.strongly_connected_components_digraph() Digraph on 1 vertex Time: CPU 2.78 s, Wall: 2.79 s
Which is already far, far too much. And if it is still slow it is -- of course -- only because of labels.
Nathann
Attachments (1)
Change History (10)
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
Changed 7 years ago by
comment:3 Changed 7 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
The running time improvement is impressive, although I had no "user died of old age" exception. Considering a linear time algorithm, the running time is still high, but I don't know how to be faster in python.
The patch is working perfectly and passes all tests (graph.py and digraph.py). I give positive review.
comment:4 Changed 7 years ago by
Thaaaaaaaaaanks ! :-)
Nathann
comment:5 Changed 7 years ago by
Please fill in your real name in the Author / Reviewer fields.
comment:6 Changed 7 years ago by
comment:7 Changed 7 years ago by
- Merged in set to sage-5.1.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
comment:8 Changed 7 years ago by
Nathann, you are my hero of the day!
I was running a calculation while Anne was presenting a talk about monoids. My calculation was taking forever (minutes? more? I killed it). I applied your patch, and it went down to 5s. And now I have a little counter example that she can announce at the end of her talk :-)
comment:9 Changed 7 years ago by
WOooooooooooohooooooooooooooooo !!!! I am a HeroooOOOOOOooooooooooooooo !!!! O_O
God ! At long, long last... :-D
Nathann
(Ninja patch -- nobody will notice that I'm exposing a parameter for graph coloring functions in this ticket
:-p
)