I just noticed that Data.Graph doesn't offer a transitive closure operation. Looking into implementing one, I discovered that doing so efficiently has been the subject of non-trivial research [*]. So if there's any demand, we should try to implement a reasonably efficient version in containers. Anybody want one?
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
It's hard to imagine reaching for a graph without some thought that you'd want to compute a closure. I've wanted this in the past, but I've never thought seriously about using Data.Graph for it. Perhaps this is why? On Wed, Jun 19, 2019 at 6:20 PM David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
I want one, because, why not? It might be useful to those who use that API. I'm always excited to see APIs become more complete. On Wed, Jun 19, 2019, 6:39 PM Elliot Cameron <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Elliot Cameron-2
Since there was nothing standard out there we (Agda) rolled our own.
https://github.com/agda/agda/blob/f3f82fa0510335087653ba715cef06a5702deb18/src/full/Agda/Utils/Graph/AdjacencyMap/Unidirectional.hs#L719-L877 There are even two versions (complete (Abel) and gaussJordanFloydWarshallMcNaughtonYamada (Danielsson)) which behave differently wrt. runtime, so we use both, for different purposes. Algorithms might look different for different graph representations, we use a version of adjacency lists which works also well for sparse graphs. On 2019-06-20 00:38, Elliot Cameron wrote: > It's hard to imagine reaching for a graph without some thought that > you'd want to compute a closure. I've wanted this in the past, but I've > never thought seriously about using Data.Graph for it. Perhaps this is why? > > On Wed, Jun 19, 2019 at 6:20 PM David Feuer <[hidden email] > <mailto:[hidden email]>> wrote: > > I just noticed that Data.Graph doesn't offer a transitive closure > operation. Looking into implementing one, I discovered that doing so > efficiently has been the subject of non-trivial research [*]. So if > there's any demand, we should try to implement a reasonably > efficient version in containers. Anybody want one? > > [*] http://www.cs.hut.fi/~enu/thesis.html > _______________________________________________ > Libraries mailing list > [hidden email] <mailto:[hidden email]> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
> ... 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 <[hidden email]> wrote: > ... reasonably efficient transitive closure for Data.Graph ... _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Elliot Cameron-2
> I've actually wondered why Data.Graph existed since it is obviously not > written for serious/heavy usage. But it was! As I understand, it was originally part of GHC (ghc-0.29/ghc/compiler/utils/Digraph.lhs) for computing SCCs (in the graph of dependencies of declarations). So we can assume that it does this well. And I guess it's used for the very same purpose in Cabal and Agda. - J. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
The big problem is that when it was broken off into containers, there was no attempt to add appropriate abstraction barriers. So it's ... awkward. On Fri, Jun 21, 2019, 2:10 PM Johannes Waldmann <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
i've definitely used the efficient SCC bits of Data.Graph in the past. graphs are just such a rich area that it seems doubtful that there'll ever be a one true library On Fri, Jun 21, 2019 at 2:21 PM David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On 21.06.19 20:44, Carter Schonwald wrote:
> ... it seems doubtful that there'll > ever be a one true [graph] library Yes. My point was that Data.Graph isn't a "graph library" (it was never meant to be) - it's a "DFS/SCC library". - J. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
Feedback from an occasional Haskell user:
I would use it. I've noticed that computational implementations of "transitive closure" often deviate from my (user-level) understanding of the standard mathematical definition. Specifically, self loops are often discarded. I assume/hope the math def will be used in haskell. A prominent example is Mathematica's TransitiveClosureGraph command. E.g., `TransitiveClosureGraph[{a -> b, b -> c, c -> a}]` has no self loops, even though `a` is clearly reachable from `a`, and TransitiveClosureGraph[{a -> a, b -> b, c -> c}]` is empty!) In the past networkx also had this flaw (although they indicated a plan to fix this; I'd have to recheck the current status). Cheers, Alan Isaac PS My apologies if I misread your post; I understood it to request user feedback, not just developer assessment. On 6/20/2019 8:00 AM, David wrote: > I just noticed that Data.Graph doesn't offer a transitive closure > operation. Looking into implementing one, I discovered that doing so > efficiently has been the subject of non-trivial research [*]. So if there's > any demand, we should try to implement a reasonably efficient version in > containers. Anybody want one? _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
> .. I would use it.
what is your use case? Can you extract test cases that could be used to validate correctness and complexity of an implementation? Specific question: assume the implementation gives you S = transitive-closure-of(R). Then what do you do with S (in your application)? Does Data.Graph (i.e., array of lists of successors) have the right structure? E.g., it is inefficient to test for membership in these lists. But lists are fine if you need to handle all successors anyway. Evaluation of (recursive) Datalog queries is another application area of transitive closure algorithms. (e.g., https://doi.org/10.1007/BF01264013 ) - J. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Johannes Waldmann-2
Dear Johannes, Carter, David, libraries,
As a formal methodist who likes and uses functional languages a lot, I looked at doing this in a "principled" way a long time ago. The idea was to formally specify an abstract graph datatype and various graph operations (create, query, modify, transitive closure, etc, etc...) and then show correctness of of simple but possibly inefficient implementations. Then the plan was to develop efficient operations, including use of appropriate graph representation types, and show formally that they were refinements of the inefficient ones. It rapidly became *very* clear that the best/only? way to do something efficiently was to decide which operations were important, and specialise for those. Woe betide you if you left out an operator that later would be important, because its efficient implementation could well force you to do complete re-design. Basically, it is not feasible to design a large/general-purpose graph library that does everything efficiently. I then got distracted by something else..... Regards, Andrew > On 21 Jun 2019, at 19:48, Johannes Waldmann <[hidden email]> wrote: > > On 21.06.19 20:44, Carter Schonwald wrote: > >> ... it seems doubtful that there'll >> ever be a one true [graph] library > > Yes. My point was that Data.Graph isn't a "graph library" > (it was never meant to be) - it's a "DFS/SCC library". > > - J. > _______________________________________________ > Libraries mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries -------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ -------------------------------------------------------------------- _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Hi,
> I looked at doing this in a "principled" way a long time ago. > I then got distracted by something else..... You don't say :-) Well, short-term suggestion (for containers:Data.Graph) don't change existing code, but improve documentation and do some benchmarking https://github.com/haskell/containers/issues/648 https://github.com/haskell/containers/issues/649 @David: perhaps you can label these issues as "nice to have" so it does not look like "bugs that need fixing". Benchmarking would make for a nice student project? In fact, I will pitch this to my current class. - Johannes _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
I have been bit before by Data.Graph... I think it's that since it's a
type synonym, it inherits Eq from Array, but it doesn't have a normalized form, so Eq is misleading in that topologically equal graphs are not Eq... something like that. And it can't be fixed because it's just a type synonym over Array. That's probably the "no attempt to add abstraction barriers" alluded to above. But the reason I used it in the first place was I wanted a graph, and behold there is Data.Graph already installed. So it's presence in containers gives it the impression of authority, but it's definitely not as well developed as the other types in containers. Since it seems like it can't be moved or made into a proper type without breaking things, we could at least have some caveats in the documentation, saying what it's appropriate for and what it's not. And maybe warning about that Eq thing. So I guess I'm seconding the "just add documentation" suggestion. Also while I'm here it's weird and confusing how it silently re-exports Data.Tree... On Mon, Jun 24, 2019 at 4:02 AM Johannes Waldmann <[hidden email]> wrote: > > Hi, > > > I looked at doing this in a "principled" way a long time ago. > > I then got distracted by something else..... > > You don't say :-) > > Well, short-term suggestion (for containers:Data.Graph) > don't change existing code, > but improve documentation and do some benchmarking > https://github.com/haskell/containers/issues/648 > https://github.com/haskell/containers/issues/649 > > @David: perhaps you can label these issues as "nice to have" > so it does not look like "bugs that need fixing". > Benchmarking would make for a nice student project? > In fact, I will pitch this to my current class. > > - Johannes > _______________________________________________ > Libraries mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
If we could boot it out of containers and into its own package, that would make me happier; then I wouldn't have such a weird, special-purpose structure sitting around in an otherwise general-purpose library. On Mon, Jun 24, 2019, 1:38 PM Evan Laforge <[hidden email]> wrote: I have been bit before by Data.Graph... I think it's that since it's a _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On 24.06.19 20:22, David Feuer wrote:
> If we could boot it out of containers and into its own package, https://hackage.haskell.org/package/GraphSCC-1.0.4/docs/Data-Graph-SCC.html ? _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
If Iavor wants to adopt Data.Graph into his package, I'm fine with that. I'm not exactly clear on what his package adds to the mix, but if it's not my problem it's not my problem. GHC HQ needs to sign off on adding it as a boot package, but its dependencies (base, array, containers) should make that acceptable. On Mon, Jun 24, 2019, 2:25 PM Johannes Waldmann <[hidden email]> wrote: On 24.06.19 20:22, David Feuer wrote: _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Free forum by Nabble | Edit this page |