Data.Graph transitive closure

Andreas Abel andreas.abel at
Thu Jun 20 07:12:38 UTC 2019

Since there was nothing standard out there we (Agda) rolled our own.

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 
> <mailto:david.feuer at>> 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
>     Libraries at <mailto:Libraries at>
> _______________________________________________
> Libraries mailing list
> Libraries at

More information about the Libraries mailing list