[Haskell-cafe] fast graph algorithms without object identities

[Alfonso Acosta]

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 <jmaessen at alum.mit.edu> wrote:
>
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>