pypol/polyhedra.py

   1 import functools
   2 import math
   3 import numbers
   4
   5 from . import islhelper
   6
   7 from .islhelper import mainctx, libisl
   8 from .geometry import GeometricObject
   9 from .coordinates import Point
  10 from .linexprs import Expression, Symbol, Rational
  11 from .domains import Domain
  12
  13
  14 __all__ = [
  15     'Polyhedron',
  16     'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt',
  17     'Empty', 'Universe',
  18 ]
  19
  20
  21 class Polyhedron(Domain):
  22
  23     __slots__ = (
  24         '_equalities',
  25         '_inequalities',
  26         '_constraints',
  27         '_symbols',
  28         '_dimension',
  29     )
  30
  31     def __new__(cls, equalities=None, inequalities=None):
  32         if isinstance(equalities, str):
  33             if inequalities is not None:
  34                 raise TypeError('too many arguments')
  35             return cls.fromstring(equalities)
  36         elif isinstance(equalities, GeometricObject):
  37             if inequalities is not None:
  38                 raise TypeError('too many arguments')
  39             return equalities.aspolyhedron()
  40         if equalities is None:
  41             equalities = []
  42         else:
  43             for i, equality in enumerate(equalities):
  44                 if not isinstance(equality, Expression):
  45                     raise TypeError('equalities must be linear expressions')
  46                 equalities[i] = equality.scaleint()
  47         if inequalities is None:
  48             inequalities = []
  49         else:
  50             for i, inequality in enumerate(inequalities):
  51                 if not isinstance(inequality, Expression):
  52                     raise TypeError('inequalities must be linear expressions')
  53                 inequalities[i] = inequality.scaleint()
  54         symbols = cls._xsymbols(equalities + inequalities)
  55         islbset = cls._toislbasicset(equalities, inequalities, symbols)
  56         return cls._fromislbasicset(islbset, symbols)
  57
  58     @property
  59     def equalities(self):
  60         return self._equalities
  61
  62     @property
  63     def inequalities(self):
  64         return self._inequalities
  65
  66     @property
  67     def constraints(self):
  68         return self._constraints
  69
  70     @property
  71     def polyhedra(self):
  72         return self,
  73
  74     def disjoint(self):
  75         return self
  76
  77     def isuniverse(self):
  78         islbset = self._toislbasicset(self.equalities, self.inequalities,
  79             self.symbols)
  80         universe = bool(libisl.isl_basic_set_is_universe(islbset))
  81         libisl.isl_basic_set_free(islbset)
  82         return universe
  83
  84     def aspolyhedron(self):
  85         return self
  86
  87     def __contains__(self, point):
  88         if not isinstance(point, Point):
  89             raise TypeError('point must be a Point instance')
  90         if self.symbols != point.symbols:
  91             raise ValueError('arguments must belong to the same space')
  92         for equality in self.equalities:
  93             if equality.subs(point.coordinates()) != 0:
  94                 return False
  95         for inequality in self.inequalities:
  96             if inequality.subs(point.coordinates()) < 0:
  97                 return False
  98         return True
  99
 100     def subs(self, symbol, expression=None):
 101         equalities = [equality.subs(symbol, expression)
 102             for equality in self.equalities]
 103         inequalities = [inequality.subs(symbol, expression)
 104             for inequality in self.inequalities]
 105         return Polyhedron(equalities, inequalities)
 106
 107     @classmethod
 108     def _fromislbasicset(cls, islbset, symbols):
 109         islconstraints = islhelper.isl_basic_set_constraints(islbset)
 110         equalities = []
 111         inequalities = []
 112         for islconstraint in islconstraints:
 113             constant = libisl.isl_constraint_get_constant_val(islconstraint)
 114             constant = islhelper.isl_val_to_int(constant)
 115             coefficients = {}
 116             for index, symbol in enumerate(symbols):
 117                 coefficient = libisl.isl_constraint_get_coefficient_val(islconstraint,
 118                     libisl.isl_dim_set, index)
 119                 coefficient = islhelper.isl_val_to_int(coefficient)
 120                 if coefficient != 0:
 121                     coefficients[symbol] = coefficient
 122             expression = Expression(coefficients, constant)
 123             if libisl.isl_constraint_is_equality(islconstraint):
 124                 equalities.append(expression)
 125             else:
 126                 inequalities.append(expression)
 127         libisl.isl_basic_set_free(islbset)
 128         self = object().__new__(Polyhedron)
 129         self._equalities = tuple(equalities)
 130         self._inequalities = tuple(inequalities)
 131         self._constraints = tuple(equalities + inequalities)
 132         self._symbols = cls._xsymbols(self._constraints)
 133         self._dimension = len(self._symbols)
 134         return self
 135
 136     @classmethod
 137     def _toislbasicset(cls, equalities, inequalities, symbols):
 138         dimension = len(symbols)
 139         indices = {symbol: index for index, symbol in enumerate(symbols)}
 140         islsp = libisl.isl_space_set_alloc(mainctx, 0, dimension)
 141         islbset = libisl.isl_basic_set_universe(libisl.isl_space_copy(islsp))
 142         islls = libisl.isl_local_space_from_space(islsp)
 143         for equality in equalities:
 144             isleq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(islls))
 145             for symbol, coefficient in equality.coefficients():
 146                 islval = str(coefficient).encode()
 147                 islval = libisl.isl_val_read_from_str(mainctx, islval)
 148                 index = indices[symbol]
 149                 isleq = libisl.isl_constraint_set_coefficient_val(isleq,
 150                     libisl.isl_dim_set, index, islval)
 151             if equality.constant != 0:
 152                 islval = str(equality.constant).encode()
 153                 islval = libisl.isl_val_read_from_str(mainctx, islval)
 154                 isleq = libisl.isl_constraint_set_constant_val(isleq, islval)
 155             islbset = libisl.isl_basic_set_add_constraint(islbset, isleq)
 156         for inequality in inequalities:
 157             islin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(islls))
 158             for symbol, coefficient in inequality.coefficients():
 159                 islval = str(coefficient).encode()
 160                 islval = libisl.isl_val_read_from_str(mainctx, islval)
 161                 index = indices[symbol]
 162                 islin = libisl.isl_constraint_set_coefficient_val(islin,
 163                     libisl.isl_dim_set, index, islval)
 164             if inequality.constant != 0:
 165                 islval = str(inequality.constant).encode()
 166                 islval = libisl.isl_val_read_from_str(mainctx, islval)
 167                 islin = libisl.isl_constraint_set_constant_val(islin, islval)
 168             islbset = libisl.isl_basic_set_add_constraint(islbset, islin)
 169         return islbset
 170
 171     @classmethod
 172     def fromstring(cls, string):
 173         domain = Domain.fromstring(string)
 174         if not isinstance(domain, Polyhedron):
 175             raise ValueError('non-polyhedral expression: {!r}'.format(string))
 176         return domain
 177
 178     def __repr__(self):
 179         if self.isempty():
 180             return 'Empty'
 181         elif self.isuniverse():
 182             return 'Universe'
 183         else:
 184             strings = []
 185             for equality in self.equalities:
 186                 strings.append('0 == {}'.format(equality))
 187             for inequality in self.inequalities:
 188                 strings.append('0 <= {}'.format(inequality))
 189             if len(strings) == 1:
 190                 return strings[0]
 191             else:
 192                 return 'And({})'.format(', '.join(strings))
 193
 194     @classmethod
 195     def fromsympy(cls, expr):
 196         domain = Domain.fromsympy(expr)
 197         if not isinstance(domain, Polyhedron):
 198             raise ValueError('non-polyhedral expression: {!r}'.format(expr))
 199         return domain
 200
 201     def tosympy(self):
 202         import sympy
 203         constraints = []
 204         for equality in self.equalities:
 205             constraints.append(sympy.Eq(equality.tosympy(), 0))
 206         for inequality in self.inequalities:
 207             constraints.append(sympy.Ge(inequality.tosympy(), 0))
 208         return sympy.And(*constraints)
 209
 210     @classmethod
 211     def _sort_polygon_2d(cls, points):
 212         if len(points) <= 3:
 213             return points
 214         o = sum((Vector(point) for point in points)) / len(points)
 215         o = Point(o.coordinates())
 216         angles = {}
 217         for m in points:
 218             om = Vector(o, m)
 219             dx, dy = (coordinate for symbol, coordinates in om.coordinates())
 220             angle = math.atan2(dy, dx)
 221             angles[m] = angle
 222         return sorted(points, key=angles.get)
 223
 224     @classmethod
 225     def _sort_polygon_3d(cls, points):
 226         if len(points) <= 3:
 227             return points
 228         o = sum((Vector(point) for point in points)) / len(points)
 229         o = Point(o.coordinates())
 230         a, b = points[:2]
 231         oa = Vector(o, a)
 232         ob = Vector(o, b)
 233         norm_oa = oa.norm()
 234         u = (oa.cross(ob)).asunit()
 235         angles = {a: 0.}
 236         for m in points[1:]:
 237             om = Vector(o, m)
 238             normprod = norm_oa * om.norm()
 239             cosinus = oa.dot(om) / normprod
 240             sinus = u.dot(oa.cross(om)) / normprod
 241             angle = math.acos(cosinus)
 242             angle = math.copysign(angle, sinus)
 243             angles[m] = angle
 244         return sorted(points, key=angles.get)
 245
 246     def plot(self):
 247         import matplotlib.pyplot as plt
 248         from matplotlib.path import Path
 249         import matplotlib.patches as patches
 250
 251         if len(self.symbols)> 3:
 252             raise TypeError
 253
 254         elif len(self.symbols) == 2:
 255             verts = self.vertices()
 256             points = []
 257             codes = [Path.MOVETO]
 258             for vert in verts:
 259                 pairs = ()
 260                 for sym in sorted(vert, key=Symbol.sortkey):
 261                     num = vert.get(sym)
 262                     pairs = pairs + (num,)
 263                 points.append(pairs)
 264             points.append((0.0, 0.0))
 265             num = len(points)
 266             while num > 2:
 267                 codes.append(Path.LINETO)
 268                 num = num - 1
 269             else:
 270                 codes.append(Path.CLOSEPOLY)
 271             path = Path(points, codes)
 272             fig = plt.figure()
 273             ax = fig.add_subplot(111)
 274             patch = patches.PathPatch(path, facecolor='blue', lw=2)
 275             ax.add_patch(patch)
 276             ax.set_xlim(-5,5)
 277             ax.set_ylim(-5,5)
 278             plt.show()
 279
 280         elif len(self.symbols)==3:
 281             return 0
 282
 283         return points
 284
 285
 286 def _polymorphic(func):
 287     @functools.wraps(func)
 288     def wrapper(left, right):
 289         if isinstance(left, numbers.Rational):
 290             left = Rational(left)
 291         elif not isinstance(left, Expression):
 292             raise TypeError('left must be a a rational number '
 293                 'or a linear expression')
 294         if isinstance(right, numbers.Rational):
 295             right = Rational(right)
 296         elif not isinstance(right, Expression):
 297             raise TypeError('right must be a a rational number '
 298                 'or a linear expression')
 299         return func(left, right)
 300     return wrapper
 301
 302 @_polymorphic
 303 def Lt(left, right):
 304     return Polyhedron([], [right - left - 1])
 305
 306 @_polymorphic
 307 def Le(left, right):
 308     return Polyhedron([], [right - left])
 309
 310 @_polymorphic
 311 def Eq(left, right):
 312     return Polyhedron([left - right], [])
 313
 314 @_polymorphic
 315 def Ne(left, right):
 316     return ~Eq(left, right)
 317
 318 @_polymorphic
 319 def Gt(left, right):
 320     return Polyhedron([], [left - right - 1])
 321
 322 @_polymorphic
 323 def Ge(left, right):
 324     return Polyhedron([], [left - right])
 325
 326
 327 Empty = Eq(1, 0)
 328
 329 Universe = Polyhedron([])