Data.Graph transitive closure

[Elliot Cameron]

I've actually wondered why Data.Graph existed since it is obviously not
written for serious/heavy usage. So I do see an argument for deprecating it
instead of polishing it.

On Fri, Jun 21, 2019 at 10:10 AM Johannes Waldmann <
johannes.waldmann at htwk-leipzig.de> wrote:

> > ... reasonably efficient transitive closure for Data.Graph ...
>
> well, since we have
>
>   type Graph = Array Vertex [Vertex]
>
> efficiency is already questionable?
> We cannot quickly check whether an edge is present,
> we cannot quickly get all predecessors of a vertex.
> But perhaps we don't need to. The underlying assumptions
> (cost of elementary operations)
> of http://www.cs.hut.fi/~enu/thesis.html
> are not immediately clear.
>
>
> The cited Agda library has
>
>    newtype Graph n e = Graph (Map n (Map n e))
>
>
> Another option is to store back edges as well, as in
>
> https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Internal.hs
>
>
> FGL fuses these two maps
>
> type GraphRep a b = IntMap (Context' a b)
> type Context' a b = (IntMap [b], a, IntMap [b])
>
>
> https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inductive.PatriciaTree.html#Gr
>
>
> this saves some look-ups (if you need successors and
> predecessors of the very same node)
> but this can't be used for relations,
> where start and end of an edge have different types.
> But for transitive closure, these types would agree anyway.
>
>
> What to make of this?
>
> Perhaps Data.Graph should be moved out of containers.
> The design space is just too large to single out one specific point?
> If we keep it, it would be very nice to document the complexity
> of algorithms. Section 7 of the King/Launchbury paper
> (cited in the API docs) claims "DFS in O(V+E)", backed up by
> experiments. This seems to be the main motivation for this library
> (DFS, with application: SCC). It's not clear whether the underlying
> design should be recommended for a general graph library.
>
>
> - Johannes
>
>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20190621/1b60770e/attachment.html>