Data.Graph transitive closure

Johannes Waldmann johannes.waldmann at
Sat Jun 22 13:03:14 UTC 2019

> .. 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., )

- J.

More information about the Libraries mailing list