id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
12235 Slow computation of strongly connected components ncohen jason ncohen rlm "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" enhancement closed major sage-5.0 graph theory fixed sage-5.0.beta2 Nathann Cohen David Coudert N/A