Transition of combinatorial computations of Polyhedron to Combinatorial Type

[kliem]

In #26887 we created a new class, that handles the calculations depending only on the combinatorial type more quickly.

The goal of this ticket is to make use of this class throughout Polyhedron_base.

Add methods:

• Add CombinatorialPolyhedron method to Polyhedron objects #28621: Add method combinatorial_polyhedron,
• Use CombinatorialPolyhedron to obtain faces of polyhedra #28646: face_generator,
• Use CombinatorialPolyhedron to obtain faces lattice of polyhedra #28982: hasse_diagram,
• Add simplicity and simpliciality to polyhedra #29186: simpliciality, simplicity

Replace the existing computation:

• Let CombinatorialPolyhedron handle f_vector of polyhedra #28625: f_vector,
• Use CombinatorialPolyhedron to obtain faces of polyhedra #28646 faces,
• Compute graph of polyhedron with CombinatorialPolyhedron #28626: graph/vertex_graph,
• graph/vertex_graph with incidences instead of Vrepresentation/expose the names=False option
• Polyhedron_base.vertex_adjacency_matrix: Do not use face_lattice #32666: vertex_adjacency_matrix
• vertex_digraph
• Polyhedron_base.facet_adjacency_matrix: Do not use face_lattice #33008: facet_adjacency_matrix,
• Use CombinatorialPolyhedron to obtain faces lattice of polyhedra #28982 face_lattice.

Migrate code to CombinatorialPolyhedron:

• Move is_prism and is_bipyramid to combinatorial polyhedron #33009: is_prism
• is_combinatorially_isomorphic
• Migrate neighborly to combinatorial polyhedron #29565: is_neighborly, neighborliness
• Move is_simple and is_simplicial to CombinatorialPolyhedron #29078: is_simple,is_simplicial
• Migrate is_lawrence_polytope and is_pyramid to combinatorial polyhedron #29189: is_lawrence_polytope
• is_self_dual
• Migrate is_lawrence_polytope and is_pyramid to combinatorial polyhedron #29189: is_pyramid
• Move is_prism and is_bipyramid to combinatorial polyhedron #33009: is_bipyramid
• combinatorial_automorphism_group
• Move vertex facet graph to combinatorial polyhedron #29188: vertex_facet_graph

NOTE: The remaining bulletins are taken care of by exposing the adjacency matrices.

Depends on #28621
Depends on #28625
Depends on #28626

CC: @jplab @mkoeppe

Component: geometry

Keywords: polyhedron, face lattice

Author: Jonathan Kliem

Reviewer: Matthias Koeppe

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

[embray]

comment:1

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

[kliem]

Changed dependencies from #26887 to #26887, #27987

[kliem]

Branch: public/27063

[kliem]

Commit: 25407f8

[kliem]

Last 10 new commits:

9b69f50	added documentation and examples to each module
4e8fd8c	correct hyperlinks
72ac3b0	documentation fix
611099f	Do not iterate twice for CombinatorialPolyhedron.facets()
d38e130	added combinatorial face
ca60665	improved docstring in list_of_all_faces
abe00b6	fixed small issues
8765313	A number of small edits.
d419d72	Merge branch 'public/26887' of git://trac.sagemath.org/sage into public/27063
25407f8	faces, f_vector, vertex_graph, vertex_digraph, neighborliness now use CombinatorialPolyhedron

[kliem]

Author: Jonathan Kliem

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c4ccf86

face lattice by CombinatorialPolyhedron

[sagetrac-git]

Changed commit from 25407f8 to c4ccf86

[embray]

comment:5

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

[jplab]

comment:7

Concerning the .faces() method. Currently, .iter_face only deals with proper faces. ... is that the intended behavior?

From an old list (so maybe some of them are renamed), I also saw the following methods make use of .face_lattice, and probably would benefit from the combinatorial polyhedra:

• adjacency_matrix
• facet_adjacency_matrix
• facial_adjacencies
• is_simple
• vertex_adjacency_matrix

It would be nice to make a thorough checking of which methods make use of "old style face lattice" things. It would be bad to not make the whole Polyhedron objects not benefit from this new class...

[kliem]

comment:8

Replying to @jplab:

Concerning the .faces() method. Currently, .iter_face only deals with proper faces. ... is that the intended behavior?

This is simply, because my method of intersecting faces and avoiding double counting has no guarantee to hit the empty face in the unbounded case. So one has to manually add it anyway. I would prefer leaving it like this in FaceIterator. But I can see that one wants to add those two extra faces (or only one for the empty polyhedron) when wrapping the class.

From an old list (so maybe some of them are renamed), I also saw the following methods make use of .face_lattice, and probably would benefit from the combinatorial polyhedra:

• adjacency_matrix
• facet_adjacency_matrix
• facial_adjacencies

what does it do, I can't find it

• is_simple

not anymore

• vertex_adjacency_matrix

It would be nice to make a thorough checking of which methods make use of "old style face lattice" things. It would be bad to not make the whole Polyhedron objects not benefit from this new class...

Yes, that's my plan. If I actually go through with it and make CombinatorialPolyhedron a parent of Polyhedron_base, as was proposed in #10777, then CombinatorialPolyhedron should do all calculations that depend only on the incidence matrix.

[jplab]

comment:9

Replying to @kliem:

Replying to @jplab:

Concerning the .faces() method. Currently, .iter_face only deals with proper faces. ... is that the intended behavior?

This is simply, because my method of intersecting faces and avoiding double counting has no guarantee to hit the empty face in the unbounded case. So one has to manually add it anyway. I would prefer leaving it like this in FaceIterator. But I can see that one wants to add those two extra faces (or only one for the empty polyhedron) when wrapping the class.

Sounds good.

From an old list (so maybe some of them are renamed), I also saw the following methods make use of .face_lattice, and probably would benefit from the combinatorial polyhedra:

• adjacency_matrix
• facet_adjacency_matrix
• facial_adjacencies

what does it do, I can't find it

Then, fine.

• is_simple

not anymore

Good

• vertex_adjacency_matrix

It would be nice to make a thorough checking of which methods make use of "old style face lattice" things. It would be bad to not make the whole Polyhedron objects not benefit from this new class...

Yes, that's my plan. If I actually go through with it and make CombinatorialPolyhedron a parent of Polyhedron_base, as was proposed in #10777, then CombinatorialPolyhedron should do all calculations that depend only on the incidence matrix.

Great! Then, one should also take care to not let the Polyhedron_base overwrite them, but duh... I'm sure you know what your doing... :)

[kliem]

comment:10

Replying to @jplab:

Great! Then, one should also take care to not let the Polyhedron_base overwrite them, but duh... I'm sure you know what your doing... :)

Well, you can always access overwritten methods using super.

Does it make sense to leave a method as e.g. simple in Polyhedron_base just to have a more specific docstring? Otherwise we would eventually end up with docstrings gathering all examples from Polyhedron, LatticePolytope and Cone.

[jplab]

comment:11

Replying to @kliem:

Replying to @jplab:

Great! Then, one should also take care to not let the Polyhedron_base overwrite them, but duh... I'm sure you know what your doing... :)

Well, you can always access overwritten methods using super.

Does it make sense to leave a method as e.g. simple in Polyhedron_base just to have a more specific docstring? Otherwise we would eventually end up with docstrings gathering all examples from Polyhedron, LatticePolytope and Cone.

I am not 100% sure about this. I believe that the method would stay in Polyhedron_base (think about the documentation online too) because one expects to see it there (and one does not directly think about the CombinatorialPolyhedron class directly, maybe) and the method would be only a couple of lines long and calling the combinatorial algorithm using super with the appropriate parameters.

On the long run, CombinatorialPolyhedron will contain the bulk of codes that strictly makes use of combinatorial data and Polyhedron_base things that use the geometry.

Further, concerning the present ticket, I believe it would make sense to make it a preparation ticket. Then each method would have 1 ticket. This way the changes will be more manageable.

Another open question: currently how is the relation between a Polyhedron object and a CombinatorialPolyhedron object? I guess that as of now, since the double description is computed by default, it is worth maybe creating the combinatorial counter part as an attribute and make it accessible via a method say named .combinatorial_polyhedron. This might make it easier to then transfer the computations to the combinatorial type.

When I create a combinatorial polyhedron from a polyhedron, it seems to keep the polyhedron object. Ideally, it would be nice to be able to go back and forth between them like it is for LP and Polyhedron (okay, it is not fully bakc and forth but still).

... and it would be nice if the methods of CombinatorialPolyhedron have exactly the same names for the same things H_representation vs Hrepr.

[kliem]

comment:12

Ok, this is a bunch of things. I realized that at some point it makes sense to create some sort of meta ticket for CombinatorialPolyhedron, also I realize that this ticket is more an agenda than anything else.

First of all, we should figure out, whether Polyhedron shall inherit from CombinatorialPolyhedron as a base class or whether its better to have it as a (lazy) method available.

Having it as a base class was proposed in #10777.

Maybe I should start a discussion on sage-devel to see what (interested) people think.

[kliem]

comment:13

I'm going to put this on needs review, so that people looking at #22420 will notice.

This way I can avoid adding each of the tickets to #22420.

If there is a better way of doing it, please tell me.

[kliem]

Changed dependencies from #26887, #27987 to #28621

[kliem]

Changed dependencies from #28621 to #28621, #28625, #28626

[jplab]

comment:22

Concerning the face lattice, when it is going to be done, it would be nice to verify if some functions are then obsolete. (For example _make_polyhedron_face which is only used in the face_lattice method.)

[kliem]

Changed commit from c4ccf86 to none

[kliem]

Changed branch from public/27063 to none

[kliem]

comment:33

Obtaining a graph that has vertices of the polyhedron as vertices is really slow. If you expose the option to obtain a graph with the vertices being the corresponding indices, that is much much faster.

[mkoeppe]

comment:38

Mission accomplished!

[mkoeppe]

Reviewer: Matthias Koeppe