Slow computation of strongly connected components

[ncohen]

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

[dcoudert]

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 !