Make indices of V_representation of faces of polyhedron accessible through a new method

[jplab]

Currently, we can get faces of polyhedron objects like this:

sage: P = polytopes.cube()
sage: TwoFace = P.faces(2)[0]
sage: TwoFace
<0,1,2,3>

It is sometimes useful to get a straight access to the printed indices given by the _repr_. Wishing something like:

sage: TwoFace.ambient_V_indices()
(0, 1, 2, 3)

And it would be nice to improve the _repr_ of faces to have a more complete description:

sage: TwoFace
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices

... but for that one, better suggestions are welcome. The annoying thing with <0,1,2,3> is that it can be a square, and it can be a simplex, there is no way to know the dimension (which the face knows anyway) from the representation string.

To get the above, it was necessary to also implement n_vertices, n_rays, and n_lines for faces.

CC: @mo271 @videlec

Component: geometry

Keywords: polytopes, faces

Author: Jean-Philippe Labbé

Branch/Commit: 553a2b1

Reviewer: Jonathan Kliem

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

[novoselt]

comment:1

As a point of comparison to consider:

sage: P = polytopes.cube()
sage: LP = LatticePolytope(P.vertices_list())
sage: TwoFace = LP.faces(2)[0]
sage: TwoFace
2-d face of 3-d reflexive polytope in 3-d lattice M
sage: TwoFace.ambient_vertex_indices()
(1, 3, 5, 7)

This output is unified for lattice polytopes, cones, fans, and their components:

sage: F = NormalFan(LP)
sage: F
Rational polyhedral fan in 3-d lattice N
sage: F.cones(2)[0]
2-d cone of Rational polyhedral fan in 3-d lattice N

Also

sage: type(TwoFace)
<class 'sage.geometry.lattice_polytope.LatticePolytopeClass'>

so faces are polytopes as well and all the methods of "standalone polytopes" are available for them as well.

[jplab]

comment:2

Replying to @novoselt:

As a point of comparison to consider:

sage: P = polytopes.cube()
sage: LP = LatticePolytope(P.vertices_list())
sage: TwoFace = LP.faces(2)[0]
sage: TwoFace
2-d face of 3-d reflexive polytope in 3-d lattice M
sage: TwoFace.ambient_vertex_indices()
(1, 3, 5, 7)

This output is unified for lattice polytopes, cones, fans, and their components:

sage: F = NormalFan(LP)
sage: F
Rational polyhedral fan in 3-d lattice N
sage: F.cones(2)[0]
2-d cone of Rational polyhedral fan in 3-d lattice N

Also

sage: type(TwoFace)
<class 'sage.geometry.lattice_polytope.LatticePolytopeClass'>

so faces are polytopes as well and all the methods of "standalone polytopes" are available for them as well.

Oh! Great, yes this is pretty much what I had in mind. I should probably use the same name of methods, to make this uniform too.

Further, to get the face as a polyhedron, the method as_polyhedron gives back the appropriate object:

sage: TwoFace.as_polyhedron()
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: type(TwoFace.as_polyhedron())
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category.element_class'>

[jplab]

Commit: 4a5c06e

[jplab]

New commits:

4a5c06e

first version

[jplab]

Author: Jean-Philippe Labbé

[jplab]

Branch: u/jipilab/27071

[novoselt]

comment:4

Replying to @jplab:

Further, to get the face as a polyhedron, the method as_polyhedron gives back the appropriate object:

sage: TwoFace.as_polyhedron()
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: type(TwoFace.as_polyhedron())
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category.element_class'>

I found it more convenient to have faces being "honest polytopes" - do you have any reasons for NOT doing it? (This is not the goal of this ticket, of course.)

A couple of questions: do we have any general guidelines for n_vertices vs. nvertices? I used the latter, but don't really have any preference. Except that it annoys me to have both versions for different objects since it is hard to remember when to use what.

More to the point - the ticket was about getting access to "ambient indices" via a method and perhaps making _repr_ more complete. But now it seems that you have completely replaced the information that was in _repr_ before. Do you want to keep those indices in _repr_ at all? Do other people want it? Are they OK with a long-ish description now? In particular the old output of

             sage: Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0]]).face_lattice().level_sets()
-            [[<>], [<0>, <1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]]
+            [[A -1-dimensional face of a Polyhedron in ZZ^3],
+             [A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
+              A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
+              A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex],
+             [A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
+              A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
+              A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices],
+             [A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices]]

could be more desirable than the new one where different faces have the same repr.

To be clear - I am not saying that your changes are bad, they are after all very much in line with my choices for lattice polytopes, just want to make sure that all things and opinions are considered. Perhaps it is useful to combine verbose description with indices. And to keep it shorter I would vote for "2-d" instead of "2-dimensional". (Faces of lattice polytopes mention 3 different dimensions so space saving was particularly visible there.)

[jplab]

comment:5

Replying to @novoselt:

Replying to @jplab:

Further, to get the face as a polyhedron, the method as_polyhedron gives back the appropriate object:

sage: TwoFace.as_polyhedron()
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: type(TwoFace.as_polyhedron())
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category.element_class'>

I found it more convenient to have faces being "honest polytopes" - do you have any reasons for NOT doing it? (This is not the goal of this ticket, of course.)

Well, the structure was already in place. Conceptually, I like to have an actual object for faces of a polytope. For example, they are the elements of the face lattice. Having them know "where they are from" is quite practical, one can ask for neighbors, etc. So all these methods are then in the class of PolyhedronFaces... Having to do .as_polyhedron is perhaps a good compromise there. For example, this question also goes for linear programs in sage where we have the method .polyhedron() and .to_linear_program(), whereas they could be considered the same... It just depends what one wants to do with them, and I would say that it makes sense to have the data structure PolyhedronFace to do al sorts of combinatorial analysis.

A couple of questions: do we have any general guidelines for n_vertices vs. nvertices? I used the latter, but don't really have any preference. Except that it annoys me to have both versions for different objects since it is hard to remember when to use what.

Good question. I followed the one for Polyhedron objects for which there are n_equations, n_facets, etc. I just checked for graphs and it uses num_verts, num_edges, etc.

In this case, I would stick to the local convention on Polyhedron.

More to the point - the ticket was about getting access to "ambient indices" via a method and perhaps making _repr_ more complete. But now it seems that you have completely replaced the information that was in _repr_ before. Do you want to keep those indices in _repr_ at all? Do other people want it? Are they OK with a long-ish description now? In particular the old output of

             sage: Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0]]).face_lattice().level_sets()
-            [[<>], [<0>, <1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]]
+            [[A -1-dimensional face of a Polyhedron in ZZ^3],
+             [A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
+              A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
+              A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex],
+             [A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
+              A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
+              A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices],
+             [A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices]]

could be more desirable than the new one where different faces have the same repr.

Yes, you are right. While I was changing the doctests, I was thinking that the information becomes somewhat lost (indices of the vertices) on the one hand, but also somehow still good on the other (dimension, ambient dim, and number of vertices).

What is better? Hm.

For example, when dealing with larger polytopes, does printing a list with 50 vertex indices instructive? Or rather "A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 50 vertices".

There is no way to know anything from just a list of indices... At least, that's how I react everytime I see such a list. But yes, sometimes, I am quite happy to see the list of indices, but then I can not fetch them in any practical way (hence this ticket!). So in the end, having them stuck in the _repr_ was not the better way to go. The user can get exactly this output now through ambient_V_indices.

I agree, this is a big change and this should be discussed. I should perhaps ask on sage-devel.

One compromise is:

Change the doctests back so that they show the actual list of indices (via the new implemented method) and not just the _repr_. So at least the doctests are detecting potential reordering in the V-representation.

To be clear - I am not saying that your changes are bad, they are after all very much in line with my choices for lattice polytopes, just want to make sure that all things and opinions are considered. Perhaps it is useful to combine verbose description with indices. And to keep it shorter I would vote for "2-d" instead of "2-dimensional". (Faces of lattice polytopes mention 3 different dimensions so space saving was particularly visible there.)

Sure, I appreciate your feedback!

Yes, I wanted to model it from your suggestion, while also keeping it uniform with the _repr_ of Polyhedron object which give, for example:

sage: P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices

[novoselt]

comment:6

Replying to @jplab:

For example, when dealing with larger polytopes, does printing a list with 50 vertex indices instructive? Or rather "A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 50 vertices".

Do faces have their own internal indices, i.e. are there edges randomly-but-consistently numbered 3 and 4? If yes, it could be useful to include this number in the output so one can see the difference between two edges in the output.

[jplab]

comment:7

Replying to @novoselt:

Replying to @jplab:

For example, when dealing with larger polytopes, does printing a list with 50 vertex indices instructive? Or rather "A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 50 vertices".

Do faces have their own internal indices, i.e. are there edges randomly-but-consistently numbered 3 and 4? If yes, it could be useful to include this number in the output so one can see the difference between two edges in the output.

The indices are fixed, they are the indices in the V-representation.

I will change the doctests back to show the indices.

Concerning the naming convention, I would stick to n_ as it is already the convention within Polyhedron objects. See the sage-devel discussion:

https://groups.google.com/forum/#!topic/sage-devel/wgo18WKZTpQ

[sagetrac-git]

Changed commit from 4a5c06e to c3e78c8

[sagetrac-git]

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

ea744a4	Merge branch 'u/jipilab/27071' of trac.sagemath.org:sage into 27071
c3e78c8	Improved doctests

[jplab]

comment:9

Ok, I would say that it is ready for review now.

[jplab]

comment:10

Failing test in quick tutorial.

[sagetrac-git]

Changed commit from c3e78c8 to 553a2b1

[sagetrac-git]

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

553a2b1

Fixed doctest in thematic tutorial

[jplab]

comment:12

... ready to get reviewed. Hopefully all tests pass now.

[novoselt]

comment:13

Replying to @jplab:

Replying to @novoselt:

Replying to @jplab:

For example, when dealing with larger polytopes, does printing a list with 50 vertex indices instructive? Or rather "A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 50 vertices".

Do faces have their own internal indices, i.e. are there edges randomly-but-consistently numbered 3 and 4? If yes, it could be useful to include this number in the output so one can see the difference between two edges in the output.

The indices are fixed, they are the indices in the V-representation.

I will change the doctests back to show the indices.

That's not what I meant, sorry for not being clear. My question was: is there edge !#3? Or a 5-dimensional face !#42? If that is the case, it may be useful to have this number in the repr. It does not have to be canonical in any sense, but when you have say a list of edges belonging to some higher-dimensional face, it may be nice to see that they are !#3, !#5, !#8, and !#23, rather than just that there are four edges, all looking exactly the same. And in any case that's just a suggestion, I don't insist ;-)

[jplab]

comment:14

Replying to @novoselt:

Replying to @jplab:

Replying to @novoselt:

Replying to @jplab:

For example, when dealing with larger polytopes, does printing a list with 50 vertex indices instructive? Or rather "A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 50 vertices".

Do faces have their own internal indices, i.e. are there edges randomly-but-consistently numbered 3 and 4? If yes, it could be useful to include this number in the output so one can see the difference between two edges in the output.

The indices are fixed, they are the indices in the V-representation.

I will change the doctests back to show the indices.

That's not what I meant, sorry for not being clear. My question was: is there edge !#3? Or a 5-dimensional face !#42? If that is the case, it may be useful to have this number in the repr. It does not have to be canonical in any sense, but when you have say a list of edges belonging to some higher-dimensional face, it may be nice to see that they are !#3, !#5, !#8, and !#23, rather than just that there are four edges, all looking exactly the same. And in any case that's just a suggestion, I don't insist ;-)

Oh, I see now! Okay! Hmm, the ordering is decided at the level of posets, through the face lattice. I do not know how much the ordering would be canonical. Especially now with the transition to python3, I would not try to introduce in there...

Only vertices receive a consistent numbering through the V-representation. The other faces do not...

[embray]

comment:15

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[kliem]

Reviewer: Jonathan Kliem

[kliem]

comment:16

Looks fine to me.

[vbraun]

Changed branch from u/jipilab/27071 to 553a2b1