It would be useful to implement IsPartialOrderCoveringDigraph and IsLatticeCoveringDigraph properties which check that a given digraph is the covering relation (the reflexive transitive reduction) of some partial order or lattice respectively. In a similar vein, CoveringDigraph versions of any other order properties in Chapter 6.4 of the Digraphs documentation. See also issue #84 for a discussion of properties of lattices and some suggestions relating to covering relations.
The motivation behind this is that the IsPartialOrderDigraph and IsLatticeDigraph properties both require that the underlying digraph is transitive. This matches the mathematical definition, however the covering relation (transitive reflexive reduction) of a partial order or lattice often has dramatically less edges. By extension there are often more efficient algorithms to check if a given digraph is the covering relation of some partial order or lattice.
As an example, consider the full binary tree of height 14:
gap> T := BinaryTree(14);
<immutable digraph with 16383 vertices, 16382 edges>
gap> S := DigraphReflexiveTransitiveClosure(T);
<immutable preorder digraph with 16383 vertices, 212993 edges>
Note that T has an order of magnitude less edges than S. See also this stack exchange post on testing if a DAG is a lattice, the top answer discusses checking if the graph is the covering relation of a lattice for improving the time taken.
A further suggestion would be to implement versions of the properties which accept an arbitrary subrelation of a partial order or lattice. I.e. a digraph whose reflexive transitive closure is a partial order or lattice.
It would be useful to implement
IsPartialOrderCoveringDigraphandIsLatticeCoveringDigraphproperties which check that a given digraph is the covering relation (the reflexive transitive reduction) of some partial order or lattice respectively. In a similar vein,CoveringDigraphversions of any other order properties in Chapter 6.4 of theDigraphsdocumentation. See also issue #84 for a discussion of properties of lattices and some suggestions relating to covering relations.The motivation behind this is that the
IsPartialOrderDigraphandIsLatticeDigraphproperties both require that the underlying digraph is transitive. This matches the mathematical definition, however the covering relation (transitive reflexive reduction) of a partial order or lattice often has dramatically less edges. By extension there are often more efficient algorithms to check if a given digraph is the covering relation of some partial order or lattice.As an example, consider the full binary tree of height 14:
Note that
Thas an order of magnitude less edges thanS. See also this stack exchange post on testing if a DAG is a lattice, the top answer discusses checking if the graph is the covering relation of a lattice for improving the time taken.A further suggestion would be to implement versions of the properties which accept an arbitrary subrelation of a partial order or lattice. I.e. a digraph whose reflexive transitive closure is a partial order or lattice.