Faster graph SCCs

Don Stewart dons at galois.com
Wed Jul 2 18:02:34 EDT 2008


iavor.diatchki:
> Hi,
> I have implemented Tarjan's algorithm for computing the strongly
> connected components of a graph.  It is considerably faster then
> what's available in the "containers" package for larger graphs (see
> the attached picture). It would be nice to replace the existing
> implementation in the containers package, but I though that I'd check
> with the mailing list before I do this.  If you want to try it out, I
> have put the code on hackage:
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/GraphSCC
> 
> -Iavor

+1 

The Data.Graph library needs some love, and these numbers are
fairly awesome.

-- Don


More information about the Libraries mailing list