Data.Graph transitive closure

[Alan Isaac]

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?