[Haskell-cafe] Re: fast graph algorithms without object identities
Jan-Willem Maessen
jmaessen at alum.mit.edu
Tue Feb 26 14:43:28 EST 2008
On Feb 23, 2008, at 5:48 PM, apfelmus wrote:
> Henning Thielemann wrote:
>> It seems that algorithms on graphs can be implemented particularly
>> efficient in low-level languages with pointers and in-place
>> updates. E.g.
>> topological sort needs only linear time, provided that dereferencing
>> pointers requires constant time. I could simulate pointer
>> dereferencings
>> and pointer updates by Map yielding linear logarithmic time for
>> topological sort. I wonder if it is possible to write a linear time
>> topological sort using lazy evaluation, since the runtime system of
>> Haskell implementations is a graph processor based on pointers.
>
> First of all, topological sorting is only linear time because the 32
> or 64 bit used to label nodes aren't counted. Put differently,
> random access in constant time to a collection of n elements
> doesn't exist.
>
> That being said, we want to use arrays of course. Preferably in a
> "whole-meal" way that doesn't involve incremental state updates. A
> few minutes ago, I stumbled upon the lazyarray packages which
> points to the paper
>
> Thomas Johnsson.
> "Efficient Graph Algorithms Using Lazy Monolithic Arrays"
> http://citeseer.ist.psu.edu/95126.html
>
> which offers such a way! (Although I currently don't quite
> understand why this works, and these ad-hoc unique numbers bother me.)
I have an implementation of this in GHC based on some of the early ST
papers, if anyone is interested. It's rather old and may have bit-
rotted; cabalizing it is at the top of "whenever-I-get-time", along
with generic splittable supplies. Note that getting the laziness
right is somewhat tricky.
-Jan-Willem Maessen
More information about the Haskell-Cafe
mailing list