Slow computation of strongly connected components

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-5.0.beta2

Issue created by migration from https://trac.sagemath.org/ticket/12235

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:1

Attachment: trac_12235.patch.gz

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:2

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 !

D.

[jdemeyer]

Merged: sage-5.0.beta2