[Haskell-cafe] Re: fast graph algorithms without object identities

[apfelmus]

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.)


Regards,
apfelmus