Compute graph of polyhedron with CombinatorialPolyhedron

[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.

Depends on #28621
Depends on #28603

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedron, combinatorial_polyhedron

Author: Jonathan Kliem

Branch/Commit: 01d1907

Reviewer: Dima Pasechnik, Jean-Philippe Labbé

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

[kliem]

Changed dependencies from #28621 to #28621, #28603

[kliem]

Branch: public/28626

[kliem]

Changed keywords from none to polyhedron, combinatorial_polyhedron

[kliem]

Commit: fe09784

[kliem]

comment:2

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]

comment:3

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

[kliem]

comment:4

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]

comment:5

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

[kliem]

comment:6

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]

Reviewer: Dima Pasechnik

[dimpase]

comment:7

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

[kliem]

comment:8

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.

[sagetrac-git]

Changed commit from fe09784 to 01d1907

[sagetrac-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]

comment:12

Ticket retargeted after milestone closed

[kliem]

comment:13

Is this ticket good to go?

[dimpase]

comment:14

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

[jplab]

comment:15

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]

comment:16

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.

[jplab]

comment:17

Replying to @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...

[jplab]

Changed reviewer from Dima Pasechnik to Dima Pasechnik, Jean-Philippe Labbé

[kliem]

comment:20

Thank you.

[vbraun]

Changed branch from public/28626 to 01d1907