X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/6a8f0d937524e9210b3283f8331ccaf6ce3caaa3..7b93cea1daf2889e9ee10ca9c22a1b5124404937:/pypol/polyhedra.py diff --git a/pypol/polyhedra.py b/pypol/polyhedra.py deleted file mode 100644 index 5d9c287..0000000 --- a/pypol/polyhedra.py +++ /dev/null @@ -1,328 +0,0 @@ -import functools -import math -import numbers - -from . import islhelper - -from .islhelper import mainctx, libisl -from .geometry import GeometricObject, Point -from .linexprs import Expression, Symbol, Rational -from .domains import Domain - - -__all__ = [ - 'Polyhedron', - 'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt', - 'Empty', 'Universe', -] - - -class Polyhedron(Domain): - - __slots__ = ( - '_equalities', - '_inequalities', - '_constraints', - '_symbols', - '_dimension', - ) - - def __new__(cls, equalities=None, inequalities=None): - if isinstance(equalities, str): - if inequalities is not None: - raise TypeError('too many arguments') - return cls.fromstring(equalities) - elif isinstance(equalities, GeometricObject): - if inequalities is not None: - raise TypeError('too many arguments') - return equalities.aspolyhedron() - if equalities is None: - equalities = [] - else: - for i, equality in enumerate(equalities): - if not isinstance(equality, Expression): - raise TypeError('equalities must be linear expressions') - equalities[i] = equality.scaleint() - if inequalities is None: - inequalities = [] - else: - for i, inequality in enumerate(inequalities): - if not isinstance(inequality, Expression): - raise TypeError('inequalities must be linear expressions') - inequalities[i] = inequality.scaleint() - symbols = cls._xsymbols(equalities + inequalities) - islbset = cls._toislbasicset(equalities, inequalities, symbols) - return cls._fromislbasicset(islbset, symbols) - - @property - def equalities(self): - return self._equalities - - @property - def inequalities(self): - return self._inequalities - - @property - def constraints(self): - return self._constraints - - @property - def polyhedra(self): - return self, - - def disjoint(self): - return self - - def isuniverse(self): - islbset = self._toislbasicset(self.equalities, self.inequalities, - self.symbols) - universe = bool(libisl.isl_basic_set_is_universe(islbset)) - libisl.isl_basic_set_free(islbset) - return universe - - def aspolyhedron(self): - return self - - def __contains__(self, point): - if not isinstance(point, Point): - raise TypeError('point must be a Point instance') - if self.symbols != point.symbols: - raise ValueError('arguments must belong to the same space') - for equality in self.equalities: - if equality.subs(point.coordinates()) != 0: - return False - for inequality in self.inequalities: - if inequality.subs(point.coordinates()) < 0: - return False - return True - - def subs(self, symbol, expression=None): - equalities = [equality.subs(symbol, expression) - for equality in self.equalities] - inequalities = [inequality.subs(symbol, expression) - for inequality in self.inequalities] - return Polyhedron(equalities, inequalities) - - @classmethod - def _fromislbasicset(cls, islbset, symbols): - islconstraints = islhelper.isl_basic_set_constraints(islbset) - equalities = [] - inequalities = [] - for islconstraint in islconstraints: - constant = libisl.isl_constraint_get_constant_val(islconstraint) - constant = islhelper.isl_val_to_int(constant) - coefficients = {} - for index, symbol in enumerate(symbols): - coefficient = libisl.isl_constraint_get_coefficient_val(islconstraint, - libisl.isl_dim_set, index) - coefficient = islhelper.isl_val_to_int(coefficient) - if coefficient != 0: - coefficients[symbol] = coefficient - expression = Expression(coefficients, constant) - if libisl.isl_constraint_is_equality(islconstraint): - equalities.append(expression) - else: - inequalities.append(expression) - libisl.isl_basic_set_free(islbset) - self = object().__new__(Polyhedron) - self._equalities = tuple(equalities) - self._inequalities = tuple(inequalities) - self._constraints = tuple(equalities + inequalities) - self._symbols = cls._xsymbols(self._constraints) - self._dimension = len(self._symbols) - return self - - @classmethod - def _toislbasicset(cls, equalities, inequalities, symbols): - dimension = len(symbols) - indices = {symbol: index for index, symbol in enumerate(symbols)} - islsp = libisl.isl_space_set_alloc(mainctx, 0, dimension) - islbset = libisl.isl_basic_set_universe(libisl.isl_space_copy(islsp)) - islls = libisl.isl_local_space_from_space(islsp) - for equality in equalities: - isleq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(islls)) - for symbol, coefficient in equality.coefficients(): - islval = str(coefficient).encode() - islval = libisl.isl_val_read_from_str(mainctx, islval) - index = indices[symbol] - isleq = libisl.isl_constraint_set_coefficient_val(isleq, - libisl.isl_dim_set, index, islval) - if equality.constant != 0: - islval = str(equality.constant).encode() - islval = libisl.isl_val_read_from_str(mainctx, islval) - isleq = libisl.isl_constraint_set_constant_val(isleq, islval) - islbset = libisl.isl_basic_set_add_constraint(islbset, isleq) - for inequality in inequalities: - islin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(islls)) - for symbol, coefficient in inequality.coefficients(): - islval = str(coefficient).encode() - islval = libisl.isl_val_read_from_str(mainctx, islval) - index = indices[symbol] - islin = libisl.isl_constraint_set_coefficient_val(islin, - libisl.isl_dim_set, index, islval) - if inequality.constant != 0: - islval = str(inequality.constant).encode() - islval = libisl.isl_val_read_from_str(mainctx, islval) - islin = libisl.isl_constraint_set_constant_val(islin, islval) - islbset = libisl.isl_basic_set_add_constraint(islbset, islin) - return islbset - - @classmethod - def fromstring(cls, string): - domain = Domain.fromstring(string) - if not isinstance(domain, Polyhedron): - raise ValueError('non-polyhedral expression: {!r}'.format(string)) - return domain - - def __repr__(self): - if self.isempty(): - return 'Empty' - elif self.isuniverse(): - return 'Universe' - else: - strings = [] - for equality in self.equalities: - strings.append('0 == {}'.format(equality)) - for inequality in self.inequalities: - strings.append('0 <= {}'.format(inequality)) - if len(strings) == 1: - return strings[0] - else: - return 'And({})'.format(', '.join(strings)) - - @classmethod - def fromsympy(cls, expr): - domain = Domain.fromsympy(expr) - if not isinstance(domain, Polyhedron): - raise ValueError('non-polyhedral expression: {!r}'.format(expr)) - return domain - - def tosympy(self): - import sympy - constraints = [] - for equality in self.equalities: - constraints.append(sympy.Eq(equality.tosympy(), 0)) - for inequality in self.inequalities: - constraints.append(sympy.Ge(inequality.tosympy(), 0)) - return sympy.And(*constraints) - - @classmethod - def _sort_polygon_2d(cls, points): - if len(points) <= 3: - return points - o = sum((Vector(point) for point in points)) / len(points) - o = Point(o.coordinates()) - angles = {} - for m in points: - om = Vector(o, m) - dx, dy = (coordinate for symbol, coordinates in om.coordinates()) - angle = math.atan2(dy, dx) - angles[m] = angle - return sorted(points, key=angles.get) - - @classmethod - def _sort_polygon_3d(cls, points): - if len(points) <= 3: - return points - o = sum((Vector(point) for point in points)) / len(points) - o = Point(o.coordinates()) - a, b = points[:2] - oa = Vector(o, a) - ob = Vector(o, b) - norm_oa = oa.norm() - u = (oa.cross(ob)).asunit() - angles = {a: 0.} - for m in points[1:]: - om = Vector(o, m) - normprod = norm_oa * om.norm() - cosinus = oa.dot(om) / normprod - sinus = u.dot(oa.cross(om)) / normprod - angle = math.acos(cosinus) - angle = math.copysign(angle, sinus) - angles[m] = angle - return sorted(points, key=angles.get) - - def plot(self): - import matplotlib.pyplot as plt - from matplotlib.path import Path - import matplotlib.patches as patches - - if len(self.symbols)> 3: - raise TypeError - - elif len(self.symbols) == 2: - verts = self.vertices() - points = [] - codes = [Path.MOVETO] - for vert in verts: - pairs = () - for sym in sorted(vert, key=Symbol.sortkey): - num = vert.get(sym) - pairs = pairs + (num,) - points.append(pairs) - points.append((0.0, 0.0)) - num = len(points) - while num > 2: - codes.append(Path.LINETO) - num = num - 1 - else: - codes.append(Path.CLOSEPOLY) - path = Path(points, codes) - fig = plt.figure() - ax = fig.add_subplot(111) - patch = patches.PathPatch(path, facecolor='blue', lw=2) - ax.add_patch(patch) - ax.set_xlim(-5,5) - ax.set_ylim(-5,5) - plt.show() - - elif len(self.symbols)==3: - return 0 - - return points - - -def _polymorphic(func): - @functools.wraps(func) - def wrapper(left, right): - if isinstance(left, numbers.Rational): - left = Rational(left) - elif not isinstance(left, Expression): - raise TypeError('left must be a a rational number ' - 'or a linear expression') - if isinstance(right, numbers.Rational): - right = Rational(right) - elif not isinstance(right, Expression): - raise TypeError('right must be a a rational number ' - 'or a linear expression') - return func(left, right) - return wrapper - -@_polymorphic -def Lt(left, right): - return Polyhedron([], [right - left - 1]) - -@_polymorphic -def Le(left, right): - return Polyhedron([], [right - left]) - -@_polymorphic -def Eq(left, right): - return Polyhedron([left - right], []) - -@_polymorphic -def Ne(left, right): - return ~Eq(left, right) - -@_polymorphic -def Gt(left, right): - return Polyhedron([], [left - right - 1]) - -@_polymorphic -def Ge(left, right): - return Polyhedron([], [left - right]) - - -Empty = Eq(1, 0) - -Universe = Polyhedron([])