Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#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)

trac_12933.patch (3.9 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by ncohen

(Ninja patch -- nobody will notice that I'm exposing a parameter for graph coloring functions in this ticket :-p)

Changed 7 years ago by ncohen

comment:3 Changed 7 years ago by dcoudert

  • 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 ncohen

Thaaaaaaaaaanks ! :-)

Nathann

comment:5 Changed 7 years ago by jdemeyer

Please fill in your real name in the Author / Reviewer fields.

comment:6 Changed 7 years ago by dcoudert

  • Authors set to Nathann Cohen

comment:7 Changed 7 years ago by jdemeyer

  • 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 nthiery

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 ncohen

WOooooooooooohooooooooooooooooo !!!! I am a HeroooOOOOOOooooooooooooooo !!!! O_O

God ! At long, long last... :-D

Nathann

Note: See TracTickets for help on using tickets.