Opened 18 months ago

Closed 12 months ago

Last modified 12 months ago

#28626 closed enhancement (fixed)

Compute graph of polyhedron with CombinatorialPolyhedron

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polyhedron, combinatorial_polyhedron
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Dima Pasechnik, Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 01d1907 (Commits, GitHub, GitLab) Commit: 01d1907cd51b34a3e5b454897efbe0f5d2a61a75
Dependencies: #28621, #28603 Stopgaps:

Status badges

Description (last modified by 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.

Change History (22)

comment:1 Changed 18 months ago by gh-kliem

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

comment:2 Changed 18 months ago by gh-kliem

  • Branch set to public/28626
  • Cc jipilab gh-LaisRast added
  • Commit set to fe0978473dab16ee78ebbc52ac87b6cfb3649ee1
  • Keywords polyhedron combinatorial_polyhedron added

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:

b89610eadded combinatorial polyhedron as an attribute for polyhedra
a005e47added vertex_graph, deprecated edge_graph
96346faimproved deprecation warning
4b83abedeprecation warning gives new name
ecb7986changed stacklevel to 3, so deprecation warning shows during normal usage
767eb74Merge branch 'public/28603' of git://trac.sagemath.org/sage into public/28626
fe09784calculate vertex_graph using combinatorialpolyhedron

comment:3 Changed 18 months ago by dimpase

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

comment:4 Changed 18 months 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_graphs in CombinatorialPolyhedron.

comment:5 Changed 18 months ago by dimpase

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

comment:6 follow-up: Changed 18 months 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 18 months ago by dimpase

  • Reviewers set to Dima Pasechnik

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

comment:8 Changed 18 months 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 18 months ago by gh-kliem

  • Description modified (diff)

comment:10 Changed 18 months ago by git

  • Commit changed from fe0978473dab16ee78ebbc52ac87b6cfb3649ee1 to 01d1907cd51b34a3e5b454897efbe0f5d2a61a75

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

5e7f291more documentation to vertex_graph
01d1907modified test vertex graph of polyhedron with lines in combinatorial_automorphism_group

comment:11 Changed 18 months ago by gh-kliem

  • Status changed from new to needs_review

comment:12 Changed 15 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:13 Changed 15 months ago by gh-kliem

Is this ticket good to go?

comment:14 follow-up: Changed 15 months ago by 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

comment:15 in reply to: ↑ 14 Changed 15 months ago by 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.

comment:16 Changed 12 months 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 12 months ago by jipilab

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

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

comment:18 Changed 12 months ago by gh-kliem

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

comment:19 Changed 12 months ago by jipilab

  • Status changed from needs_review to positive_review

comment:20 Changed 12 months ago by gh-kliem

Thank you.

comment:21 Changed 12 months ago by vbraun

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

comment:22 Changed 12 months ago by mkoeppe

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