Data.Graph transitive closure

[Andreas Abel]

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 <david.feuer at gmail.com 
> <mailto:david.feuer at 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 at haskell.org <mailto: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
>