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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
