Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement IsPartialOrderCoveringDigraph property and add CoveringDigraph versions for other properties #632

Open
reiniscirpons opened this issue Mar 27, 2024 · 0 comments
Labels
feature-request A label for feature requests performance A label for issues or PR related to performance

Comments

@reiniscirpons
Copy link
Collaborator

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.

@james-d-mitchell james-d-mitchell changed the title Implement IsPartialOrderCoveringDigraph property and add CoveringDigraph versions for other properties. Implement IsPartialOrderCoveringDigraph property and add CoveringDigraph versions for other properties Mar 28, 2024
@james-d-mitchell james-d-mitchell added performance A label for issues or PR related to performance feature-request A label for feature requests labels Mar 28, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature-request A label for feature requests performance A label for issues or PR related to performance
Projects
None yet
Development

No branches or pull requests

2 participants