id	summary	reporter	owner	description	type	status	priority	milestone	component	resolution	keywords	cc	work_issues	upstream	reviewer	author	merged	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				N/A	David Coudert	Nathann Cohen	sage-5.0.beta2