<div dir="auto"><div>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.<br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jun 21, 2019, 12:37 PM Elliot Cameron <<a href="mailto:eacameron@gmail.com">eacameron@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif;font-size:small">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.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jun 21, 2019 at 10:10 AM Johannes Waldmann <<a href="mailto:johannes.waldmann@htwk-leipzig.de" target="_blank" rel="noreferrer">johannes.waldmann@htwk-leipzig.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> ... reasonably efficient transitive closure for Data.Graph ...<br>
<br>
well, since we have<br>
<br>
  type Graph = Array Vertex [Vertex]<br>
<br>
efficiency is already questionable?<br>
We cannot quickly check whether an edge is present,<br>
we cannot quickly get all predecessors of a vertex.<br>
But perhaps we don't need to. The underlying assumptions<br>
(cost of elementary operations)<br>
of <a href="http://www.cs.hut.fi/~enu/thesis.html" rel="noreferrer noreferrer" target="_blank">http://www.cs.hut.fi/~enu/thesis.html</a><br>
are not immediately clear.<br>
<br>
<br>
The cited Agda library has<br>
<br>
   newtype Graph n e = Graph (Map n (Map n e))<br>
<br>
<br>
Another option is to store back edges as well, as in<br>
<a href="https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Internal.hs" rel="noreferrer noreferrer" target="_blank">https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Internal.hs</a><br>
<br>
<br>
FGL fuses these two maps<br>
<br>
type GraphRep a b = IntMap (Context' a b)<br>
type Context' a b = (IntMap [b], a, IntMap [b])<br>
<br>
<a href="https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inductive.PatriciaTree.html#Gr" rel="noreferrer noreferrer" target="_blank">https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inductive.PatriciaTree.html#Gr</a><br>
<br>
<br>
this saves some look-ups (if you need successors and<br>
predecessors of the very same node)<br>
but this can't be used for relations,<br>
where start and end of an edge have different types.<br>
But for transitive closure, these types would agree anyway.<br>
<br>
<br>
What to make of this?<br>
<br>
Perhaps Data.Graph should be moved out of containers.<br>
The design space is just too large to single out one specific point?<br>
If we keep it, it would be very nice to document the complexity<br>
of algorithms. Section 7 of the King/Launchbury paper<br>
(cited in the API docs) claims "DFS in O(V+E)", backed up by<br>
experiments. This seems to be the main motivation for this library<br>
(DFS, with application: SCC). It's not clear whether the underlying<br>
design should be recommended for a general graph library.<br>
<br>
<br>
- Johannes<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank" rel="noreferrer">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div></div>