Faster graph SCCs

[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


_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Neil Mitchell]

Hi Iavor,

>  connected components of a graph.  It is considerably faster then
>  what's available in the "containers" package for larger graphs (see
>  the attached picture).

Is it slower in any circumstances? If so, by how much?

However, that graph makes it look like a fairly simple choice...

Thanks

Neil
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Don Stewart-2]

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
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Iavor Diatchki]

Hi,
I don't know of any examples when it is slower.
-Iavor


On Wed, Jul 2, 2008 at 2:24 PM, Neil Mitchell <ndmitchell@...> wrote:

> Hi Iavor,
>
>>  connected components of a graph.  It is considerably faster then
>>  what's available in the "containers" package for larger graphs (see
>>  the attached picture).
>
> Is it slower in any circumstances? If so, by how much?
>
> However, that graph makes it look like a fairly simple choice...
>
> Thanks
>
> Neil
>

_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries