Coverage for local/lib/python2.7/site-packages/sage/geometry/polyhedron/parent.py : 95%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" Parents for Polyhedra """
#***************************************************************************** # Copyright (C) 2014 Volker Braun <vbraun.name@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #******************************************************************************
""" Construct a suitable parent class for polyhedra
INPUT:
- ``base_ring`` -- A ring. Currently there are backends for `\ZZ`, `\QQ`, and `\RDF`.
- ``ambient_dim`` -- integer. The ambient space dimension.
- ``backend`` -- string. The name of the backend for computations. There are several backends implemented:
* ``backend="ppl"`` uses the Parma Polyhedra Library
* ``backend="cdd"`` uses CDD
* ``backend="normaliz"`` uses normaliz
* ``backend="polymake"`` uses polymake
* ``backend="field"`` a generic Sage implementation
OUTPUT:
A parent class for polyhedra over the given base ring if the backend supports it. If not, the parent base ring can be larger (for example, `\QQ` instead of `\ZZ`). If there is no implementation at all, a ``ValueError`` is raised.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(AA, 3) Polyhedra in AA^3 sage: Polyhedra(ZZ, 3) Polyhedra in ZZ^3 sage: type(_) <class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category'> sage: Polyhedra(QQ, 3, backend='cdd') Polyhedra in QQ^3 sage: type(_) <class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_cdd_with_category'>
CDD does not support integer polytopes directly::
sage: Polyhedra(ZZ, 3, backend='cdd') Polyhedra in QQ^3
TESTS::
sage: Polyhedra(RR, 3, backend='field') Traceback (most recent call last): ... ValueError: the 'field' backend for polyhedron can not be used with non-exact fields sage: Polyhedra(RR, 3) Traceback (most recent call last): ... ValueError: no appropriate backend for computations with Real Field with 53 bits of precision """ # TODO: find a more robust way of checking that the coefficients are indeed # real numbers raise ValueError("invalid base ring") else:
return Polyhedra_ZZ_normaliz(base_ring, ambient_dim, backend) return Polyhedra_polymake(base_ring.fraction_field(), ambient_dim, backend) else: raise ValueError('No such backend (=' + str(backend) + ') implemented for given basering (=' + str(base_ring)+').')
r""" Polyhedra in a fixed ambient space.
INPUT:
- ``base_ring`` -- either ``ZZ``, ``QQ``, or ``RDF``. The base ring of the ambient module/vector space.
- ``ambient_dim`` -- integer. The ambient space dimension.
- ``backend`` -- string. The name of the backend for computations. There are several backends implemented:
* ``backend="ppl"`` uses the Parma Polyhedra Library
* ``backend="cdd"`` uses CDD
* ``backend="normaliz"`` uses normaliz
* ``backend="polymake"`` uses polymake
* ``backend="field"`` a generic Sage implementation
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(ZZ, 3) Polyhedra in ZZ^3 """ """ The Python constructor.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 3) Polyhedra in QQ^3
TESTS::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: P = Polyhedra(QQ, 3) sage: TestSuite(P).run(skip='_test_pickling') """
""" Recycle the H/V-representation objects of a polyhedron.
This speeds up creation of new polyhedra by reusing objects. After recycling a polyhedron object, it is not in a consistent state any more and neither the polyhedron nor its H/V-representation objects may be used any more.
INPUT:
- ``polyhedron`` -- a polyhedron whose parent is ``self``.
EXAMPLES::
sage: p = Polyhedron([(0,0),(1,0),(0,1)]) sage: p.parent().recycle(p)
TESTS::
sage: p = Polyhedron([(0,0),(1,0),(0,1)]) sage: n = len(p.parent()._Vertex_pool) sage: p._delete() sage: len(p.parent()._Vertex_pool) - n 3 """ raise TypeError('The polyhedron has the wrong parent class.')
r""" Return the dimension of the ambient space.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 3).ambient_dim() 3 """
r""" Return the backend.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 3).backend() 'ppl' """
def an_element(self): r""" Returns a Polyhedron.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 4).an_element() A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 5 vertices """
def some_elements(self): r""" Returns a list of some elements of the semigroup.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 4).some_elements() [A 3-dimensional polyhedron in QQ^4 defined as the convex hull of 4 vertices, A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex and 4 rays, A 2-dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices and 1 ray, The empty polyhedron in QQ^4] sage: Polyhedra(ZZ,0).some_elements() [The empty polyhedron in ZZ^0, A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex] """ self.element_class(self, None, None), self.element_class(self, None, [[], []])] self.element_class(self, [points[0:self.ambient_dim()+1], [], []], None), self.element_class(self, [points[0:1], points[1:self.ambient_dim()+1], []], None), self.element_class(self, [points[0:3], points[4:5], []], None), self.element_class(self, None, None)]
def zero(self): r""" Return the polyhedron consisting of the origin, which is the neutral element for Minkowski addition.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: p = Polyhedra(QQ, 4).zero(); p A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex sage: p+p == p True """
""" Return the empty polyhedron.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: P = Polyhedra(QQ, 4) sage: P.empty() The empty polyhedron in QQ^4 sage: P.empty().is_empty() True """
""" Return the entire ambient space as polyhedron.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: P = Polyhedra(QQ, 4) sage: P.universe() A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex and 4 lines sage: P.universe().is_universe() True """
def Vrepresentation_space(self): r""" Return the ambient vector space.
This is the vector space or module containing the Vrepresentation vectors.
OUTPUT:
A free module over the base ring of dimension :meth:`ambient_dim`.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 4).Vrepresentation_space() Vector space of dimension 4 over Rational Field sage: Polyhedra(QQ, 4).ambient_space() Vector space of dimension 4 over Rational Field """ else:
def Hrepresentation_space(self): r""" Return the linear space containing the H-representation vectors.
OUTPUT:
A free module over the base ring of dimension :meth:`ambient_dim` + 1.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(ZZ, 2).Hrepresentation_space() Ambient free module of rank 3 over the principal ideal domain Integer Ring """ else:
""" Return an abbreviated string representation of the ambient space.
OUTPUT:
String.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 3)._repr_ambient_module() 'QQ^3' sage: K.<sqrt3> = NumberField(x^2 - 3, embedding=AA(3).sqrt()) sage: Polyhedra(K, 4)._repr_ambient_module() '(Number Field in sqrt3 with defining polynomial x^2 - 3)^4' """ else:
""" Return a string representation.
OUTPUT:
String.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ, 3) Polyhedra in QQ^3 sage: Polyhedra(QQ, 3)._repr_() 'Polyhedra in QQ^3' """
""" The element (polyhedron) constructor.
INPUT:
- ``Vrep`` -- a list `[vertices, rays, lines]`` or ``None``.
- ``Hrep`` -- a list `[ieqs, eqns]`` or ``None``.
- ``convert`` -- boolean keyword argument (default: ``True``). Whether to convert the coordinates into the base ring.
- ``**kwds`` -- optional remaining keywords that are passed to the polyhedron constructor.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: P = Polyhedra(QQ, 3) sage: P._element_constructor_([[(0, 0, 0), (1, 0, 0), (0, 1, 0), (0,0,1)], [], []], None) A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices sage: P([[(0,0,0),(1,0,0),(0,1,0),(0,0,1)], [], []], None) A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices sage: P(0) A 0-dimensional polyhedron in QQ^3 defined as the convex hull of 1 vertex
Check that :trac:`21270` is fixed::
sage: poly = polytopes.regular_polygon(7) sage: lp, x = poly.to_linear_program(solver='InteractiveLP', return_variable=True) sage: lp.set_objective(x[0] + x[1]) sage: b = lp.get_backend() sage: P = b.interactive_lp_problem() sage: p = P.plot()
sage: Q = Polyhedron(ieqs=[[-499999, 1000000], [1499999, -1000000]]) sage: P = Polyhedron(ieqs=[[0, 1.0], [1.0, -1.0]], base_ring=RDF) sage: Q.intersection(P) A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices sage: P.intersection(Q) A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices """
# renormalize before converting when going from QQ to RDF, see trac 21270 newlstlst.append(lst) else: else: newlstlst.append(lst) Hrep = [convert_base_ring_Hrep(_) for _ in Hrep] else: raise ValueError('Cannot convert to polyhedron object.')
""" Return the base extended parent.
INPUT:
- ``base_ring``, ``backend`` -- see :func:`~sage.geometry.polyhedron.constructor.Polyhedron`.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(ZZ,3).base_extend(QQ) Polyhedra in QQ^3 sage: Polyhedra(ZZ,3).an_element().base_extend(QQ) A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices """
""" Return the common base rincg for both ``self`` and ``other``.
This method is not part of the coercion framework, but only a convenience function for :class:`Polyhedra_base`.
INPUT:
- ``other`` -- must be either:
* another ``Polyhedron`` object
* `\ZZ`, `\QQ`, `RDF`, or a ring that can be coerced into them.
* a constant that can be coerced to `\ZZ`, `\QQ`, or `RDF`.
OUTPUT:
Either `\ZZ`, `\QQ`, or `RDF`. Raises ``TypeError`` if ``other`` is not a suitable input.
.. NOTE::
"Real" numbers in sage are not necessarily elements of `RDF`. For example, the literal `1.0` is not.
EXAMPLES::
sage: triangle_QQ = Polyhedron(vertices = [[1,0],[0,1],[1,1]], base_ring=QQ).parent() sage: triangle_RDF = Polyhedron(vertices = [[1,0],[0,1],[1,1]], base_ring=RDF).parent() sage: triangle_QQ._coerce_base_ring(QQ) Rational Field sage: triangle_QQ._coerce_base_ring(triangle_RDF) Real Double Field sage: triangle_RDF._coerce_base_ring(triangle_QQ) Real Double Field sage: triangle_QQ._coerce_base_ring(RDF) Real Double Field sage: triangle_QQ._coerce_base_ring(ZZ) Rational Field sage: triangle_QQ._coerce_base_ring(1/2) Rational Field sage: triangle_QQ._coerce_base_ring(0.5) Real Double Field """ # other is a constant? raise TypeError('Could not coerce '+str(other)+' into ZZ, QQ, or RDF.')
raise TypeError('Could not coerce type '+str(other)+' into ZZ, QQ, or RDF.')
r""" Return whether there is a coercion from ``X``
INPUT:
- ``X`` -- anything.
OUTPUT:
Boolean.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: Polyhedra(QQ,3).has_coerce_map_from( Polyhedra(ZZ,3) ) # indirect doctest True sage: Polyhedra(ZZ,3).has_coerce_map_from( Polyhedra(QQ,3) ) False """ return False
""" Register actions with the coercion model.
The monoid actions are Minkowski sum and Cartesian product. In addition, we want multiplication by a scalar to be dilation and addition by a vector to be translation. This is implemented as an action in the coercion model.
INPUT:
- ``other`` -- a scalar or a vector.
- ``op`` -- the operator.
- ``self_is_left`` -- boolean. Whether ``self`` is on the left of the operator.
OUTPUT:
An action that is used by the coercion model.
EXAMPLES::
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: PZZ2 = Polyhedra(ZZ, 2) sage: PZZ2.get_action(ZZ) # indirect doctest Right action by Integer Ring on Polyhedra in ZZ^2 sage: PZZ2.get_action(QQ) Right action by Rational Field on Polyhedra in QQ^2 with precomposition on left by Coercion map: From: Polyhedra in ZZ^2 To: Polyhedra in QQ^2 with precomposition on right by Identity endomorphism of Rational Field sage: PQQ2 = Polyhedra(QQ, 2) sage: PQQ2.get_action(ZZ) Right action by Integer Ring on Polyhedra in QQ^2 sage: PQQ2.get_action(QQ) Right action by Rational Field on Polyhedra in QQ^2
sage: Polyhedra(ZZ,2).an_element() * 2 A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: Polyhedra(ZZ,2).an_element() * (2/3) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices sage: Polyhedra(QQ,2).an_element() * 2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices sage: Polyhedra(QQ,2).an_element() * (2/3) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices
sage: 2 * Polyhedra(ZZ,2).an_element() A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: (2/3) * Polyhedra(ZZ,2).an_element() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices sage: 2 * Polyhedra(QQ,2).an_element() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices sage: (2/3) * Polyhedra(QQ,2).an_element() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices
sage: from sage.geometry.polyhedron.parent import Polyhedra sage: PZZ2.get_action(ZZ^2, op=operator.add) Right action by Ambient free module of rank 2 over the principal ideal domain Integer Ring on Polyhedra in ZZ^2 with precomposition on left by Identity endomorphism of Polyhedra in ZZ^2 with precomposition on right by Generic endomorphism of Ambient free module of rank 2 over the principal ideal domain Integer Ring
"""
extended_self._internal_coerce_map_from(self).__copy__(), extended_other._internal_coerce_map_from(other).__copy__()) else: action = PrecomposedAction(action, extended_other._internal_coerce_map_from(other).__copy__(), extended_self._internal_coerce_map_from(self).__copy__())
extended._internal_coerce_map_from(self).__copy__(), ring._internal_coerce_map_from(other).__copy__()) else: ring._internal_coerce_map_from(other).__copy__(), extended._internal_coerce_map_from(self).__copy__())
""" Create a new inequality object.
INPUT:
- ``polyhedron`` -- the new polyhedron.
- ``data`` -- the H-representation data.
OUTPUT:
A new :class:`~sage.geometry.polyhedron.representation.Inequality` object.
EXAMPLES::
sage: p = Polyhedron([(1,2,3),(2/3,3/4,4/5)]) # indirect doctest sage: next(p.inequality_generator()) An inequality (0, 0, -1) x + 3 >= 0 """
""" Create a new equation object.
INPUT:
- ``polyhedron`` -- the new polyhedron.
- ``data`` -- the H-representation data.
OUTPUT:
A new :class:`~sage.geometry.polyhedron.representation.Equation` object.
EXAMPLES::
sage: p = Polyhedron([(1,2,3),(2/3,3/4,4/5)]) # indirect doctest sage: next(p.equation_generator()) An equation (0, 44, -25) x - 13 == 0 """
""" Create a new vertex object.
INPUT:
- ``polyhedron`` -- the new polyhedron.
- ``data`` -- the V-representation data.
OUTPUT:
A new :class:`~sage.geometry.polyhedron.representation.Vertex` object.
EXAMPLES::
sage: p = Polyhedron([(1,2,3),(2/3,3/4,4/5)], rays=[(5/6,6/7,7/8)]) # indirect doctest sage: next(p.vertex_generator()) A vertex at (1, 2, 3) """
""" Create a new ray object.
INPUT:
- ``polyhedron`` -- the new polyhedron.
- ``data`` -- the V-representation data.
OUTPUT:
A new :class:`~sage.geometry.polyhedron.representation.Ray` object.
EXAMPLES::
sage: p = Polyhedron([(1,2,3),(2/3,3/4,4/5)], rays=[(5/6,6/7,7/8)]) # indirect doctest sage: next(p.ray_generator()) A ray in the direction (140, 144, 147) """
""" Create a new line object.
INPUT:
- ``polyhedron`` -- the new polyhedron.
- ``data`` -- the V-representation data.
OUTPUT:
A new :class:`~sage.geometry.polyhedron.representation.Line` object.
EXAMPLES::
sage: p = Polyhedron([(1,2,3),(2/3,3/4,4/5)], lines=[(5/6,6/7,7/8)]) # indirect doctest sage: next(p.line_generator()) A line in the direction (140, 144, 147) """
|