Data.Graph transitive closure

[David Feuer]

Yes, Data.Graph is a weird, difficult-to-polish corner of containers. I'm
all for removing it, but there's one sticky point: it's managed to
accumulate some extremely important reverse dependencies. In particular,
GHC, Cabal, and Agda all use it. So if we want to deprecate it, we need a
really good plan for what happens next.

On Fri, Jun 21, 2019, 12:37 PM Elliot Cameron <eacameron at gmail.com> wrote:

> 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
>>
> _______________________________________________
> 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/dd2dd9ed/attachment.html>