Compute graph of polyhedron with CombinatorialPolyhedron

[gh-kliem]

We use CombinatorialPolyhedron to compute the graph of Polyhedron_base.

In the case of polyhedra with lines aka unpointed polyhedra this changes the behavior:

• Old behavior: The vertex graph basically ignored the lines, so that

  sage: P = Polyhedron(vertices=my_vertices, rays=my_rays, lines=my_lines)
  sage: Q = Polyhedron(vertices=my_vertices, rays=my_rays)
  

  have the same graph (assuming the Vrepresentation as ['my_vertices', 'my_rays', 'my_lines'] is minimal).
• New behavior: The vertex graph of a polyhedron with lines contains no vertices as the polyhedron as no vertices.

We add information about this to the documentation of vertex_graph.

We alter a doctest in combinatorial_automorphism_group that assumed the old behavior.

See ​https://groups.google.com/d/msg/sage-devel/lTwb_P0nBEw/_R4vXOxgDAAJ for the discussion of this change.

[gh-kliem]

What do we do with polyhedra that contain lines?

As of now it is understood that in this case the vertex_graph is non-empty. So the vertex graph is basically the one of the projection.

However, the docstring of vertex_graph states that the edges correspond to edges of the polyhedron. I find it very confusing that the vertex_graph of an unpointed polyhedron should have edges.

If people think this is the way it should be than the docstring of vertex_graph should be more precise.

I stumbled upon this because I got a test failure at File "src/sage/geometry/polyhedron/base.py", line 7229

7225         Permutations can only exchange vertices with vertices, rays
7226         with rays, and lines with lines::
7227 
7228             sage: P = Polyhedron(vertices=[(1,0,0), (1,1,0)], rays=[(1,0,0)], lines=[(0,0,1)])
7229             sage: P.combinatorial_automorphism_group(vertex_graph_only=True)
7230             Permutation Group with generators [(A vertex at (1,0,0),A vertex at (1,1,0))]

This is a weird test, as it tests a behavior which seems to be opposed to the intention of vertex_graph. Also the announcement is strange, as the vertex_graph contains neither rays nor lines and thus will not interchange them (not even a ray with a ray).

---

New commits:

​b89610e	added combinatorial polyhedron as an attribute for polyhedra
​a005e47	added vertex_graph, deprecated edge_graph
​96346fa	improved deprecation warning
​4b83abe	deprecation warning gives new name
​ecb7986	changed stacklevel to 3, so deprecation warning shows during normal usage
​767eb74	Merge branch 'public/28603' of git://trac.sagemath.org/sage into public/28626
​fe09784	calculate vertex_graph using combinatorialpolyhedron

[dimpase]

it is not clear from the ticket description why edge_graph is deprecated, can you explain?

[gh-kliem]

Sorry about the confusion. This ticket is built on top of #28603 and #28621. Only the last commit is due to this ticket.

In CombinatorialPolyhedron, I chose to implement a method edge_graph. In order to make it more compatible with Polyhedron I replace it by vertex_graph in #28603.

This way CombinatorialPolyhedron(P).vertex_graph() gives the vertex graph of our polyhedron P.

There are two issues with edge graph:

• It has no vertices if there are no edges (a 0-dimensional polyhedron).
• It depends not just on the combinatorial type, for example those two

  sage: Q = Polyhedron(vertices=[[1,0],[0,1]],rays=[[1,11/10],[11/10,1]]); Q
  A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 2 rays
  sage: P = Polyhedron(vertices=[[1,0],[0,1]],rays=[[1,1]]); P
  A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
  

  polyhedra do not have isomorphic edge_graphs in CombinatorialPolyhedron.

[dimpase]

So this does bring the sanity in, where vertices correspond to vertices in the geometric sense, right?

[gh-kliem]

Yes.

However, as I'm changing the behavior, I didn't want to do it secretely and see if there are objections. Hence the post on sage_devel.

[dimpase]

Are you still working on the ticket, or it needs review?

[gh-kliem]

I mostly waited, if there where objections to changing the behavior.

If there are none, I need to change the failing test and probably comment on the vertices being different from the method vertices.

[git]

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

​5e7f291	more documentation to vertex_graph
​01d1907	modified test vertex graph of polyhedron with lines in combinatorial_automorphism_group

[embray]

Ticket retargeted after milestone closed

[gh-kliem]

Is this ticket good to go?

[dimpase]

How about the bot report:

========== pyflakes ==========
git checkout patchbot/ticket_merged
src/sage/geometry/polyhedron/base.py:5189: local variable 'ambient_dim' is assigned to but never used
src/sage/geometry/polyhedron/base.py:5190: local variable 'polytope_dim' is assigned to but never used

[jipilab]

Replying to dimpase:

How about the bot report:

========== pyflakes ==========
git checkout patchbot/ticket_merged
src/sage/geometry/polyhedron/base.py:5189: local variable 'ambient_dim' is assigned to but never used
src/sage/geometry/polyhedron/base.py:5190: local variable 'polytope_dim' is assigned to but never used

Fixed in #28880.

[mkoeppe]

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[jipilab]

Replying to gh-kliem:

Yes.

However, as I'm changing the behavior, I didn't want to do it secretely and see if there are objections. Hence the post on sage_devel.

Could you link to the post?

I would say that the ticket looks ready, but for the sake of completeness, I would like to check the change of behavior...

[gh-kliem]

Thank you.