Opened 8 years ago

Closed 8 years ago

#12235 closed enhancement (fixed)

Slow computation of strongly connected components

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: Merged in: sage-5.0.beta2
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_12235.patch (1.9 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (4)

Changed 8 years ago by ncohen

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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 !

comment:3 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.