Opened 3 years ago
Last modified 7 weeks ago
#27063 needs_work task
Transition of combinatorial computations of Polyhedron to Combinatorial Type
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sagepending 
Component:  geometry  Keywords:  polyhedron, face lattice 
Cc:  jipilab  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  Commit:  
Dependencies:  #28621, #28625, #28626  Stopgaps: 
Description (last modified by )
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:
 #28621: Add method
combinatorial_polyhedron
,  #28646:
face_generator
,  #28982:
hasse_diagram
,  #29186:
simpliciality
,simplicity
Replace the existing computation:
 #28625:
f_vector
,  #28646
faces
,  #28626:
graph
/vertex_graph
, graph
/vertex_graph
with incidences instead of Vrepresentation/expose the names=False option #32666:
vertex_adjacency_matrix
vertex_digraph
 #33008:
facet_adjacency_matrix
,  #28982
face_lattice
.
Migrate code to CombinatorialPolyhedron
:
Change History (35)
comment:1 Changed 3 years ago by
 Milestone changed from sage8.6 to sage8.7
comment:2 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.8
comment:3 Changed 3 years ago by
 Branch set to public/27063
 Commit set to 25407f852d524693571b97e1d26e4fdd264b51fe
 Dependencies changed from #26887 to #26887, #27987
 Description modified (diff)
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

comment:4 Changed 3 years ago by
 Commit changed from 25407f852d524693571b97e1d26e4fdd264b51fe to c4ccf860ba2906123bd20b4e3a49ad3e94ca7bdb
Branch pushed to git repo; I updated commit sha1. New commits:
c4ccf86  face lattice by CombinatorialPolyhedron

comment:5 Changed 3 years ago by
 Milestone sage8.8 deleted
As the Sage8.8 release milestone is pending, we should delete the sage8.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 (sage8.9).
comment:6 Changed 3 years ago by
 Milestone set to sage8.9
comment:7 followup: ↓ 8 Changed 2 years ago by
 Milestone changed from sage8.9 to sagepending
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...
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 2 years ago by
Replying to jipilab:
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.
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 2 years ago by
Replying to ghkliem:
Replying to jipilab:
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 ofPolyhedron_base
, as was proposed in #10777, thenCombinatorialPolyhedron
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... :)
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 2 years ago by
Replying to jipilab:
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
.
comment:11 in reply to: ↑ 10 Changed 2 years ago by
Replying to ghkliem:
Replying to jipilab:
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
inPolyhedron_base
just to have a more specific docstring? Otherwise we would eventually end up with docstrings gathering all examples fromPolyhedron
,LatticePolytope
andCone
.
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 metaticket tracking each method and have 1 ticket per method.
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
.
comment:12 Changed 2 years ago by
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 sagedevel to see what (interested) people think.
comment:13 followup: ↓ 16 Changed 2 years ago by
 Dependencies changed from #26887, #27987 to #28621
 Description modified (diff)
 Status changed from new to needs_review
comment:14 Changed 2 years ago by
 Description modified (diff)
comment:15 Changed 2 years ago by
 Status changed from needs_review to needs_work
 Type changed from enhancement to task
comment:16 in reply to: ↑ 13 Changed 2 years ago by
 Summary changed from Polyhedron: let CombinatorialPolyhedron do all combinatorial calculations to Transition of combinatorial computations of Polyhedron to Combinatorial Type
Replying to ghkliem:
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.
Putting it at needs review is not the appropriate status. In #22420, change the title of the #27063 ticket to "TASK: XXX", where XXX is the current title. Then, what is written will be sufficient to understand what is going on in this ticket. No need to add every single ticket from here, to #22420.
comment:17 Changed 2 years ago by
 Description modified (diff)
Finally, it might make sense to move code to
CombinatorialPolyhedron
. E.g.is_prism
can be checked there and should only be checked there to avoid code duplication.
Yes, I agree, I adapted the description of the ticket.
comment:18 Changed 2 years ago by
 Dependencies changed from #28621 to #28621, #28625, #28626
 Description modified (diff)
comment:19 Changed 2 years ago by
 Description modified (diff)
comment:20 Changed 2 years ago by
 Description modified (diff)
comment:21 Changed 2 years ago by
 Cc jipilab added
comment:22 Changed 2 years ago by
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.)
comment:23 Changed 2 years ago by
 Description modified (diff)
comment:24 Changed 2 years ago by
 Branch public/27063 deleted
 Commit c4ccf860ba2906123bd20b4e3a49ad3e94ca7bdb deleted
comment:25 Changed 2 years ago by
 Description modified (diff)
comment:26 Changed 2 years ago by
 Description modified (diff)
comment:27 Changed 2 years ago by
 Description modified (diff)
comment:28 Changed 2 years ago by
 Description modified (diff)
comment:29 Changed 2 years ago by
 Description modified (diff)
comment:30 Changed 2 years ago by
 Description modified (diff)
comment:31 Changed 2 years ago by
 Description modified (diff)
comment:32 Changed 21 months ago by
 Description modified (diff)
comment:33 Changed 20 months ago by
 Description modified (diff)
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.
comment:34 Changed 7 weeks ago by
 Description modified (diff)
comment:35 Changed 7 weeks ago by
 Description modified (diff)
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 sagepending or sagewishlist.