Opened 3 years ago

Closed 2 years ago

# Compute graph of polyhedron with CombinatorialPolyhedron

Reported by: Owned by: gh-kliem major sage-9.1 geometry polyhedron, combinatorial_polyhedron jipilab, gh-LaisRast Jonathan Kliem Dima Pasechnik, Jean-Philippe Labbé N/A 01d1907 01d1907cd51b34a3e5b454897efbe0f5d2a61a75 #28621, #28603

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.

### comment:1 Changed 3 years ago by gh-kliem

• Dependencies changed from #28621 to #28621, #28603

### comment:2 Changed 3 years ago by gh-kliem

• Branch set to public/28626
• Commit set to fe0978473dab16ee78ebbc52ac87b6cfb3649ee1

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`

### comment:3 Changed 3 years ago by dimpase

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

### comment:4 Changed 3 years ago by 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_graph`s in `CombinatorialPolyhedron`.

### comment:5 Changed 3 years ago by dimpase

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

### comment:6 follow-up: ↓ 17 Changed 3 years ago by 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.

### comment:7 Changed 3 years ago by dimpase

• Reviewers set to Dima Pasechnik

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

### comment:8 Changed 3 years ago by 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`.

### comment:9 Changed 3 years ago by gh-kliem

• Description modified (diff)

### comment:10 Changed 3 years ago by git

• Commit changed from fe0978473dab16ee78ebbc52ac87b6cfb3649ee1 to 01d1907cd51b34a3e5b454897efbe0f5d2a61a75

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`

### comment:11 Changed 3 years ago by gh-kliem

• Status changed from new to needs_review

### comment:12 Changed 3 years ago by embray

• Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

### comment:13 Changed 3 years ago by gh-kliem

Is this ticket good to go?

### comment:14 follow-up: ↓ 15 Changed 3 years ago by dimpase

```========== 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
```

### comment:15 in reply to: ↑ 14 Changed 3 years ago by jipilab

```========== 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.

### comment:16 Changed 2 years ago by mkoeppe

• Milestone changed from sage-9.1 to sage-9.2

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.

### comment:17 in reply to: ↑ 6 Changed 2 years ago by jipilab

• Reviewers changed from Dima Pasechnik to Dima Pasechnik, Jean-Philippe Labbé
• Status changed from needs_review to needs_info

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

### comment:18 Changed 2 years ago by gh-kliem

• Description modified (diff)
• Status changed from needs_info to needs_review

### comment:19 Changed 2 years ago by jipilab

• Status changed from needs_review to positive_review

Thank you.

### comment:21 Changed 2 years ago by vbraun

• Branch changed from public/28626 to 01d1907cd51b34a3e5b454897efbe0f5d2a61a75
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:22 Changed 2 years ago by mkoeppe

• Milestone changed from sage-9.2 to sage-9.1
Note: See TracTickets for help on using tickets.