#12235: Slow computation of strongly connected components
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Nathann Cohen
Merged: | Dependencies:
----------------------------+-----------------------------------------------
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12235>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
