Opened 10 months ago

Closed 9 months ago

Last modified 9 months ago

#29899 closed defect (fixed)

Two bugs with dilation

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords: polyhedra, dilation
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 0bb6413 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

The new dilation with #29200 discovered two bugs:

sage: 2*Polyhedron([[]], backend='cdd')
...
TypeError ...

and

sage: K.<sqrt2> = QuadraticField(2)
sage: sqrt2*Polyhedron(backend='normaliz')
...
AttributeError

The underlying errors are the following:

sage: from sage.geometry.polyhedron.backend_cdd import Polyhedron_QQ_cdd
sage: from sage.geometry.polyhedron.parent import Polyhedra_QQ_cdd
sage: parent = Polyhedra_QQ_cdd(QQ, 0, 'cdd')
sage: p = Polyhedron_QQ_cdd(parent, [iter([]), iter([]), iter([])], None)
Traceback (most recent call last):
...
TypeError: can't multiply sequence by non-int of type 'NoneType'

sage: Polyhedron(ieqs=[], ambient_dim=5, backend='cdd')
Traceback (most recent call last):
...
TypeError: unsupported operand type(s) for -=: 'NoneType' and 'int'

sage: from sage.geometry.polyhedron.parent import Polyhedra_RDF_cdd
sage: from sage.geometry.polyhedron.backend_cdd import Polyhedron_RDF_cdd
sage: parent = Polyhedra_RDF_cdd(RDF, 1, 'cdd')
sage: Vrep = [[], [], [[1.0]]]
sage: Hrep = [[], []]
sage: p = Polyhedron_RDF_cdd(parent, Vrep, Hrep,
....:                        Vrep_minimal=True, Hrep_minimal=True) 
Traceback (most recent call last):
...
TypeError: unsupported operand type(s) for -=: 'NoneType' and 'int'

There are two tiny fixes to it:

  • Make sure to special-case the empty polyhedron in Polyhedron_base.__init__.
  • Add a trivial inequality for initialization of the universe polyhedron with backend cdd.

We add doctests for each fix. Note that #29907 will also indirectly test this.

Change History (18)

comment:1 Changed 10 months ago by gh-kliem

  • Branch set to public/29899
  • Commit set to e055bc7957b210c056dc1c6b3e41d2df57495edf
  • Status changed from new to needs_review

New commits:

e41d698fix universe from Hrep for cdd
e055bc7correctly detect the empty polyhedron

comment:2 Changed 10 months ago by gh-kliem

What also doesn't work for cdd and this is how the TestSuite detected the problem is 2*Polyhedron(backend='cdd'). The problem is that it tries to discover the action via

parent(Polyhedron(backend='cdd')).an_element(), which is Polyhedron([[]], backend='cdd').

comment:3 Changed 10 months ago by gh-kliem

  • Description modified (diff)

There is no thing as a trivial equation of course.

comment:4 Changed 10 months ago by git

  • Commit changed from e055bc7957b210c056dc1c6b3e41d2df57495edf to 7eba64db686ba6145eda21e6e86b6bb991a53a94

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

7eba64dtrivial inequality

comment:5 Changed 10 months ago by git

  • Commit changed from 7eba64db686ba6145eda21e6e86b6bb991a53a94 to 067fb163bbf684960ff25caf9919a418301025ee

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

067fb16also fix it for initialization from Hrep and Vrep

comment:6 Changed 10 months ago by gh-kliem

Again, the branch that I push into public/29842 in a second really tests those things. Otherwise, I wouldn't have discovered this stuff in the first place.

comment:7 Changed 10 months ago by gh-kliem

  • Description modified (diff)

comment:8 Changed 10 months ago by mkoeppe

I think you should add a doctest that more specifically illustrates this subtle point of the behavior of Polyhedron_base.__init__ when generators are involved.

comment:9 Changed 10 months ago by git

  • Commit changed from 067fb163bbf684960ff25caf9919a418301025ee to e94f71c35570a2807c185a29add4f9b36fae4d48

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

e94f71cadd doctests

comment:10 Changed 10 months ago by gh-kliem

  • Description modified (diff)

comment:11 Changed 10 months ago by mkoeppe

inequalites -> inequalities.

Also could you rephrase/expand the comment involving "The damage is limited." I don't fully understand it

comment:12 Changed 10 months ago by gh-kliem

I will improve this.

The reason for using generators is that we don't have to build a list/tuple that is possibly discarded. Once we are there, we need to generate all the generators. Of course it might be better if you can really just generate them, when you feed them to the backend, but the backends require that you don't call _init_from_Vrepresentation, when vertices and rays and lines are empty. So we should respect that.

comment:13 Changed 9 months ago by mkoeppe

  • Status changed from needs_review to needs_work

comment:14 Changed 9 months ago by gh-kliem

  • Branch changed from public/29899 to public/29899-reb
  • Commit changed from e94f71c35570a2807c185a29add4f9b36fae4d48 to 0bb641359527cb77f74d373c95a0c90c65f6f117
  • Status changed from needs_work to needs_review

New commits:

53a64b0Merge branch 'public/29899' of git://trac.sagemath.org/sage into public/29899-reb
0bb6413documentation

comment:15 Changed 9 months ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

comment:16 Changed 9 months ago by gh-kliem

Thank you.

comment:17 Changed 9 months ago by vbraun

  • Branch changed from public/29899-reb to 0bb641359527cb77f74d373c95a0c90c65f6f117
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:18 Changed 9 months ago by slelievre

  • Commit 0bb641359527cb77f74d373c95a0c90c65f6f117 deleted
  • Description modified (diff)
Note: See TracTickets for help on using tickets.