Opened 10 years ago
Closed 10 years ago
#12235 closed enhancement (fixed)
Slow computation of strongly connected components
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-5.0.beta2 | |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Helloooooooo !!!
After three days coding a *loooot* of things that may (or may not) prove useful later, I noticed there was a quick way to fix this crazy slowness in "strongly_connected_components".
I hope I will be able to improve it a bit more later, but I noticed many importants things that need fixing while working on this patch.
NetworkX
sage: import networkx sage: g = digraphs.RandomDirectedGNP(1000,.1).networkx_graph() sage: %timeit networkx.strongly_connected_components(g) 5 loops, best of 3: 103 ms per loop sage: g = digraphs.RandomDirectedGNP(1000,.1).networkx_graph() sage: %timeit networkx.strongly_connected_components(g) 5 loops, best of 3: 102 ms per loop sage: g = digraphs.RandomDirectedGNP(1000,.1).networkx_graph() sage: %timeit networkx.strongly_connected_components(g) 5 loops, best of 3: 103 ms per loop
Before (Sage)
sage: g = digraphs.RandomDirectedGNP(1000,.1) sage: %timeit g.strongly_connected_components() 5 loops, best of 3: 186 ms per loop sage: g = digraphs.RandomDirectedGNP(1000,.1) sage: %timeit g.strongly_connected_components() 5 loops, best of 3: 183 ms per loop sage: g = digraphs.RandomDirectedGNP(1000,.1) sage: %timeit g.strongly_connected_components() 5 loops, best of 3: 184 ms per loop
After (Sage)
sage: g = digraphs.RandomDirectedGNP(1000,.1) sage: %timeit g.strongly_connected_components() 25 loops, best of 3: 28.9 ms per loop sage: g = digraphs.RandomDirectedGNP(1000,.1) sage: %timeit g.strongly_connected_components() 25 loops, best of 3: 28.4 ms per loop sage: g = digraphs.RandomDirectedGNP(1000,.1) sage: %timeit g.strongly_connected_components() 25 loops, best of 3: 29.8 ms per loop
I also added a LONG doctests that checks the computations are correct by comparing the result with NetworkX
sage: import networkx sage: for i in range(100): # long ... g = digraphs.RandomDirectedGNP(100,.05) # long ... h = g.networkx_graph() # long ... scc1 = g.strongly_connected_components() # long ... scc2 = networkx.strongly_connected_components(h) # long ... s1 = Set(map(Set,scc1)) # long ... s2 = Set(map(Set,scc2)) # long ... if s1 != s2: # long ... print "Ooch !" # long
Now, there are many things left to improve in the library, but I hope this settles the SCC issue reported in https://groups.google.com/d/topic/sage-support/MSTS8fC5fyg/discussion
Yeah ! :-D
Nathann
Attachments (1)
Change History (4)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
comment:3 Changed 10 years ago by
- Merged in set to sage-5.0.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
The patch installs correctly and all test pass (sage -t) with sage-5.0.beta1. I did several experiments on various sizes of GNP graphs with various density. The results are corrects and it is faster than networkx.
Good work !