Re: Data.Graph transitive closure

Since there was nothing standard out there we (Agda) rolled our own. https://github.com/agda/agda/blob/f3f82fa0510335087653ba715cef06a5702deb18/s... 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 mailto:david.feuer@gmail.com> 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 Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries