Volker Braun avatar Volker Braun committed dce0729

rebased for sage-5.10.beta2

Comments (0)

Files changed (10)

+trac_13736-content-take2.patch
+trac_13736-unit_primpart.patch
 trac_14232_ppl_doctest_fixes.patch
-trac_14319.patch
-trac_14319-from_list_to_domain.patch
-trac_14319_fix_fan_isomorphism.patch
-trac_14319-empty.patch
 trac_14523_improve_attach.patch
-trac_12553_ppl_count_points.patch
-trac_12553_ppl_lattice_polytope.patch
-trac_12553_palp_database.patch
 trac_13084_ppl_lattice_polygon.patch
 trac_13084_toric_weierstrass.patch
 trac_13458_toric_Weierstrass_covering.patch

trac_12553_palp_database.patch

-# HG changeset patch
-# Parent 6c2ab10b686cb990b61ff95c152bc5a696f00f4c
-# HG changeset patch
-# Parent 79fc04fc63d1ddbdd042230335ca4af0087f288b
-
-Trac #12553: Add interface for PALP polytope databases
-
-Implements a new PALPreader class to parse the PALP listing of polytopes
-
-diff --git a/sage/geometry/polyhedron/palp_database.py b/sage/geometry/polyhedron/palp_database.py
-new file mode 100644
---- /dev/null
-+++ b/sage/geometry/polyhedron/palp_database.py
-@@ -0,0 +1,469 @@
-+"""
-+Access the PALP database(s) of reflexive lattice polytopes
-+
-+EXAMPLES::
-+
-+    sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+    sage: for lp in PALPreader(2):
-+    ...       cone = Cone([(1,r[0],r[1]) for r in lp.vertices()])
-+    ...       fan = Fan([cone])
-+    ...       X = ToricVariety(fan)
-+    ...       ideal = X.affine_algebraic_patch(cone).defining_ideal()
-+    ...       print lp.n_vertices(), ideal.hilbert_series()
-+    3 (-t^2 - 7*t - 1)/(t^3 - 3*t^2 + 3*t - 1)
-+    3 (-t^2 - t - 1)/(t^3 - 3*t^2 + 3*t - 1)
-+    3 (t^2 + 6*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    3 (t^2 + 2*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    3 (t^2 + 4*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    4 (-t^2 - 5*t - 1)/(t^3 - 3*t^2 + 3*t - 1)
-+    4 (-t^2 - 3*t - 1)/(t^3 - 3*t^2 + 3*t - 1)
-+    4 (t^2 + 2*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    4 (t^2 + 6*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    4 (t^2 + 6*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    4 (t^2 + 2*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    4 (t^2 + 4*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    5 (-t^2 - 3*t - 1)/(t^3 - 3*t^2 + 3*t - 1)
-+    5 (-t^2 - 5*t - 1)/(t^3 - 3*t^2 + 3*t - 1)
-+    5 (t^2 + 4*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+    6 (t^2 + 4*t + 1)/(-t^3 + 3*t^2 - 3*t + 1)
-+"""
-+
-+from subprocess import Popen, PIPE
-+
-+from sage.structure.sage_object import SageObject
-+from sage.matrix.all import matrix
-+from sage.rings.all import Integer, ZZ
-+
-+from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+from sage.geometry.polyhedron.constructor import Polyhedron
-+
-+
-+
-+#########################################################################
-+class PALPreader(SageObject):
-+    """
-+    Read PALP database of polytopes.
-+
-+
-+    INPUT:
-+    
-+    - ``dim`` -- integer. The dimension of the poylhedra
-+        
-+    - ``data_basename`` -- string or ``None`` (default). The directory
-+      and database base filename (PALP usually uses ``'zzdb'``) name
-+      containing the PALP database to read. Defaults to the built-in
-+      database location.
-+        
-+    - ``output`` -- string. How to return the reflexive polyhedron
-+      data. Allowed values = ``'list'``, ``'Polyhedron'`` (default),
-+      ``'pointcollection'``, and ``'PPL'``. Case is ignored.
-+
-+    EXAMPLES::
-+
-+        sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+        sage: polygons = PALPreader(2)
-+        sage: [ (p.n_Vrepresentation(), len(p.integral_points())) for p in polygons ]
-+        [(3, 4), (3, 10), (3, 5), (3, 9), (3, 7), (4, 6), (4, 8), (4, 9), 
-+         (4, 5), (4, 5), (4, 9), (4, 7), (5, 8), (5, 6), (5, 7), (6, 7)]
-+
-+        sage: iter(PALPreader(2, output='list')).next()
-+        [[1, 0], [0, 1], [-1, -1]]
-+        sage: type(_)
-+        <type 'list'>
-+
-+        sage: iter(PALPreader(2, output='Polyhedron')).next()
-+        A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
-+        sage: type(_)
-+        <class 'sage.geometry.polyhedron.backend_ppl.Polyhedra_ZZ_ppl_with_category.element_class'>
-+
-+        sage: iter(PALPreader(2, output='PPL')).next()
-+        A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
-+        sage: type(_)
-+        <class 'sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class'>
-+
-+        sage: iter(PALPreader(2, output='PointCollection')).next()
-+        [ 1,  0],
-+        [ 0,  1],
-+        [-1, -1]
-+        in Ambient free module of rank 2 over the principal ideal domain Integer Ring
-+        sage: type(_)
-+        <type 'sage.geometry.point_collection.PointCollection'>
-+    """
-+
-+    def __init__(self, dim, data_basename=None, output='Polyhedron'):
-+        """
-+        The Python constructor
-+        
-+        See :class:`PALPreader` for documentation.
-+        
-+        TESTS::
-+        
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+        """
-+        self._dim = dim
-+        if data_basename is not None:
-+            self._data_basename = data_basename
-+        else:
-+            import os
-+            SAGE_DATA = os.getenv('SAGE_DATA')
-+            self._data_basename = os.path.join(SAGE_DATA, 'reflexive_polytopes', 
-+                                               'Full'+str(dim)+'d', 'zzdb')
-+            info = self._data_basename + '.info'
-+            if not os.path.exists(info):
-+                raise ValueError('Cannot find PALP database: '+info)
-+        from sage.geometry.polyhedron.parent import Polyhedra
-+        self._polyhedron_parent = Polyhedra(ZZ, dim)
-+        self._output = output.lower()
-+        
-+    def _palp_Popen(self):
-+        """
-+        Open PALP.
-+        
-+        OUTPUT:
-+
-+        A PALP subprocess.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: polygons._palp_Popen()
-+            <subprocess.Popen object at 0x...>
-+        """
-+        return Popen(["class.x", "-b2a", "-di", self._data_basename], stdout=PIPE)
-+
-+    def _read_vertices(self, stdout, rows, cols):
-+        """
-+        Read vertex data from the PALP output pipe.
-+
-+        OUTPUT:
-+        
-+        A list of lists.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: palp = polygons._palp_Popen()
-+            sage: palp.stdout.readline()
-+            '2 3  \n'
-+            sage: polygons._read_vertices(palp.stdout, 2, 3)
-+            [[1, 0], [0, 1], [-1, -1]]
-+        """
-+        m = [ [] for col in range(0,cols) ]
-+        for row in range(0,rows):
-+            for col,x in enumerate(stdout.readline().split()):
-+                m[col].append(ZZ(x))
-+        return m
-+    
-+    def _read_vertices_transposed(self, stdout, rows, cols):
-+        """
-+        Read vertex data from the PALP output pipe.
-+
-+        OUTPUT:
-+        
-+        A list of lists.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: palp = polygons._palp_Popen()
-+            sage: palp.stdout.readline()
-+            '2 3  \n'
-+            sage: polygons._read_vertices_transposed(palp.stdout, 2, 3)
-+            [[1, 0, -1], [0, 1, -1]]
-+        """
-+        m = []
-+        for row in range(0,rows):
-+            m.append( [ ZZ(x) for x in stdout.readline().split() ] )
-+        return m
-+    
-+    def _iterate_list(self, start, stop, step):
-+        """
-+        Iterate over the reflexive polytopes.
-+
-+        INPUT:
-+
-+        - ``start``, ``stop``, ``step`` -- integers specifying the
-+          range to iterate over.
-+
-+        OUTPUT:
-+
-+        A generator for vertex data as a list of lists.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: iter = polygons._iterate_list(0,4,2)
-+            sage: iter.next()
-+            [[1, 0], [0, 1], [-1, -1]]
-+        """
-+        if start is None:
-+            start = 0
-+        if step is None:
-+            step = 1
-+        palp = self._palp_Popen()
-+        try:
-+            palp_out = palp.stdout
-+            i = 0
-+            while True:
-+                l = palp_out.readline().strip()
-+                if l=='' or l.startswith('#'): 
-+                    return  # EOF
-+                l=l.split()
-+                dim = ZZ(l[0]);  # dimension
-+                n = ZZ(l[1]);    # number of vertices
-+                if i>=start and (i-start) % step == 0:
-+                    if dim == self._dim:
-+                        vertices = self._read_vertices(palp_out, dim, n)
-+                    elif n == self._dim:  # PALP sometimes returns transposed data #@!#@
-+                        vertices = self._read_vertices_transposed(palp_out, dim, n)
-+                    else:
-+                        raise ValueError('PALP output dimension mismatch.')
-+                    yield vertices
-+                else: 
-+                    for row in range(0,dim): 
-+                        palp_out.readline()
-+                i += 1
-+                if stop is not None and i>=stop:
-+                    return
-+        finally:
-+            palp.poll()
-+            if palp.returncode is None:
-+                palp.terminate()
-+            palp.poll()
-+            if palp.returncode is None:
-+                palp.kill()
-+    
-+
-+    def _iterate_Polyhedron(self, start, stop, step):
-+        """
-+        Iterate over the reflexive polytopes.
-+
-+        INPUT:
-+
-+        - ``start``, ``stop``, ``step`` -- integers specifying the
-+          range to iterate over.
-+
-+        OUTPUT:
-+
-+        A generator for lattice polyhedra.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: iter = polygons._iterate_Polyhedron(0,4,2)
-+            sage: iter.next()
-+            A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
-+        """
-+        parent = self._polyhedron_parent
-+        for vertices in self._iterate_list(start, stop, step):
-+            p = parent.element_class(parent, [vertices,[],[]], None)
-+            yield p
-+
-+    def _iterate_PPL(self, start, stop, step):
-+        """
-+        Iterate over the reflexive polytopes.
-+
-+        INPUT:
-+
-+        - ``start``, ``stop``, ``step`` -- integers specifying the
-+          range to iterate over.
-+
-+        OUTPUT:
-+
-+        A generator for PPL-based lattice polyhedra.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: iter = polygons._iterate_PPL(0,4,2)
-+            sage: iter.next()
-+            A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
-+        """
-+        for vertices in self._iterate_list(start, stop, step):
-+            yield LatticePolytope_PPL(*vertices)
-+
-+    def _iterate_PointCollection(self, start, stop, step):
-+        """
-+        Iterate over the reflexive polytopes.
-+
-+        INPUT:
-+
-+        - ``start``, ``stop``, ``step`` -- integers specifying the
-+          range to iterate over.
-+
-+        OUTPUT:
-+
-+        A generator for PPL-based lattice polyhedra.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: iter = polygons._iterate_PointCollection(0,4,2)
-+            sage: iter.next()
-+            [ 1,  0],
-+            [ 0,  1],
-+            [-1, -1]
-+            in Ambient free module of rank 2 over the principal ideal domain Integer Ring
-+        """
-+        from sage.modules.free_module import FreeModule
-+        N = FreeModule(ZZ, self._dim)
-+        from sage.geometry.point_collection import PointCollection
-+        for vertices in self._iterate_list(start, stop, step):
-+            yield PointCollection(vertices, module=N)
-+
-+    def _iterate(self, output=None):
-+        """
-+        Iterate over the reflexive polytopes.
-+
-+        INPUT:
-+
-+        - ``output`` -- as in the :class:`PALPreader` constructor.
-+
-+        OUTPUT:
-+
-+        A function generating lattice polytopes in the specified output format.
-+
-+        EAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: func = polygons._iterate(output='list')
-+            sage: func
-+            <bound method PALPreader._iterate_list of <class 'sage.geometry.polyhedron.palp_database.PALPreader'>>
-+            sage: iter = func(0,1,1)
-+            sage: iter.next()
-+            [[1, 0], [0, 1], [-1, -1]]
-+        """
-+        if output is None: 
-+            output = self._output
-+        if output == 'polyhedron':
-+            return self._iterate_Polyhedron
-+        elif output == 'ppl':
-+            return self._iterate_PPL
-+        elif output == 'pointcollection':
-+            return self._iterate_PointCollection
-+        elif output == 'list':
-+            return self._iterate_list
-+        else:
-+            raise TypeError('Unknown output format (='+str(self._output)+').')
-+
-+    def __iter__(self):
-+        """
-+        Iterate over all polytopes.
-+        
-+        OUTPUT:
-+
-+        An iterator for all polytopes.
-+
-+        TESTS::
-+        
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: polygons = PALPreader(2)
-+            sage: polygons.__iter__()
-+            <generator object _iterate_Polyhedron at 0x...>
-+        """
-+        iterator = self._iterate()
-+        return iterator(None, None, None)
-+
-+    def __getitem__(self, item):
-+        """
-+        Return the polytopes(s) indexed by ``item``.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import PALPreader
-+            sage: palp = PALPreader(3)
-+            sage: list(palp[10:30:10])
-+            [A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices, 
-+             A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices]
-+        """
-+        iterator = self._iterate()
-+        if isinstance(item, slice):
-+            return iterator(item.start, item.stop, item.step)
-+        else:
-+            try:
-+                return iterator(item, item+1, 1).next()
-+            except StopIteration:
-+                raise IndexError('Index out of range.')
-+
-+
-+
-+#########################################################################
-+class Reflexive4dHodge(PALPreader):
-+    """
-+    Read the PALP database for Hodge numbers of 4d polytopes.
-+
-+    The database is very large and not installed by default. You can
-+    install it with the command ``install_package('polytopes_db_4d')``.
-+    
-+    INPUT:
-+
-+    - ``h11``, ``h21`` -- Integers. The Hodge numbers of the reflexive
-+      polytopes to list.
-+
-+    Any additional keyword arguments are passed to
-+    :class:`PALPreader`.
-+
-+    EXAMPLES:
-+
-+        sage: from sage.geometry.polyhedron.palp_database import Reflexive4dHodge
-+        sage: ref = Reflexive4dHodge(1,101)             # optional - polytopes_db_4d
-+        sage: iter(ref).next().Vrepresentation()        # optional - polytopes_db_4d
-+        (A vertex at (-1, -1, -1, -1), A vertex at (0, 0, 0, 1), 
-+         A vertex at (0, 0, 1, 0), A vertex at (0, 1, 0, 0), A vertex at (1, 0, 0, 0))
-+    """
-+    def __init__(self, h11, h21, data_basename=None, **kwds):
-+        """
-+        The Python constructor.
-+        
-+        See :class:`Reflexive4dHodge` for documentation.
-+
-+        TESTS::
-+
-+        sage: from sage.geometry.polyhedron.palp_database import Reflexive4dHodge
-+        sage: Reflexive4dHodge(1,101)  # optional - polytopes_db_4d
-+        <class 'sage.geometry.polyhedron.palp_database.Reflexive4dHodge'>
-+        """
-+        dim = 4
-+        if data_basename is None:
-+            import os
-+            SAGE_DATA = os.getenv('SAGE_DATA')
-+            data_basename = os.path.join(SAGE_DATA, 'reflexive_polytopes', 
-+                                         'Hodge4d', 'all')
-+            info = data_basename + '.vinfo'
-+            if not os.path.exists(info):
-+                raise ValueError('Cannot find PALP database: '+info+
-+                                 '. Did you install the polytopes_db_4d optional spkg?')
-+        PALPreader.__init__(self, dim, data_basename=data_basename, **kwds)
-+        self._h11 = h11
-+        self._h21 = h21
-+        
-+    def _palp_Popen(self):
-+        """
-+        Open PALP.
-+        
-+        OUTPUT:
-+
-+        A PALP subprocess.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.palp_database import Reflexive4dHodge
-+            sage: polygons = Reflexive4dHodge(1, 101)   # optional - polytopes_db_4d
-+            sage: polygons._palp_Popen()                # optional - polytopes_db_4d
-+            <subprocess.Popen object at 0x...>
-+        """
-+        return Popen(['class-4d.x', '-He', 
-+                      'H'+str(self._h21)+':'+str(self._h11)+'L100000000', 
-+                      '-di', self._data_basename], stdout=PIPE)
-+        
-+
-+

trac_12553_ppl_count_points.patch

-# HG changeset patch
-# Parent ca877a1fdc06f49f74e422f648ed5c05fea1a570
-# HG changeset patch
-# Parent 9ee052e2cf54354047d4c281e6c596ed35746625
-
-Trac #12553: Add interface for PALP polytope databases
-
-This patch implement counting of integral points (without enumerating them)
-
-diff --git a/sage/geometry/integral_points.pyx b/sage/geometry/integral_points.pyx
---- a/sage/geometry/integral_points.pyx
-+++ b/sage/geometry/integral_points.pyx
-@@ -14,7 +14,7 @@
- from sage.rings.all import QQ, RR, ZZ, gcd, lcm
- from sage.combinat.permutation import Permutation
- from sage.combinat.cartesian_product import CartesianProduct
--from sage.misc.all import prod
-+from sage.misc.all import prod, uniq
- import copy
- 
- ##############################################################################
-@@ -346,8 +346,9 @@
-     - ``box_max`` -- A list of integers. The maximal value for each
-       coordinate of the rectangular bounding box.
- 
--    - ``polyhedron`` -- A :class:`~sage.geometry.polyhedra.Polyhedron`
--      or ``None`` (default).
-+    - ``polyhedron`` -- A
-+      :class:`~sage.geometry.polyhedron.base.Polyhedron_base`, a PPL
-+      :class:`~sage.libs.ppl.C_Polyhedron`, or ``None`` (default).
- 
-     OUTPUT:
- 
-@@ -443,6 +444,20 @@
-          (0, 100000000000000000000000000000000000000000000000001))
-         sage: len( rectangular_box_points([0,-100+10^50], [1,100+10^50], halfplane) )
-         201
-+
-+    Using a PPL polyhedron::
-+    
-+        sage: from sage.libs.ppl import Variable, Generator_System, C_Polyhedron, point
-+        sage: gs = Generator_System()
-+        sage: x = Variable(0); y = Variable(1); z = Variable(2)
-+        sage: gs.insert(point(0*x + 1*y + 0*z))
-+        sage: gs.insert(point(0*x + 1*y + 3*z))
-+        sage: gs.insert(point(3*x + 1*y + 0*z))
-+        sage: gs.insert(point(3*x + 1*y + 3*z))
-+        sage: poly = C_Polyhedron(gs)
-+        sage: rectangular_box_points([0]*3, [3]*3, poly)
-+        ((0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), 
-+         (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (3, 1, 0), (3, 1, 1), (3, 1, 2), (3, 1, 3))
-     """
-     assert len(box_min)==len(box_max)
-     cdef int d = len(box_min)
-@@ -551,8 +566,10 @@
-     cdef object b
-     cdef object coeff
-     cdef object cache
-+    # The index of the inequality in the polyhedron H-representation
-+    cdef int index
- 
--    def __cinit__(self, A, b):
-+    def __cinit__(self, A, b, index=-1):
-         """
-         The Cython constructor
- 
-@@ -570,6 +587,7 @@
-         self.b = b
-         self.coeff = 0
-         self.cache = 0
-+        self.index = int(index)
- 
-     def __repr__(self):
-         """
-@@ -614,9 +632,24 @@
-     cdef bint is_not_satisfied(self, inner_loop_variable):
-         r"""
-         Test the inequality, using the cached value from :meth:`prepare_inner_loop`
-+
-+        OUTPUT: 
-+
-+        Boolean. Whether the inequality is not satisfied.
-         """
-         return inner_loop_variable*self.coeff + self.cache < 0        
- 
-+    cdef bint is_equality(Inequality_generic self, int inner_loop_variable):
-+        r"""
-+        Test the inequality, using the cached value from :meth:`prepare_inner_loop`
-+
-+        OUTPUT: 
-+
-+        Boolean. Given the inequality `Ax+b\geq 0`, this method
-+        returns whether the equality `Ax+b=0` is satisfied.
-+        """
-+        return inner_loop_variable*self.coeff + self.cache == 0        
-+
- 
- 
- DEF INEQ_INT_MAX_DIM = 20
-@@ -677,12 +710,14 @@
-     # the next-to-innermost coefficient
-     cdef int coeff_next
-     cdef int cache_next
-+    # The index of the inequality in the polyhedron H-representation
-+    cdef int index
- 
-     cdef int _to_int(self, x) except? -999:
-         if not x in ZZ: raise ValueError('Not integral.')
-         return int(x)  # raises OverflowError in Cython if necessary
- 
--    def __cinit__(self, A, b, max_abs_coordinates):
-+    def __cinit__(self, A, b, max_abs_coordinates, index=-1):
-         """
-         The Cython constructor
- 
-@@ -696,6 +731,7 @@
-         """
-         cdef int i
-         self.dim = self._to_int(len(A))
-+        self.index = int(index)
-         if self.dim<1 or self.dim>INEQ_INT_MAX_DIM:
-             raise OverflowError('Dimension limit exceeded.')
-         for i in range(0,self.dim):
-@@ -752,6 +788,9 @@
-     cdef bint is_not_satisfied(Inequality_int self, int inner_loop_variable):
-         return inner_loop_variable*self.coeff + self.cache < 0        
- 
-+    cdef bint is_equality(Inequality_int self, int inner_loop_variable):
-+        return inner_loop_variable*self.coeff + self.cache == 0        
-+
- 
- 
- cdef class InequalityCollection:
-@@ -798,7 +837,7 @@
-     """
-     cdef object ineqs_int
-     cdef object ineqs_generic
--
-+    
-     def __repr__(self):
-         r"""
-         Return a string representation.
-@@ -880,31 +919,102 @@
-         self.ineqs_generic = []
-         if polyhedron is None:
-             return
-+
-+        try:
-+            # polyhedron is a PPL C_Polyhedron class?
-+            self._cinit_from_PPL(max_abs_coordinates, permutation, polyhedron)
-+        except AttributeError:
-+            try:
-+                # polyhedron is a Polyhedron class?
-+                self._cinit_from_Polyhedron(max_abs_coordinates, permutation, polyhedron)
-+            except AttributeError:
-+                raise TypeError('Cannot extract Hrepresentation data from polyhedron.')
-+
-+    cdef _cinit_from_PPL(self, max_abs_coordinates, permutation, polyhedron):
-+        """
-+        Initialize the inequalities from a PPL C_Polyhedron
-+
-+        See __cinit__ for a description of the arguments.
-+
-+        EXAMPLES::
-+        
-+            sage: from sage.libs.ppl import Variable, Generator_System, C_Polyhedron, point
-+            sage: gs = Generator_System()
-+            sage: x = Variable(0); y = Variable(1); z = Variable(2)
-+            sage: gs.insert(point(0*x + 0*y + 1*z))
-+            sage: gs.insert(point(0*x + 3*y + 1*z))
-+            sage: gs.insert(point(3*x + 0*y + 1*z))
-+            sage: gs.insert(point(3*x + 3*y + 1*z))
-+            sage: poly = C_Polyhedron(gs)
-+            sage: from sage.geometry.integral_points import InequalityCollection
-+            sage: InequalityCollection(poly, Permutation([1,3,2]), [0]*3, [3]*3 )
-+            The collection of inequalities
-+            integer: (0, 1, 0) x + -1 >= 0
-+            integer: (0, -1, 0) x + 1 >= 0
-+            integer: (1, 0, 0) x + 0 >= 0
-+            integer: (0, 0, 1) x + 0 >= 0
-+            integer: (-1, 0, 0) x + 3 >= 0
-+            integer: (0, 0, -1) x + 3 >= 0
-+        """
-+        for index,c in enumerate(polyhedron.minimized_constraints()):
-+            A = permutation.action(c.coefficients())
-+            b = c.inhomogeneous_term()
-+            try:
-+                H = Inequality_int(A, b, max_abs_coordinates, index)
-+                self.ineqs_int.append(H)
-+            except (OverflowError, ValueError):
-+                H = Inequality_generic(A, b, index)
-+                self.ineqs_generic.append(H)                
-+            if c.is_equality():
-+                A = [ -a for a in A ]
-+                b = -b
-+                try:
-+                    H = Inequality_int(A, b, max_abs_coordinates, index)
-+                    self.ineqs_int.append(H)
-+                except (OverflowError, ValueError):
-+                    H = Inequality_generic(A, b, index)
-+                    self.ineqs_generic.append(H)
-+
-+    cdef _cinit_from_Polyhedron(self, max_abs_coordinates, permutation, polyhedron):
-+        """
-+        Initialize the inequalities from a Sage Polyhedron
-+
-+        See __cinit__ for a description of the arguments.
-+
-+        EXAMPLES::
-+        
-+            sage: from sage.geometry.integral_points import InequalityCollection
-+            sage: line = Polyhedron(eqns=[(2,3,7)])
-+            sage: InequalityCollection(line, Permutation([1,2]), [0]*2, [1]*2 )
-+            The collection of inequalities
-+            integer: (3, 7) x + 2 >= 0
-+            integer: (-3, -7) x + -2 >= 0
-+        """
-         for Hrep_obj in polyhedron.inequality_generator():
-             A, b = self._make_A_b(Hrep_obj, permutation)
-             try:
--                H = Inequality_int(A, b, max_abs_coordinates)
-+                H = Inequality_int(A, b, max_abs_coordinates, Hrep_obj.index())
-                 self.ineqs_int.append(H)
-             except (OverflowError, ValueError):
--                H = Inequality_generic(A, b)
-+                H = Inequality_generic(A, b, Hrep_obj.index())
-                 self.ineqs_generic.append(H)
-         for Hrep_obj in polyhedron.equation_generator():
-             A, b = self._make_A_b(Hrep_obj, permutation)
-             # add inequality
-             try:
--                H = Inequality_int(A, b, max_abs_coordinates)
-+                H = Inequality_int(A, b, max_abs_coordinates, Hrep_obj.index())
-                 self.ineqs_int.append(H)
-             except (OverflowError, ValueError):
--                H = Inequality_generic(A, b)
-+                H = Inequality_generic(A, b, Hrep_obj.index())
-                 self.ineqs_generic.append(H)
-             # add sign-reversed inequality
-             A = [ -a for a in A ]
-             b = -b
-             try:
--                H = Inequality_int(A, b, max_abs_coordinates)
-+                H = Inequality_int(A, b, max_abs_coordinates, Hrep_obj.index())
-                 self.ineqs_int.append(H)
-             except (OverflowError, ValueError):
--                H = Inequality_generic(A, b)
-+                H = Inequality_generic(A, b, Hrep_obj.index())
-                 self.ineqs_generic.append(H)
-         
-     def prepare_next_to_inner_loop(self, p):
-@@ -1054,7 +1164,49 @@
-                 return False
-         return True
-     
-+    def satisfied_as_equalities(self, inner_loop_variable):
-+        """
-+        Return the inequalities (by their index) that are satisfied as
-+        equalities.
- 
-+        INPUT:
-+
-+        - ``inner_loop_variable`` -- Integer. the 0-th coordinate of
-+          the lattice point.
-+
-+        OUTPUT:
-+        
-+        A tuple of integers in ascending order. Each integer is the
-+        index of a H-representation object of the
-+        polyhedron. Equalities are treated as a pair of opposite
-+        inequalities.  
-+        
-+        EXAMPLES::
-+        
-+            sage: from sage.geometry.integral_points import InequalityCollection
-+            sage: quadrant = Polyhedron(rays=[(1,0), (0,1)])
-+            sage: ieqs = InequalityCollection(quadrant, Permutation([1,2]), [-1]*2, [1]*2 )
-+            sage: ieqs.prepare_next_to_inner_loop([-1,0])
-+            sage: ieqs.prepare_inner_loop([-1,0])
-+            sage: ieqs.satisfied_as_equalities(-1)
-+            (1,)
-+            sage: ieqs.satisfied_as_equalities(0)
-+            (0, 1)
-+            sage: ieqs.satisfied_as_equalities(1)
-+            (1,)
-+        """
-+        cdef int i
-+        result = []
-+        for i in range(0,len(self.ineqs_int)):
-+            ineq = self.ineqs_int[i]
-+            if (<Inequality_int>ineq).is_equality(inner_loop_variable):
-+                result.append( (<Inequality_int>ineq).index )
-+        for i in range(0,len(self.ineqs_generic)):
-+            ineq = self.ineqs_generic[i]
-+            if (<Inequality_generic>ineq).is_equality(inner_loop_variable):
-+                result.append( (<Inequality_generic>ineq).index )
-+        return tuple(uniq(result))
-+    
- 
- 
- cpdef print_cache(InequalityCollection inequality_collection):

trac_12553_ppl_lattice_polytope.patch

-# HG changeset patch
-# Parent ea8f149ec0e88183d31b0f76b95758fda2df3ad6
-# HG changeset patch
-# Parent 1e07db38ea8e6c690f661456ccc9db71e07fae78
-
-Trac #12553: Add interface for PALP polytope databases
-
-A PPL-based lattice polytope class
-
-diff --git a/sage/geometry/integral_points.pyx b/sage/geometry/integral_points.pyx
---- a/sage/geometry/integral_points.pyx
-+++ b/sage/geometry/integral_points.pyx
-@@ -333,7 +333,8 @@
- # rectangular bounding box) it is faster to naively enumerate the
- # points. This saves the overhead of triangulating the polytope etc.
- 
--def rectangular_box_points(box_min, box_max, polyhedron=None):
-+def rectangular_box_points(box_min, box_max, polyhedron=None, 
-+                           count_only=False, return_saturated=False):
-     r"""
-     Return the integral points in the lattice bounding box that are
-     also contained in the given polyhedron.
-@@ -350,16 +351,35 @@
-       :class:`~sage.geometry.polyhedron.base.Polyhedron_base`, a PPL
-       :class:`~sage.libs.ppl.C_Polyhedron`, or ``None`` (default).
- 
-+    - ``count_only`` -- Boolean (default: ``False``). Whether to
-+      return only the total number of vertices, and not their
-+      coordinates. Enabling this option speeds up the
-+      enumeration. Cannot be combined with the ``return_saturated``
-+      option.
-+
-+    - ``return_saturated`` -- Boolean (default: ``False``. Whether to
-+      also return which inequalities are saturated for each point of
-+      the polyhedron. Enabling this slows down the enumeration. Cannot
-+      be combined with the ``count_only`` option.
-+
-     OUTPUT:
- 
--    A tuple containing the integral points of the rectangular box
--    spanned by `box_min` and `box_max` and that lie inside the
--    ``polyhedron``. For sufficiently large bounding boxes, this are
--    all integral points of the polyhedron. 
-+    By default, this function returns a tuple containing the integral
-+    points of the rectangular box spanned by `box_min` and `box_max`
-+    and that lie inside the ``polyhedron``. For sufficiently large
-+    bounding boxes, this are all integral points of the polyhedron.
- 
-     If no polyhedron is specified, all integral points of the
-     rectangular box are returned.
- 
-+    If ``count_only`` is specified, only the total number (an integer)
-+    of found lattice points is returned.
-+
-+    If ``return_saturated`` is enabled, then for each integral point a
-+    pair ``(point, Hrep)`` is returned where ``point`` is the point
-+    and ``Hrep`` is the set of indices of the H-representation objects
-+    that are saturated at the point.
-+
-     ALGORITHM:
- 
-     This function implements the naive algorithm towards counting
-@@ -404,6 +424,10 @@
-          (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), 
-          (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 2, 3))
- 
-+        sage: from sage.geometry.integral_points import rectangular_box_points
-+        sage: rectangular_box_points([0,0,0],[1,2,3], count_only=True)
-+        24
-+
-         sage: cell24 = polytopes.twenty_four_cell()
-         sage: rectangular_box_points([-1]*4, [1]*4, cell24)
-         ((-1, 0, 0, 0), (0, -1, 0, 0), (0, 0, -1, 0), (0, 0, 0, -1), 
-@@ -419,6 +443,9 @@
-         sage: len( rectangular_box_points([-d]*4, [d]*4, dilated_cell24) )
-         3625
- 
-+        sage: rectangular_box_points([-d]*4, [d]*4, dilated_cell24, count_only=True)
-+        3625
-+
-         sage: polytope = Polyhedron([(-4,-3,-2,-1),(3,1,1,1),(1,2,1,1),(1,1,3,0),(1,3,2,4)])
-         sage: pts = rectangular_box_points([-4]*4, [4]*4, polytope); pts
-         ((-4, -3, -2, -1), (-1, 0, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1), (1, 1, 3, 0), 
-@@ -446,7 +473,7 @@
-         201
- 
-     Using a PPL polyhedron::
--    
-+
-         sage: from sage.libs.ppl import Variable, Generator_System, C_Polyhedron, point
-         sage: gs = Generator_System()
-         sage: x = Variable(0); y = Variable(1); z = Variable(2)
-@@ -458,8 +485,28 @@
-         sage: rectangular_box_points([0]*3, [3]*3, poly)
-         ((0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), 
-          (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (3, 1, 0), (3, 1, 1), (3, 1, 2), (3, 1, 3))
-+
-+    Optionally, return the information about the saturated inequalities as well::
-+
-+        sage: cube = polytopes.n_cube(3)
-+        sage: cube.Hrepresentation(0)              
-+        An inequality (0, 0, -1) x + 1 >= 0
-+        sage: cube.Hrepresentation(1)
-+        An inequality (0, -1, 0) x + 1 >= 0
-+        sage: cube.Hrepresentation(2)
-+        An inequality (-1, 0, 0) x + 1 >= 0
-+        sage: rectangular_box_points([0]*3, [1]*3, cube, return_saturated=True)
-+        (((0, 0, 0), frozenset([])), 
-+         ((0, 0, 1), frozenset([0])), 
-+         ((0, 1, 0), frozenset([1])), 
-+         ((0, 1, 1), frozenset([0, 1])), 
-+         ((1, 0, 0), frozenset([2])), 
-+         ((1, 0, 1), frozenset([0, 2])), 
-+         ((1, 1, 0), frozenset([1, 2])), 
-+         ((1, 1, 1), frozenset([0, 1, 2])))
-     """
-     assert len(box_min)==len(box_max)
-+    assert not (count_only and return_saturated)
-     cdef int d = len(box_min)
-     diameter = sorted([ (box_max[i]-box_min[i], i) for i in range(0,d) ], reverse=True)
-     diameter_value = [ x[0] for x in diameter ]
-@@ -472,17 +519,32 @@
-     box_max = sort_perm.action(box_max)
-     inequalities = InequalityCollection(polyhedron, sort_perm, box_min, box_max)
- 
-+    if count_only: 
-+        return loop_over_rectangular_box_points(box_min, box_max, inequalities, d, count_only)
-+
-+    points = []
-     v = vector(ZZ, d)
--    points = []
--    for p in loop_over_rectangular_box_points(box_min, box_max, inequalities, d):
--        #  v = vector(ZZ, orig_perm.action(p))   # too slow
--        for i in range(0,d):
--            v[i] = p[orig_perm_list[i]]
--        points.append(copy.copy(v))
-+    if not return_saturated:
-+        for p in loop_over_rectangular_box_points(box_min, box_max, inequalities, d, count_only):
-+            #  v = vector(ZZ, orig_perm.action(p))   # too slow
-+            for i in range(0,d):
-+                v.set(i, p[orig_perm_list[i]])
-+            v_copy = copy.copy(v)
-+            v_copy.set_immutable()
-+            points.append(v_copy)
-+    else:
-+        for p, saturated in \
-+                loop_over_rectangular_box_points_saturated(box_min, box_max, inequalities, d):
-+            for i in range(0,d):
-+                v.set(i, p[orig_perm_list[i]])
-+            v_copy = copy.copy(v)
-+            v_copy.set_immutable()
-+            points.append( (v_copy, saturated) )
-+
-     return tuple(points)
- 
- 
--cdef loop_over_rectangular_box_points(box_min, box_max, inequalities, int d):
-+cdef loop_over_rectangular_box_points(box_min, box_max, inequalities, int d, bint count_only):
-     """
-     The inner loop of :func:`rectangular_box_points`.
-     
-@@ -495,12 +557,78 @@
- 
-     - ``d`` -- the ambient space dimension.
- 
-+    - ``count_only`` -- whether to only return the total number of
-+      lattice points.
-+
-     OUTPUT:
- 
-     The integral points in the bounding box satisfying all
-     inequalities.
-     """
-     cdef int inc
-+    if count_only:
-+        points = 0
-+    else:
-+        points = []
-+    p = copy.copy(box_min)
-+    inequalities.prepare_next_to_inner_loop(p)
-+    while True:
-+        inequalities.prepare_inner_loop(p)
-+        i_min = box_min[0]
-+        i_max = box_max[0]
-+        # Find the lower bound for the allowed region
-+        while i_min <= i_max:
-+            if inequalities.are_satisfied(i_min):
-+                break
-+            i_min += 1
-+        # Find the upper bound for the allowed region
-+        while i_min <= i_max:
-+            if inequalities.are_satisfied(i_max):
-+                break
-+            i_max -= 1
-+        # The points i_min .. i_max are contained in the polyhedron
-+        if count_only:
-+            if i_max>=i_min:
-+                points += i_max-i_min+1
-+        else:
-+            i = i_min
-+            while i <= i_max:
-+                p[0] = i
-+                points.append(tuple(p))
-+                i += 1
-+        # finally increment the other entries in p to move on to next inner loop
-+        inc = 1
-+        if d==1: return points
-+        while True:
-+            if p[inc]==box_max[inc]:
-+                p[inc] = box_min[inc]
-+                inc += 1
-+                if inc==d:
-+                    return points
-+            else:
-+                p[inc] += 1
-+                break
-+        if inc>1:
-+            inequalities.prepare_next_to_inner_loop(p)
-+
-+
-+
-+cdef loop_over_rectangular_box_points_saturated(box_min, box_max, inequalities, int d):
-+    """
-+    The analog of :func:`rectangular_box_points` except that it keeps
-+    track of which inequalities are saturated.
-+    
-+    INPUT:
-+
-+    See :func:`rectangular_box_points`.
-+
-+    OUTPUT:
-+
-+    The integral points in the bounding box satisfying all
-+    inequalities, each point being returned by a coordinate vector and
-+    a set of H-representation object indices.
-+    """
-+    cdef int inc
-     points = []
-     p = copy.copy(box_min)
-     inequalities.prepare_next_to_inner_loop(p)
-@@ -522,7 +650,8 @@
-         i = i_min
-         while i <= i_max:
-             p[0] = i
--            points.append(tuple(p))
-+            saturated = inequalities.satisfied_as_equalities(i)
-+            points.append( (tuple(p), saturated) )
-             i += 1
-         # finally increment the other entries in p to move on to next inner loop
-         inc = 1
-@@ -651,7 +780,7 @@
-         return inner_loop_variable*self.coeff + self.cache == 0        
- 
- 
--
-+# if dim>20 then we always use the generic inequalities (Inequality_generic)
- DEF INEQ_INT_MAX_DIM = 20
- 
- cdef class Inequality_int:
-@@ -1176,10 +1305,9 @@
- 
-         OUTPUT:
-         
--        A tuple of integers in ascending order. Each integer is the
--        index of a H-representation object of the
--        polyhedron. Equalities are treated as a pair of opposite
--        inequalities.  
-+        A set of integers in ascending order. Each integer is the
-+        index of a H-representation object of the polyhedron (either a
-+        inequality or an equation).
-         
-         EXAMPLES::
-         
-@@ -1189,11 +1317,11 @@
-             sage: ieqs.prepare_next_to_inner_loop([-1,0])
-             sage: ieqs.prepare_inner_loop([-1,0])
-             sage: ieqs.satisfied_as_equalities(-1)
--            (1,)
-+            frozenset([1])
-             sage: ieqs.satisfied_as_equalities(0)
--            (0, 1)
-+            frozenset([0, 1])
-             sage: ieqs.satisfied_as_equalities(1)
--            (1,)
-+            frozenset([1])
-         """
-         cdef int i
-         result = []
-@@ -1205,7 +1333,7 @@
-             ineq = self.ineqs_generic[i]
-             if (<Inequality_generic>ineq).is_equality(inner_loop_variable):
-                 result.append( (<Inequality_generic>ineq).index )
--        return tuple(uniq(result))
-+        return frozenset(result)
-     
- 
- 
-diff --git a/sage/geometry/polyhedron/ppl_lattice_polytope.py b/sage/geometry/polyhedron/ppl_lattice_polytope.py
-new file mode 100644
---- /dev/null
-+++ b/sage/geometry/polyhedron/ppl_lattice_polytope.py
-@@ -0,0 +1,1028 @@
-+"""
-+Fast Lattice Polytopes using PPL.
-+
-+The :func:`LatticePolytope_PPL` class is a thin wrapper around PPL
-+polyhedra. Its main purpose is to be fast to construct, at the cost of
-+being much less full-featured than the usual polyhedra. This makes it
-+possible to iterate with it over the list of all 473800776 reflexive
-+polytopes in 4 dimensions.
-+
-+.. NOTE::
-+
-+    For general lattice polyhedra you should use
-+    :func:`~sage.geometry.polyhedon.constructor.Polyhedron` with
-+    `base_ring=ZZ`.
-+
-+EXAMPLES::
-+
-+    sage: vertices = [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (-9, -6, -1, -1)]
-+    sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+    sage: P = LatticePolytope_PPL(vertices);  P
-+    A 4-dimensional lattice polytope in ZZ^4 with 5 vertices
-+    sage: P.integral_points()
-+    ((-9, -6, -1, -1), (-3, -2, 0, 0), (-2, -1, 0, 0), (-1, -1, 0, 0),
-+     (-1, 0, 0, 0), (0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0))
-+    sage: P.integral_points_not_interior_to_facets()
-+    ((-9, -6, -1, -1), (-3, -2, 0, 0), (0, 0, 0, 0), (1, 0, 0, 0),
-+     (0, 1, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0))
-+
-+Fibrations of the lattice polytopes are defined as lattice
-+sub-polytopes and give rise to fibrations of toric varieties for
-+suitable fan refinements. We can compute them using
-+:meth:`~LatticePolytope_PPL.fibration_generator` ::
-+
-+    sage: F = P.fibration_generator(2).next()
-+    sage: F.vertices()
-+    ((1, 0, 0, 0), (0, 1, 0, 0), (-3, -2, 0, 0))
-+
-+Finally, we can compute automorphisms and identify fibrations that
-+only differ by a lattice automorphism::
-+
-+    sage: square = LatticePolytope_PPL((-1,-1),(-1,1),(1,-1),(1,1))
-+    sage: fibers = [ f.vertices() for f in square.fibration_generator(1) ];  fibers
-+    [((1, 0), (-1, 0)), ((0, 1), (0, -1)), ((-1, -1), (1, 1)), ((-1, 1), (1, -1))]
-+    sage: square.pointsets_mod_automorphism(fibers)
-+    (frozenset([(0, 1), (0, -1)]), frozenset([(1, 1), (-1, -1)]))
-+
-+AUTHORS:
-+
-+    - Volker Braun: initial version, 2012
-+"""
-+
-+########################################################################
-+#       Copyright (C) 2012 Volker Braun <vbraun.name@gmail.com>
-+#
-+#  Distributed under the terms of the GNU General Public License (GPL)
-+#
-+#                  http://www.gnu.org/licenses/
-+########################################################################
-+
-+
-+
-+import copy
-+from sage.rings.integer import GCD_list
-+from sage.rings.integer_ring import ZZ
-+from sage.misc.all import union, cached_method, prod, uniq
-+from sage.matrix.constructor import matrix, column_matrix, vector, diagonal_matrix
-+from sage.libs.ppl import (
-+    C_Polyhedron, Linear_Expression, Variable,
-+    point, ray, line, Generator, Generator_System,
-+    Constraint_System,
-+    Poly_Con_Relation)
-+
-+
-+
-+
-+########################################################################
-+def LatticePolytope_PPL(*args):
-+    """
-+    Construct a new instance of the PPL-based lattice polytope class.
-+
-+    EXAMPLES::
-+
-+        sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+        sage: LatticePolytope_PPL((0,0),(1,0),(0,1))
-+        A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
-+
-+        sage: from sage.libs.ppl import point, Generator_System, C_Polyhedron, Linear_Expression, Variable
-+        sage: p = point(Linear_Expression([2,3],0));  p
-+        point(2/1, 3/1)
-+        sage: LatticePolytope_PPL(p)
-+        A 0-dimensional lattice polytope in ZZ^2 with 1 vertex
-+
-+        sage: P = C_Polyhedron(Generator_System(p));  P
-+        A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point
-+        sage: LatticePolytope_PPL(P)
-+        A 0-dimensional lattice polytope in ZZ^2 with 1 vertex
-+
-+    A ``TypeError`` is raised if the arguments do not specify a lattice polytope::
-+
-+        sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+        sage: LatticePolytope_PPL((0,0),(1/2,1))
-+        Traceback (most recent call last):
-+        ...
-+        TypeError: no conversion of this rational to integer
-+
-+        sage: from sage.libs.ppl import point, Generator_System, C_Polyhedron, Linear_Expression, Variable
-+        sage: p = point(Linear_Expression([2,3],0), 5);  p
-+        point(2/5, 3/5)
-+        sage: LatticePolytope_PPL(p)
-+        Traceback (most recent call last):
-+        ...
-+        TypeError: The generator is not a lattice polytope generator.
-+
-+        sage: P = C_Polyhedron(Generator_System(p));  P
-+        A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point
-+        sage: LatticePolytope_PPL(P)
-+        Traceback (most recent call last):
-+        ...
-+        TypeError: The polyhedron has non-integral generators.
-+    """
-+    if len(args)==1 and isinstance(args[0], C_Polyhedron):
-+        polyhedron = args[0]
-+        #if not polyhedron.is_bounded():
-+        #    raise TypeError('The polyhedron is unbounded.')
-+        if not all(p.is_point() and p.divisor().is_one() for p in polyhedron.generators()):
-+            raise TypeError('The polyhedron has non-integral generators.')
-+        return LatticePolytope_PPL_class(polyhedron)
-+    if len(args)==1:
-+        vertices = args[0]
-+        try:
-+            return LatticePolytope_PPL(*vertices)
-+        except TypeError:
-+            pass
-+    vertices = args
-+    gs = Generator_System()
-+    for v in vertices:
-+        if isinstance(v, Generator):
-+            if (not v.is_point()) or (not v.divisor().is_one()):
-+                raise TypeError('The generator is not a lattice polytope generator.')
-+            gs.insert(v)
-+        else:
-+            gs.insert(point(Linear_Expression(v, 0)))
-+    return LatticePolytope_PPL_class(gs)
-+
-+
-+########################################################################
-+class LatticePolytope_PPL_class(C_Polyhedron):
-+    """
-+    The lattice polytope class.
-+
-+    You should use :func:LatticePolytope_PPL` to construct instances.
-+
-+    EXAMPLES::
-+
-+        sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+        sage: LatticePolytope_PPL((0,0),(1,0),(0,1))
-+        A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
-+    """
-+
-+    def _repr_(self):
-+        """
-+        Return the string representation
-+
-+        OUTPUT:
-+
-+        A string.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: P = LatticePolytope_PPL((0,0),(1,0),(0,1))
-+            sage: P
-+            A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
-+            sage: P._repr_()
-+            'A 2-dimensional lattice polytope in ZZ^2 with 3 vertices'
-+
-+            sage: LatticePolytope_PPL()
-+            The empty lattice polytope in ZZ^0
-+        """
-+        desc = ''
-+        if self.n_vertices()==0:
-+            desc += 'The empty lattice polytope'
-+        else:
-+            desc += 'A ' + repr(self.affine_dimension()) + '-dimensional lattice polytope'
-+        desc += ' in ZZ^' + repr(self.space_dimension())
-+
-+        if self.n_vertices()>0:
-+            desc += ' with '
-+            desc += repr(self.n_vertices())
-+            if self.n_vertices()==1: desc += ' vertex'
-+            else:                    desc += ' vertices'
-+        return desc
-+
-+
-+
-+    def is_bounded(self):
-+        """
-+        Return whether the lattice polytope is compact.
-+
-+        OUTPUT:
-+
-+        Always ``True``, since polytopes are by definition compact.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((0,0),(1,0),(0,1)).is_bounded()
-+            True
-+        """
-+        return True
-+
-+    @cached_method
-+    def n_vertices(self):
-+        """
-+        Return the number of vertices.
-+
-+        OUTPUT:
-+
-+        An integer, the number of vertices.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((0,0,0), (1,0,0), (0,1,0)).n_vertices()
-+            3
-+        """
-+        return len(self.minimized_generators())
-+
-+    @cached_method
-+    def is_simplex(self):
-+        r"""
-+        Return whether the polyhedron is a simplex.
-+
-+        OUTPUT:
-+
-+        Boolean, whether the polyhedron is a simplex (possibly of
-+        strictly smaller dimension than the ambient space).
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((0,0,0), (1,0,0), (0,1,0)).is_simplex()
-+            True
-+        """
-+        return self.affine_dimension()+1==self.n_vertices()
-+
-+    @cached_method
-+    def bounding_box(self):
-+        r"""
-+        Return the coordinates of a rectangular box containing the non-empty polytope.
-+
-+        OUTPUT:
-+
-+        A pair of tuples ``(box_min, box_max)`` where ``box_min`` are
-+        the coordinates of a point bounding the coordinates of the
-+        polytope from below and ``box_max`` bounds the coordinates
-+        from above.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((0,0),(1,0),(0,1)).bounding_box()
-+            ((0, 0), (1, 1))
-+        """
-+        box_min = []
-+        box_max = []
-+        if self.is_empty():
-+            raise ValueError('Empty polytope is not allowed')
-+        for i in range(0, self.space_dimension()):
-+            x = Variable(i)
-+            coords = [ v.coefficient(x) for v in self.generators() ]
-+            max_coord = max(coords)
-+            min_coord = min(coords)
-+            box_max.append(max_coord)
-+            box_min.append(min_coord)
-+        return (tuple(box_min), tuple(box_max))
-+
-+    @cached_method
-+    def n_integral_points(self):
-+        """
-+        Return the number of integral points.
-+
-+        OUTPUT:
-+
-+        Integer. The number of integral points contained in the
-+        lattice polytope.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((0,0),(1,0),(0,1)).n_integral_points()
-+            3
-+        """
-+        if self.is_empty():
-+            return tuple()
-+        box_min, box_max = self.bounding_box()
-+        from sage.geometry.integral_points import rectangular_box_points
-+        return rectangular_box_points(box_min, box_max, self, count_only=True)
-+
-+    @cached_method
-+    def integral_points(self):
-+        r"""
-+        Return the integral points in the polyhedron.
-+
-+        Uses the naive algorithm (iterate over a rectangular bounding
-+        box).
-+
-+        OUTPUT:
-+
-+        The list of integral points in the polyhedron. If the
-+        polyhedron is not compact, a ``ValueError`` is raised.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((-1,-1),(1,0),(1,1),(0,1)).integral_points()
-+            ((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))
-+
-+            sage: simplex = LatticePolytope_PPL((1,2,3), (2,3,7), (-2,-3,-11))
-+            sage: simplex.integral_points()
-+            ((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))
-+
-+        The polyhedron need not be full-dimensional::
-+
-+            sage: simplex = LatticePolytope_PPL((1,2,3,5), (2,3,7,5), (-2,-3,-11,5))
-+            sage: simplex.integral_points()
-+            ((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))
-+
-+            sage: point = LatticePolytope_PPL((2,3,7))
-+            sage: point.integral_points()
-+            ((2, 3, 7),)
-+
-+            sage: empty = LatticePolytope_PPL()
-+            sage: empty.integral_points()
-+            ()
-+
-+        Here is a simplex where the naive algorithm of running over
-+        all points in a rectangular bounding box no longer works fast
-+        enough::
-+
-+            sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
-+            sage: simplex = LatticePolytope_PPL(v); simplex
-+            A 4-dimensional lattice polytope in ZZ^4 with 5 vertices
-+            sage: len(simplex.integral_points())
-+            49
-+
-+        Finally, the 3-d reflexive polytope number 4078::
-+
-+            sage: v = [(1,0,0), (0,1,0), (0,0,1), (0,0,-1), (0,-2,1),
-+            ...        (-1,2,-1), (-1,2,-2), (-1,1,-2), (-1,-1,2), (-1,-3,2)]
-+            sage: P = LatticePolytope_PPL(*v)
-+            sage: pts1 = P.integral_points()                     # Sage's own code
-+            sage: pts2 = LatticePolytope(v).points().columns()   # PALP
-+            sage: for p in pts1: p.set_immutable()
-+            sage: for p in pts2: p.set_immutable()
-+            sage: set(pts1) == set(pts2)
-+            True
-+
-+            sage: timeit('Polyhedron(v).integral_points()')   # random output
-+            sage: timeit('LatticePolytope(v).points()')       # random output
-+            sage: timeit('LatticePolytope_PPL(*v).integral_points()')       # random output
-+        """
-+        if self.is_empty():
-+            return tuple()
-+        box_min, box_max = self.bounding_box()
-+        from sage.geometry.integral_points import rectangular_box_points
-+        points = rectangular_box_points(box_min, box_max, self)
-+        if not self.n_integral_points.is_in_cache():
-+            self.n_integral_points.set_cache(len(points))
-+        return points
-+
-+    @cached_method
-+    def _integral_points_saturating(self):
-+        """
-+        Return the integral points together with information about
-+        which inequalities are saturated.
-+
-+        See :func:`~sage.geometry.integral_points.rectangular_box_points`.
-+
-+        OUTPUT:
-+
-+        A tuple of pairs (one for each integral point) consisting of a
-+        pair ``(point, Hrep)``, where ``point`` is the coordinate
-+        vector of the intgeral point and ``Hrep`` is the set of
-+        indices of the :meth:`minimized_constraints` that are
-+        saturated at the point.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: quad = LatticePolytope_PPL((-1,-1),(0,1),(1,0),(1,1))
-+            sage: quad._integral_points_saturating()
-+            (((-1, -1), frozenset([0, 1])),
-+             ((0, 0), frozenset([])),
-+             ((0, 1), frozenset([0, 3])),
-+             ((1, 0), frozenset([1, 2])),
-+             ((1, 1), frozenset([2, 3])))
-+        """
-+        if self.is_empty():
-+            return tuple()
-+        box_min, box_max = self.bounding_box()
-+        from sage.geometry.integral_points import rectangular_box_points
-+        points= rectangular_box_points(box_min, box_max, self, return_saturated=True)
-+        if not self.n_integral_points.is_in_cache():
-+            self.n_integral_points.set_cache(len(points))
-+        if not self.integral_points.is_in_cache():
-+            self.integral_points.set_cache(tuple(p[0] for p in points))
-+        return points
-+
-+    @cached_method
-+    def integral_points_not_interior_to_facets(self):
-+        """
-+        Return the integral points not interior to facets
-+
-+        OUTPUT:
-+
-+        A tuple whose entries are the coordinate vectors of integral
-+        points not interior to facets (codimension one faces) of the
-+        lattice polytope.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: square = LatticePolytope_PPL((-1,-1),(-1,1),(1,-1),(1,1))
-+            sage: square.n_integral_points()
-+            9
-+            sage: square.integral_points_not_interior_to_facets()
-+            ((-1, -1), (-1, 1), (0, 0), (1, -1), (1, 1))
-+        """
-+        n = 1 + self.space_dimension() - self.affine_dimension()
-+        return tuple(p[0] for p in self._integral_points_saturating() if len(p[1])!=n)
-+
-+    @cached_method
-+    def vertices(self):
-+        r"""
-+        Return the vertices as a tuple of `\ZZ`-vectors.
-+
-+        OUTPUT:
-+
-+        A tuple of `\ZZ`-vectors. Each entry is the coordinate vector
-+        of an integral points of the lattice polytope.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: p = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
-+            sage: p.vertices()
-+            ((-9, -6, -1, -1), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0))
-+            sage: p.minimized_generators()
-+            Generator_System {point(-9/1, -6/1, -1/1, -1/1), point(0/1, 0/1, 0/1, 1/1),
-+            point(0/1, 0/1, 1/1, 0/1), point(0/1, 1/1, 0/1, 0/1), point(1/1, 0/1, 0/1, 0/1)}
-+        """
-+        d = self.space_dimension()
-+        v = vector(ZZ, d)
-+        points = []
-+        for g in self.minimized_generators():
-+            for i in range(0,d):
-+                v[i] = g.coefficient(Variable(i))
-+            v_copy = copy.copy(v)
-+            v_copy.set_immutable()
-+            points.append(v_copy)
-+        return tuple(points)
-+
-+    @cached_method
-+    def is_full_dimensional(self):
-+        """
-+        Return whether the lattice polytope is full dimensional.
-+
-+        OUTPUT:
-+
-+        Boolean. Whether the :meth:`affine_dimension` equals the
-+        ambient space dimension.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: p = LatticePolytope_PPL((0,0),(0,1))
-+            sage: p.is_full_dimensional()
-+            False
-+            sage: q = LatticePolytope_PPL((0,0),(0,1),(1,0))
-+            sage: q.is_full_dimensional()
-+            True
-+        """
-+
-+        return self.affine_dimension() == self.space_dimension()
-+
-+    def fibration_generator(self, dim):
-+        """
-+        Generate the lattice polytope fibrations.
-+
-+        For the purposes of this function, a lattice polytope fiber is
-+        a sub-lattice polytope. Projecting the plane spanned by the
-+        subpolytope to a point yields another lattice polytope, the
-+        base of the fibration.
-+
-+        INPUT:
-+
-+        - ``dim`` -- integer. The dimension of the lattice polytope
-+          fiber.
-+
-+        OUTPUT:
-+
-+        A generator yielding the distinct lattice polytope fibers of
-+        given dimension.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: p = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
-+            sage: list( p.fibration_generator(2) )
-+            [A 2-dimensional lattice polytope in ZZ^4 with 3 vertices]
-+        """
-+        assert self.is_full_dimensional()
-+        codim = self.space_dimension() - dim
-+        # "points" are the potential vertices of the fiber. They are
-+        # in the $codim$-skeleton of the polytope, which is contained
-+        # in the points that saturate at least $dim$ equations.
-+        points = [ p for p in self._integral_points_saturating() if len(p[1])>=dim ]
-+        points = sorted(points, key=lambda x:len(x[1]))
-+
-+        # iterate over point combinations subject to all points being on one facet.
-+        def point_combinations_iterator(n, i0=0, saturated=None):
-+            for i in range(i0, len(points)):
-+                p, ieqs = points[i]
-+                if saturated is None:
-+                    saturated_ieqs = ieqs
-+                else:
-+                    saturated_ieqs = saturated.intersection(ieqs)
-+                if len(saturated_ieqs)==0:
-+                    continue
-+                if n == 1:
-+                    yield [i]
-+                else:
-+                    for c in point_combinations_iterator(n-1, i+1, saturated_ieqs):
-+                        yield [i] + c
-+
-+        point_lines = [ line(Linear_Expression(p[0].list(),0)) for p in points ]
-+        origin = point()
-+        fibers = set()
-+        gs = Generator_System()
-+        for indices in point_combinations_iterator(dim):
-+            gs.clear()
-+            gs.insert(origin)
-+            for i in indices:
-+                gs.insert(point_lines[i])
-+            plane = C_Polyhedron(gs)
-+            if plane.affine_dimension() != dim:
-+                continue
-+            plane.intersection_assign(self)
-+            if (not self.is_full_dimensional()) and (plane.affine_dimension() != dim):
-+                continue
-+            try:
-+                fiber = LatticePolytope_PPL(plane)
-+            except TypeError:   # not a lattice polytope
-+                continue
-+            fiber_vertices = tuple(sorted(fiber.vertices()))
-+            if fiber_vertices not in fibers:
-+                yield fiber
-+                fibers.update([fiber_vertices])
-+
-+    def pointsets_mod_automorphism(self, pointsets):
-+        """
-+        Return ``pointsets`` modulo the automorphisms of ``self``.
-+
-+        INPUT:
-+
-+        - ``polytopes`` a tuple/list/iterable of subsets of the
-+          integral points of ``self``.
-+
-+        OUTPUT:
-+
-+        Representatives of the point sets modulo the
-+        :meth:`lattice_automorphism_group` of ``self``.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: square = LatticePolytope_PPL((-1,-1),(-1,1),(1,-1),(1,1))
-+            sage: fibers = [ f.vertices() for f in square.fibration_generator(1) ]
-+            sage: square.pointsets_mod_automorphism(fibers)
-+            (frozenset([(0, 1), (0, -1)]), frozenset([(1, 1), (-1, -1)]))
-+
-+            sage: cell24 = LatticePolytope_PPL(
-+            ...   (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,-1,-1,1),(0,0,-1,1),
-+            ...   (0,-1,0,1),(-1,0,0,1),(1,0,0,-1),(0,1,0,-1),(0,0,1,-1),(-1,1,1,-1),
-+            ...   (1,-1,-1,0),(0,0,-1,0),(0,-1,0,0),(-1,0,0,0),(1,-1,0,0),(1,0,-1,0),
-+            ...   (0,1,1,-1),(-1,1,1,0),(-1,1,0,0),(-1,0,1,0),(0,-1,-1,1),(0,0,0,-1))
-+            sage: fibers = [ f.vertices() for f in cell24.fibration_generator(2) ]
-+            sage: cell24.pointsets_mod_automorphism(fibers)   # long time
-+            (frozenset([(1, 0, -1, 0), (-1, 0, 1, 0), (0, -1, -1, 1), (0, 1, 1, -1)]),
-+             frozenset([(-1, 0, 0, 0), (1, 0, 0, 0), (0, 0, 0, 1),
-+                        (1, 0, 0, -1), (0, 0, 0, -1), (-1, 0, 0, 1)]))
-+        """
-+        points = set()
-+        for ps in pointsets:
-+            points.update(ps)
-+        points = tuple(points)
-+        Aut = self.lattice_automorphism_group(points, 
-+                                              point_labels=tuple(range(len(points))))
-+        indexsets = set([ frozenset([points.index(p) for p in ps]) for ps in pointsets ])
-+        orbits = []
-+        while len(indexsets)>0:
-+            idx = indexsets.pop()
-+            orbits.append(frozenset([points[i] for i in idx]))
-+            for g in Aut:
-+                g_idx = frozenset([g(i) for i in idx])
-+                indexsets.difference_update([g_idx])
-+        return tuple(orbits)
-+
-+    @cached_method
-+    def ambient_space(self):
-+        r"""
-+        Return the ambient space.
-+
-+        OUTPUT:
-+
-+        The free module `\ZZ^d`, where `d` is the ambient space
-+        dimension.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: point = LatticePolytope_PPL((1,2,3))
-+            sage: point.ambient_space()
-+            Ambient free module of rank 3 over the principal ideal domain Integer Ring
-+        """
-+        from sage.modules.free_module import FreeModule
-+        return FreeModule(ZZ, self.space_dimension())
-+
-+    def contains(self, point_coordinates):
-+        r"""
-+        Test whether point is contained in the polytope.
-+        
-+        INPUT:
-+ 
-+        - ``point_coordinates`` -- a list/tuple/iterable of rational
-+          numbers. The coordinates of the point.
-+
-+        OUTPUT:
-+
-+        Boolean.
-+        
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: line = LatticePolytope_PPL((1,2,3), (-1,-2,-3))
-+            sage: line.contains([0,0,0])
-+            True
-+            sage: line.contains([1,0,0])
-+            False
-+        """
-+        p = C_Polyhedron(point(Linear_Expression(list(point_coordinates), 1)))
-+        is_included = Poly_Con_Relation.is_included()
-+        for c in self.constraints():
-+            if not p.relation_with(c).implies(is_included):
-+                return False
-+        return True
-+        
-+    @cached_method
-+    def contains_origin(self):
-+        """
-+        Test whether the polytope contains the origin
-+
-+        OUTPUT:
-+        
-+        Boolean.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((1,2,3), (-1,-2,-3)).contains_origin()
-+            True
-+            sage: LatticePolytope_PPL((1,2,5), (-1,-2,-3)).contains_origin()
-+            False
-+        """
-+        return self.contains(self.ambient_space().zero())
-+
-+    @cached_method
-+    def affine_space(self):
-+        r"""
-+        Return the affine space spanned by the polytope.
-+
-+        OUTPUT:
-+
-+        The free module `\ZZ^n`, where `n` is the dimension of the
-+        affine space spanned by the points of the polytope.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: point = LatticePolytope_PPL((1,2,3))
-+            sage: point.affine_space()
-+            Free module of degree 3 and rank 0 over Integer Ring
-+            Echelon basis matrix:
-+            []
-+            sage: line = LatticePolytope_PPL((1,1,1), (1,2,3))
-+            sage: line.affine_space()
-+            Free module of degree 3 and rank 1 over Integer Ring
-+            Echelon basis matrix:
-+            [0 1 2]
-+        """
-+        vertices = self.vertices()
-+        if not self.contains_origin():
-+            v0 = vertices[0]
-+            vertices = [v-v0 for v in vertices]
-+        return self.ambient_space().span(vertices).saturation()
-+
-+    def affine_lattice_polytope(self):
-+        """
-+        Return the lattice polytope restricted to
-+        :meth:`affine_space`.
-+
-+        OUTPUT:
-+
-+        A new, full-dimensional lattice polytope.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: poly_4d = LatticePolytope_PPL((-9,-6,0,0),(0,1,0,0),(1,0,0,0));  poly_4d
-+            A 2-dimensional lattice polytope in ZZ^4 with 3 vertices
-+            sage: poly_4d.space_dimension()
-+            4
-+            sage: poly_2d = poly_4d.affine_lattice_polytope();  poly_2d
-+            A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
-+            sage: poly_2d.space_dimension()
-+            2
-+        """
-+        V = self.affine_space()
-+        if self.contains_origin():
-+            vertices = [ V.coordinates(v) for v in self.vertices() ]
-+        else:
-+            v0 = vertices[0]
-+            vertices = [ V.coordinates(v-v0) for v in self.vertices() ]
-+        return LatticePolytope_PPL(*vertices)
-+
-+    @cached_method
-+    def base_projection(self, fiber):
-+        """
-+        The projection that maps the sub-polytope ``fiber`` to a
-+        single point.
-+
-+        OUTPUT:
-+
-+        The quotient module of the ambient space modulo the
-+        :meth:`affine_space` spanned by the fiber.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: poly = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
-+            sage: fiber = poly.fibration_generator(2).next()
-+            sage: poly.base_projection(fiber)
-+            Finitely generated module V/W over Integer Ring with invariants (0, 0)
-+        """
-+        return self.ambient_space().quotient(fiber.affine_space())
-+
-+    @cached_method
-+    def base_projection_matrix(self, fiber):
-+        """
-+        The projection that maps the sub-polytope ``fiber`` to a
-+        single point.
-+
-+        OUTPUT:
-+
-+        An integer matrix that represents the projection to the
-+        base.
-+
-+        .. SEEALSO::
-+        
-+            The :meth:`base_projection` yields equivalent information,
-+            and is easier to use. However, just returning the matrix
-+            has lower overhead.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: poly = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
-+            sage: fiber = poly.fibration_generator(2).next()
-+            sage: poly.base_projection_matrix(fiber)
-+            [0 0 1 0]
-+            [0 0 0 1]
-+
-+        Note that the basis choice in :meth:`base_projection` for the
-+        quotient is usually different::
-+
-+            sage: proj = poly.base_projection(fiber)
-+            sage: proj_matrix = poly.base_projection_matrix(fiber)
-+            sage: [ proj(p) for p in poly.integral_points() ]
-+            [(-1, -1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (1, 0), (0, 1)]
-+            sage: [ proj_matrix*p for p in poly.integral_points() ]
-+            [(-1, -1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 1), (1, 0)]
-+        """
-+        return matrix(ZZ, fiber.vertices()).right_kernel_matrix()
-+
-+    def base_rays(self, fiber, points):
-+        """
-+        Return the primitive lattice vectors that generate the
-+        direction given by the base projection of points.
-+
-+        INPUT:
-+
-+        - ``fiber`` -- a sub-lattice polytope defining the
-+          :meth:`base_projection`.
-+
-+        - ``points`` -- the points to project to the base.
-+
-+        OUTPUT:
-+
-+        A tuple of primitive `\ZZ`-vectors.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: poly = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
-+            sage: fiber = poly.fibration_generator(2).next()
-+            sage: poly.base_rays(fiber, poly.integral_points_not_interior_to_facets())
-+            ((-1, -1), (0, 1), (1, 0))
-+
-+            sage: p = LatticePolytope_PPL((1,0),(1,2),(-1,0))
-+            sage: f = LatticePolytope_PPL((1,0),(-1,0))
-+            sage: p.base_rays(f, p.integral_points())
-+            ((1),)
-+        """
-+        quo = self.base_projection(fiber)
-+        vertices = []
-+        for p in points:
-+            v = vector(ZZ,quo(p))
-+            if v.is_zero():
-+                continue
-+            d =  GCD_list(v.list())
-+            if d>1:
-+                for i in range(0,v.degree()):
-+                    v[i] /= d
-+            v.set_immutable()
-+            vertices.append(v)
-+        return tuple(uniq(vertices))
-+
-+    @cached_method
-+    def has_IP_property(self):
-+        """
-+        Whether the lattice polytope has the IP property.
-+
-+        That is, the polytope is full-dimensional and the origin is a
-+        interior point not on the boundary.
-+
-+        OUTPUT:
-+
-+        Boolean.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: LatticePolytope_PPL((-1,-1),(0,1),(1,0)).has_IP_property()
-+            True
-+            sage: LatticePolytope_PPL((-1,-1),(1,1)).has_IP_property()
-+            False
-+        """
-+        origin = C_Polyhedron(point(0*Variable(self.space_dimension())))
-+        is_included = Poly_Con_Relation.is_included()
-+        saturates = Poly_Con_Relation.saturates()
-+        for c in self.constraints():
-+            rel = origin.relation_with(c)
-+            if (not rel.implies(is_included)) or rel.implies(saturates):
-+                return False
-+        return True
-+
-+    @cached_method
-+    def restricted_automorphism_group(self, vertex_labels=None):
-+        r"""
-+        Return the restricted automorphism group.
-+
-+        First, let the linear automorphism group be the subgroup of
-+        the Euclidean group `E(d) = GL(d,\RR) \ltimes \RR^d`
-+        preserving the `d`-dimensional polyhedron. The Euclidean group
-+        acts in the usual way `\vec{x}\mapsto A\vec{x}+b` on the
-+        ambient space. The restricted automorphism group is the
-+        subgroup of the linear automorphism group generated by
-+        permutations of vertices. If the polytope is full-dimensional,
-+        it is equal to the full (unrestricted) automorphism group.
-+
-+        INPUT:
-+
-+        - ``vertex_labels`` -- a tuple or ``None`` (default). The
-+          labels of the vertices that will be used in the output
-+          permutation group. By default, the vertices are used
-+          themselves.
-+
-+        OUTPUT:
-+
-+        A
-+        :class:`PermutationGroup<sage.groups.perm_gps.permgroup.PermutationGroup_generic>`
-+        acting on the vertices (or the ``vertex_labels``, if
-+        specified).
-+
-+        REFERENCES:
-+
-+        ..  [BSS]
-+            David Bremner, Mathieu Dutour Sikiric, Achill Schuermann:
-+            Polyhedral representation conversion up to symmetries.
-+            http://arxiv.org/abs/math/0702239
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: Z3square = LatticePolytope_PPL((0,0), (1,2), (2,1), (3,3))
-+            sage: Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4))
-+            Permutation Group with generators [(2,3), (1,2)(3,4), (1,4)]
-+            sage: G = Z3square.restricted_automorphism_group(); G
-+            Permutation Group with generators [((1,2),(2,1)),
-+            ((0,0),(1,2))((2,1),(3,3)), ((0,0),(3,3))]
-+            sage: tuple(G.domain()) == Z3square.vertices()
-+            True
-+            sage: G.orbit(Z3square.vertices()[0])
-+            ((0, 0), (1, 2), (3, 3), (2, 1))
-+
-+            sage: cell24 = LatticePolytope_PPL(
-+            ...   (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,-1,-1,1),(0,0,-1,1),
-+            ...   (0,-1,0,1),(-1,0,0,1),(1,0,0,-1),(0,1,0,-1),(0,0,1,-1),(-1,1,1,-1),
-+            ...   (1,-1,-1,0),(0,0,-1,0),(0,-1,0,0),(-1,0,0,0),(1,-1,0,0),(1,0,-1,0),
-+            ...   (0,1,1,-1),(-1,1,1,0),(-1,1,0,0),(-1,0,1,0),(0,-1,-1,1),(0,0,0,-1))
-+            sage: cell24.restricted_automorphism_group().cardinality()
-+            1152
-+        """
-+        if not self.is_full_dimensional():
-+            return self.affine_lattice_polytope().\
-+                restricted_automorphism_group(vertex_labels=vertex_labels)
-+        if vertex_labels is None:
-+            vertex_labels = self.vertices()
-+        from sage.groups.perm_gps.permgroup import PermutationGroup
-+        from sage.graphs.graph import Graph
-+        # good coordinates for the vertices
-+        v_list = []
-+        for v in self.minimized_generators():
-+            assert v.divisor().is_one()
-+            v_coords = (1,) + v.coefficients()
-+            v_list.append(vector(v_coords))
-+
-+        # Finally, construct the graph
-+        Qinv = sum( v.column() * v.row() for v in v_list ).inverse()
-+        G = Graph()
-+        for i in range(0,len(v_list)):
-+            for j in range(i+1,len(v_list)):
-+                v_i = v_list[i]
-+                v_j = v_list[j]
-+                G.add_edge(vertex_labels[i], vertex_labels[j], v_i * Qinv * v_j)
-+        return G.automorphism_group(edge_labels=True)
-+
-+    @cached_method
-+    def lattice_automorphism_group(self, points=None, point_labels=None):
-+        """
-+        The integral subgroup of the restricted automorphism group.
-+
-+        INPUT:
-+
-+        - ``points`` -- A tuple of coordinate vectors or ``None``
-+          (default). If specified, the points must form complete
-+          orbits under the lattice automorphism group. If ``None`` all
-+          vertices are used.
-+
-+        - ``point_labels`` -- A tuple of labels for the ``points`` or
-+          ``None`` (default). These will be used as labels for the do
-+          permutation group. If ``None`` the ``points`` will be used
-+          themselves.
-+
-+        OUTPUT:
-+
-+        The integral subgroup of the restricted automorphism group
-+        acting on the given ``points``, or all vertices if not
-+        specified.
-+
-+        EXAMPLES::
-+
-+            sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
-+            sage: Z3square = LatticePolytope_PPL((0,0), (1,2), (2,1), (3,3))
-+            sage: Z3square.lattice_automorphism_group()
-+            Permutation Group with generators [(), ((1,2),(2,1)),
-+            ((0,0),(3,3)), ((0,0),(3,3))((1,2),(2,1))]
-+
-+            sage: G1 = Z3square.lattice_automorphism_group(point_labels=(1,2,3,4));  G1
-+            Permutation Group with generators [(), (2,3), (1,4), (1,4)(2,3)]
-+            sage: G1.cardinality()
-+            4
-+
-+            sage: G2 = Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4)); G2
-+            Permutation Group with generators [(2,3), (1,2)(3,4), (1,4)]
-+            sage: G2.cardinality()
-+            8
-+
-+            sage: points = Z3square.integral_points();  points
-+            ((0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3))
-+            sage: Z3square.lattice_automorphism_group(points, point_labels=(1,2,3,4,5,6))
-+            Permutation Group with generators [(), (3,4), (1,6)(2,5), (1,6)(2,5)(3,4)]
-+        """
-+        if not self.is_full_dimensional():
-+            return self.affine_lattice_polytope().lattice_automorphism_group()
-+
-+        if points is None:
-+            points = self.vertices()
-+        if point_labels is None:
-+            point_labels = tuple(points)
-+        points = [ vector(ZZ, [1]+v.list()) for v in points ]
-+        map(lambda x:x.set_immutable(), points)
-+        
-+        vertices = [ vector(ZZ, [1]+v.list()) for v in self.vertices() ]
-+        pivots = matrix(ZZ, vertices).pivot_rows()
-+        basis = matrix(ZZ, [ vertices[i] for i in pivots ])
-+        Mat_ZZ = basis.parent()
-+        basis_inverse = basis.inverse()
-+
-+        from sage.groups.perm_gps.permgroup import PermutationGroup
-+        from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
-+        lattice_gens = []
-+        G = self.restricted_automorphism_group(
-+            vertex_labels=tuple(range(len(vertices))))
-+        for g in G:
-+            image = matrix(ZZ, [ vertices[g(i)] for i in pivots ])
-+            m = basis_inverse*image
-+            if m not in Mat_ZZ:
-+                continue
-+            perm_list = [ point_labels[points.index(p*m)] 
-+                          for p in points ]
-+            lattice_gens.append(perm_list)
-+        return PermutationGroup(lattice_gens, domain=point_labels)
-+
-+
-+
-+
-diff --git a/sage/libs/ppl.pyx b/sage/libs/ppl.pyx