CoCalc -- backend

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/geometry/polyhedron/backend_ppl.py
⁸⁸¹⁷ views
1
"""
2
The PPL (Parma Polyhedra Library) backend for polyhedral computations
3
"""
4

5
from sage.rings.all import ZZ, QQ
6
from sage.rings.integer import LCM_list
7
from sage.misc.functional import denominator
8
from sage.matrix.constructor import matrix
9
from sage.libs.ppl import (
10
    C_Polyhedron, Constraint_System, Generator_System,
11
    Variable, Linear_Expression,
12
    line, ray, point )
13

14
from base import Polyhedron_base
15
from base_QQ import Polyhedron_QQ
16
from base_ZZ import Polyhedron_ZZ
17

18

19
#########################################################################
20
class Polyhedron_ppl(Polyhedron_base):
21
    """
22
    Polyhedra with ppl
23

24
    INPUT:
25

26
    - ``Vrep`` -- a list ``[vertices, rays, lines]`` or ``None``.
27

28
    - ``Hrep`` -- a list ``[ieqs, eqns]`` or ``None``.
29

30
    EXAMPLES::
31

32
        sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], rays=[(1,1)], lines=[], backend='ppl')
33
        sage: TestSuite(p).run()
34
    """
35

36
    def _init_from_Vrepresentation(self, vertices, rays, lines, minimize=True, verbose=False):
37
        """
38
        Construct polyhedron from V-representation data.
39

40
        INPUT:
41

42
        - ``vertices`` -- list of point. Each point can be specified
43
           as any iterable container of
44
           :meth:`~sage.geometry.polyhedron.base.base_ring` elements.
45

46
        - ``rays`` -- list of rays. Each ray can be specified as any
47
          iterable container of
48
          :meth:`~sage.geometry.polyhedron.base.base_ring` elements.
49

50
        - ``lines`` -- list of lines. Each line can be specified as
51
          any iterable container of
52
          :meth:`~sage.geometry.polyhedron.base.base_ring` elements.
53

54
        - ``verbose`` -- boolean (default: ``False``). Whether to print
55
          verbose output for debugging purposes.
56

57
        EXAMPLES::
58

59
            sage: p = Polyhedron(backend='ppl')
60
            sage: from sage.geometry.polyhedron.backend_ppl import Polyhedron_ppl
61
            sage: Polyhedron_ppl._init_from_Vrepresentation(p, [], [], [])
62
        """
63
        gs = Generator_System()
64
        if vertices is None: vertices = []
65
        for v in vertices:
66
            d = LCM_list([denominator(v_i) for v_i in v])
67
            if d.is_one():
68
                gs.insert(point(Linear_Expression(v, 0)))
69
            else:
70
                dv = [ d*v_i for v_i in v ]
71
                gs.insert(point(Linear_Expression(dv, 0), d))
72
        if rays is None: rays = []
73
        for r in rays:
74
            d = LCM_list([denominator(r_i) for r_i in r])
75
            if d.is_one():
76
                gs.insert(ray(Linear_Expression(r, 0)))
77
            else:
78
                dr = [ d*r_i for r_i in r ]
79
                gs.insert(ray(Linear_Expression(dr, 0)))
80
        if lines is None: lines = []
81
        for l in lines:
82
            d = LCM_list([denominator(l_i) for l_i in l])
83
            if d.is_one():
84
                gs.insert(line(Linear_Expression(l, 0)))
85
            else:
86
                dl = [ d*l_i for l_i in l ]
87
                gs.insert(line(Linear_Expression(dl, 0)))
88
        if gs.empty():
89
            self._ppl_polyhedron = C_Polyhedron(self.ambient_dim(), 'empty')
90
        else:
91
            self._ppl_polyhedron = C_Polyhedron(gs)
92
        self._init_Vrepresentation_from_ppl(minimize)
93
        self._init_Hrepresentation_from_ppl(minimize)
94

95
    def _init_from_Hrepresentation(self, ieqs, eqns, minimize=True, verbose=False):
96
        """
97
        Construct polyhedron from H-representation data.
98

99
        INPUT:
100

101
        - ``ieqs`` -- list of inequalities. Each line can be specified
102
          as any iterable container of
103
          :meth:`~sage.geometry.polyhedron.base.base_ring` elements.
104

105
        - ``eqns`` -- list of equalities. Each line can be specified
106
          as any iterable container of
107
          :meth:`~sage.geometry.polyhedron.base.base_ring` elements.
108

109
        - ``verbose`` -- boolean (default: ``False``). Whether to print
110
          verbose output for debugging purposes.
111

112
        EXAMPLES::
113

114
            sage: p = Polyhedron(backend='ppl')
115
            sage: from sage.geometry.polyhedron.backend_ppl import Polyhedron_ppl
116
            sage: Polyhedron_ppl._init_from_Hrepresentation(p, [], [])
117
        """
118
        cs = Constraint_System()
119
        if ieqs is None: ieqs = []
120
        for ieq in ieqs:
121
            d = LCM_list([denominator(ieq_i) for ieq_i in ieq])
122
            dieq = [ ZZ(d*ieq_i) for ieq_i in ieq ]
123
            b = dieq[0]
124
            A = dieq[1:]
125
            cs.insert(Linear_Expression(A, b) >= 0)
126
        if eqns is None: eqns = []
127
        for eqn in eqns:
128
            d = LCM_list([denominator(eqn_i) for eqn_i in eqn])
129
            deqn = [ ZZ(d*eqn_i) for eqn_i in eqn ]
130
            b = deqn[0]
131
            A = deqn[1:]
132
            cs.insert(Linear_Expression(A, b) == 0)
133
        if cs.empty():
134
            self._ppl_polyhedron = C_Polyhedron(self.ambient_dim(), 'universe')
135
        else:
136
            self._ppl_polyhedron = C_Polyhedron(cs)
137
        self._init_Vrepresentation_from_ppl(minimize)
138
        self._init_Hrepresentation_from_ppl(minimize)
139

140
    def _init_Vrepresentation_from_ppl(self, minimize):
141
        """
142
        Create the Vrepresentation objects from the ppl polyhedron.
143

144
        EXAMPLES::
145

146
            sage: p = Polyhedron(vertices=[(0,1/2),(2,0),(4,5/6)],
147
            ...                  backend='ppl')  # indirect doctest
148
            sage: p.Hrepresentation()
149
            (An inequality (1, 4) x - 2 >= 0,
150
             An inequality (1, -12) x + 6 >= 0,
151
             An inequality (-5, 12) x + 10 >= 0)
152
            sage: p._ppl_polyhedron.minimized_constraints()
153
            Constraint_System {x0+4*x1-2>=0, x0-12*x1+6>=0, -5*x0+12*x1+10>=0}
154
            sage: p.Vrepresentation()
155
            (A vertex at (0, 1/2), A vertex at (2, 0), A vertex at (4, 5/6))
156
            sage: p._ppl_polyhedron.minimized_generators()
157
            Generator_System {point(0/2, 1/2), point(2/1, 0/1), point(24/6, 5/6)}
158
        """
159
        self._Vrepresentation = []
160
        gs = self._ppl_polyhedron.minimized_generators()
161
        parent = self.parent()
162
        for g in gs:
163
            if g.is_point():
164
                d = g.divisor()
165
                if d.is_one():
166
                    parent._make_Vertex(self, g.coefficients())
167
                else:
168
                    parent._make_Vertex(self, [x/d for x in g.coefficients()])
169
            elif g.is_ray():
170
                parent._make_Ray(self, g.coefficients())
171
            elif g.is_line():
172
                parent._make_Line(self, g.coefficients())
173
            else:
174
                assert False
175
        self._Vrepresentation = tuple(self._Vrepresentation)
176

177
    def _init_Hrepresentation_from_ppl(self, minimize):
178
        """
179
        Create the Hrepresentation objects from the ppl polyhedron.
180

181
        EXAMPLES::
182

183
            sage: p = Polyhedron(vertices=[(0,1/2),(2,0),(4,5/6)],
184
            ...                  backend='ppl')  # indirect doctest
185
            sage: p.Hrepresentation()
186
            (An inequality (1, 4) x - 2 >= 0,
187
             An inequality (1, -12) x + 6 >= 0,
188
             An inequality (-5, 12) x + 10 >= 0)
189
            sage: p._ppl_polyhedron.minimized_constraints()
190
            Constraint_System {x0+4*x1-2>=0, x0-12*x1+6>=0, -5*x0+12*x1+10>=0}
191
            sage: p.Vrepresentation()
192
            (A vertex at (0, 1/2), A vertex at (2, 0), A vertex at (4, 5/6))
193
            sage: p._ppl_polyhedron.minimized_generators()
194
            Generator_System {point(0/2, 1/2), point(2/1, 0/1), point(24/6, 5/6)}
195
        """
196
        self._Hrepresentation = []
197
        cs = self._ppl_polyhedron.minimized_constraints()
198
        parent = self.parent()
199
        for c in cs:
200
            if c.is_inequality():
201
                parent._make_Inequality(self, (c.inhomogeneous_term(),) + c.coefficients())
202
            elif c.is_equality():
203
                parent._make_Equation(self, (c.inhomogeneous_term(),) + c.coefficients())
204
        self._Hrepresentation = tuple(self._Hrepresentation)
205

206
    def _init_empty_polyhedron(self):
207
        """
208
        Initializes an empty polyhedron.
209

210
        TESTS::
211

212
            sage: empty = Polyhedron(backend='ppl'); empty
213
            The empty polyhedron in ZZ^0
214
            sage: empty.Vrepresentation()
215
            ()
216
            sage: empty.Hrepresentation()
217
            (An equation -1 == 0,)
218
            sage: Polyhedron(vertices = [], backend='ppl')
219
            The empty polyhedron in ZZ^0
220
            sage: Polyhedron(backend='ppl')._init_empty_polyhedron()
221
        """
222
        super(Polyhedron_ppl, self)._init_empty_polyhedron()
223
        self._ppl_polyhedron = C_Polyhedron(self.ambient_dim(), 'empty')
224

225

226

227

228
#########################################################################
229
class Polyhedron_QQ_ppl(Polyhedron_ppl, Polyhedron_QQ):
230
    """
231
    Polyhedra over `\QQ` with ppl
232

233
    INPUT:
234

235
    - ``Vrep`` -- a list ``[vertices, rays, lines]`` or ``None``.
236

237
    - ``Hrep`` -- a list ``[ieqs, eqns]`` or ``None``.
238

239
    EXAMPLES::
240

241
        sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], rays=[(1,1)], lines=[],
242
        ...                  backend='ppl', base_ring=QQ)
243
        sage: TestSuite(p).run(skip='_test_pickling')
244
    """
245
    pass
246

247

248
#########################################################################
249
class Polyhedron_ZZ_ppl(Polyhedron_ppl, Polyhedron_ZZ):
250
    """
251
    Polyhedra over `\ZZ` with ppl
252

253
    INPUT:
254

255
    - ``Vrep`` -- a list ``[vertices, rays, lines]`` or ``None``.
256

257
    - ``Hrep`` -- a list ``[ieqs, eqns]`` or ``None``.
258

259
    EXAMPLES::
260

261
        sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], rays=[(1,1)], lines=[])
262
        ...                  backend='ppl', base_ring=ZZ)
263
        sage: TestSuite(p).run(skip='_test_pickling')
264
    """
265
    pass
266

267
Product

Resources

Company
