# Data.Graph transitive closure

Elliot Cameron eacameron at gmail.com
Fri Jun 21 16:37:26 UTC 2019

```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

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]
>
> 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
>
>
>
> FGL fuses these two maps
>
> type GraphRep a b = IntMap (Context' a b)
> type Context' a b = (IntMap [b], a, IntMap [b])
>
>
>
>
> 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