digraphs
Implement `IsBetweenCoverAndX` for partial orders and lattices
Computing all the edges of a partial order or lattice via DigraphReflexiveTransitiveClosure can be very time and memory intensive, especially for larger graphs. At the same time, many algorithms for lattices can be run quite efficiently even if some transitive edges are missing.
We should implement the functions
-
IsBetweenCoverAndPreorder- to check if a given digraph contains the cover relation of some preorder digraph, and is in turn contained in a preorder digraph. -
IsBetweenCoverAndPartialOrder- the equivalent functionality for partial order -
IsBetweenCoverAndLattice- for lattices.
One naive way to implement this would be to compute the reflexive transitive closure and then apply the appropriate filter, i.e. IsLatticeDigraph(DigraphReflexiveTransitiveClosure(D)); would compute IsBetweenCoverAndLattice. However as mentioned above, doing so is memory intensive on large graphs, see also #636 . So the idea would be to implement IsBetweenCoverAndLattice ideally without adding any extra edges to the given digraph.
See also #664 and #632 for related, but not quite same problems.
@zljlzljlz this is a writeup of what we spoke about earlier. I think the name I initially suggested for the function wasn't all that good and we should instead call the functions IsBetweenCoverAndX for each of the classes X.
As you mentioned, IsBetweenCoverAndPreorder should just always return true since this will always be the case. For IsBetweenCoverAndPartialOrder(D) I spoke to @james-d-mitchell briefly and we thought that maybe this would just involve checking if D is acyclic. For lattices we weren't really sure how to proceed but we can have a brainstorm next week!
