fast graph algorithms without object identities
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.
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
You'd probably be interested to read
http://www.cs.chalmers.se/~koen/pubs/entry-asian99-lava.html
On Jan 31, 2008 9:56 PM, 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Feb 1, 2008, at 9:41 AM, Alfonso Acosta wrote:
You'd probably be interested to read http://www.cs.chalmers.se/~koen/pubs/entry-asian99-lava.html
It is indeed an interesting paper (that I've read and referred to several times over the years). But it's tricky to get right in practice! And sadly, while it solves the problem of sharing (or object equivalence) it doesn't give us some sort of total order or hash key, so there's no way to efficiently associate transient mutable state uniquely with each reference we encounter. For that we need one of the other solutions discussed and rejected. This is why Data.Unique provides a pure hashUnique function. The best option I know of here to get the desired time bounds with a purely-functional abstraction is to use a splittable supply of unique labels (which can be encapsulated in a monad if we like), then use ST to associate a hash table of references with the graph nodes while traversing the graph. -Jan
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
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
participants (4)
-
Alfonso Acosta -
apfelmus -
Henning Thielemann -
Jan-Willem Maessen