[Haskell-cafe] fast graph algorithms without object identities

[Jan-Willem Maessen]

On Jan 31, 2008, at 5:39 AM, 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.

If so, I'd love to see this written up; I think it may be publishable  
if it isn't published already.

Note that even using ST techniques can take more than linear time,  
given an arbitrary purely-functionally-defined graph as input.  We  
can't (eg) assume that each node contains a reference, or that they  
are densely numbered, so we end up having to look them up in some  
fashion (though using a hash table can be reasonably quick if we  
uniquely number nodes).

-Jan-Willem Maessen

>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe