Make CombinatorialPolyhedron a base class for polyhedra/lattice polytopes/cones

[novoselt]

While thinking about uniformizing lattice polytopes and cones/fans, I came to the conclusion that it would be nice to abstract the current "face lattice relations" of cones to a separate class, say CombinatorialPolyhedron, and include it as a base class for cones, lattice polytopes, and polyhedra.

Current situation with faces is "very different":

• faces of cones are cones, represented by the same class;
• faces of lattice polytopes are objects of a different class with different behaviour of methods with the same name, e.g. for polytopes points returns a matrix, for their faces - a list of some indices;
• faces of polyhedra are also objects of some special class.
  I think that ideally all faces of X must be represented by objects of the same class as X, and some methods can be the same for all of the above three situations. It may also work nicely for collections of objects (i.e. fans and polyhedral complexes).

So, an object of CombinatorialPolyhedron, say cp should have the following properties:

1. cp knows its "ambient structure" A, which can be either an object of the same type, or their collection. E.g. each cone sits either in another cone or in a fan. Each polyhedron sits in another polyhedron or a polyhedron complex.
2. A knows how to compute its whole face lattice and cp knows how to access it and use it to create the face lattice of cp. This is good for efficiency as well as convenience and face walks:
3. cp can return facets, facet_of, and adjacent elements of the face lattice of A relative to cp.
4. Since it may happen that cp IS A, cp should know how to compute its face lattice. Hasse_diagram_from_incidences computes it quite efficiently if incidences of vertex-to-facet and facet-to-vertex are known, so perhaps derived classes should provide this information in a uniform way and then the actual computation is done in CombinatorialPolytope. Or maybe it would be more convenient to do it in each derived class separately.

It kind of seems that I just want to inherit polyhedra objects from a poset element class, but I don't think it will work: I am definitely against creating the whole face lattice with all its elements when a single polyhedron is created, which is required for using current Poset function. But then what should be the parent of these elements? On the other hand, if it was possible to construct a poset without specifying all elements but only providing a way to compare elements, it could be quite nice! (See #10783.)

In principle, one may think about unifying all polyhedra classes into a single one, but I don't think that it is a good idea from the efficiency point of view. I think that in general the current separation with imposed restrictions is quite reasonable and convenient, especially if one can easily switch from one representation to another:

• cones are always centered at the origin and thought of as fan elements or their dual, they are represented by some lattice points;
• lattice polytopes are bounded and thought of as related to toric geometry as well and are represented by lattice points;
• polyhedra allow complete generality: no binding to any underlying lattice, working with inexact fields, maybe even strict inequalities once Volker's PPL package is in.

CC: @vbraun @sagetrac-mhampton @mo271 @jplab

Component: geometry

Issue created by migration from https://trac.sagemath.org/ticket/10777

[novoselt]

comment:1

Yay, I got a cool number for this ticket ;-)

Volker, I know that you are also thinking about refactoring polyhedra code, so perhaps it would be nice to coordinate with this ticket. I am not sure if I will work on this issue before summer (I definitely will not before April), so feel free to take over if you agree that this is a good idea in general.

If anyone thinks that it is a bad idea, please speak up!

[novoselt]

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@
 3. `cp` can return `facets`, `facet_of`, and `adjacent` elements of the face lattice of `A` relative to `cp`.
 4. Since it may happen that `cp` IS `A`, `cp` should know how to compute its face lattice. `Hasse_diagram_from_incidences` computes it quite efficiently if incidences of vertex-to-facet and facet-to-vertex are known, so perhaps derived classes should provide this information in a uniform way and then the actual computation is done in `CombinatorialPolytope`. Or maybe it would be more convenient to do it in each derived class separately.
 
-It kind of seems that I just want to inherit polyhedra objects from a poset element class, but I don't think it will work: I am definitely against creating the whole face lattice with all its elements when a single polyhedron is created, which is required for using current `Poset` function. But then what should be the parent of these elements? On the other hand, if it was possible to construct a poset without specifying all elements but only providing a way to compare elements, it could be quite nice!
+It kind of seems that I just want to inherit polyhedra objects from a poset element class, but I don't think it will work: I am definitely against creating the whole face lattice with all its elements when a single polyhedron is created, which is required for using current `Poset` function. But then what should be the parent of these elements? On the other hand, if it was possible to construct a poset without specifying all elements but only providing a way to compare elements, it could be quite nice! (See #10783.)
 
 In principle, one may think about unifying all polyhedra classes into a single one, but I don't think that it is a good idea from the efficiency point of view. I think that in general the current separation with imposed restrictions is quite reasonable and convenient, especially if one can easily switch from one representation to another:
 * cones are always centered at the origin and thought of as fan elements or their dual, they are represented by some lattice points;

[kliem]

comment:4

In #26887 I will create new class with this name. Once this is done, it will be able to handle Polytopes and Lattice Polytopes. I don't know about cones.

[kliem]

comment:5

Maybe the following post is better suited for sage-devel, please tell me, if this is the case.

#26887 has been merged now (with bug fix #27987 yet to be merged) implementing a class CombinatorialPolyhedron.

This class has a structure a bit different then proposed here. It basically knows the vertex-facet-incidences and then can compute e.g. the f-vector or the face lattice. (Still some work to obtain a combinatorial polyhedron from a cone, but of course can be done.)

Now with #27063, I want to compute combinatorial properties of polyhedra with CombinatorialPolyhedron.

There are at least two ways of doing this:

• Have a method that accesses the combinatorial polyhedron (much easier).
• Inherit Polyhedron_base from CombinatorialPolyhedron.

Is it still desirable to inherit lattice polytope, cone and polyhedra from common combinatorial class? Is the class CombinatorialPolyhedron more or less suited for this purpose?

[novoselt]

comment:6

I think it would be desirable to have a common class for shared functionality, both to avoid code duplication and to ensure consistency. However I am personally not likely to work on it in the foreseeable future due to a bunch of other activities. Volker, I imagine, also has his plate full, to put it lightly ;-)

[kliem]

comment:7

Ok. From your first comment on the ticket, I figured that you were busy with other things.

I see what I can do about it. I did spend a lot of time on CombinatorialPolyhedron and it would be great to make good use of it.