X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/fd990941199581e977b4455345b55f841bbaa05a..7b93cea1daf2889e9ee10ca9c22a1b5124404937:/pypol/polyhedra.py diff --git a/pypol/polyhedra.py b/pypol/polyhedra.py deleted file mode 100644 index ac67cf8..0000000 --- a/pypol/polyhedra.py +++ /dev/null @@ -1,260 +0,0 @@ -import functools -import numbers - -from . import islhelper - -from .islhelper import mainctx, libisl -from .linexprs import Expression, Constant -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, Polyhedron): - if inequalities is not None: - raise TypeError('too many arguments') - return equalities - elif isinstance(equalities, Domain): - if inequalities is not None: - raise TypeError('too many arguments') - return equalities.polyhedral_hull() - 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._toint() - 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._toint() - 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 polyhedral_hull(self): - return self - - @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('Eq({}, 0)'.format(equality)) - for inequality in self.inequalities: - strings.append('Ge({}, 0)'.format(inequality)) - if len(strings) == 1: - return strings[0] - else: - return 'And({})'.format(', '.join(strings)) - - @classmethod - def _fromsympy(cls, expr): - import sympy - equalities = [] - inequalities = [] - if expr.func == sympy.And: - for arg in expr.args: - arg_eqs, arg_ins = cls._fromsympy(arg) - equalities.extend(arg_eqs) - inequalities.extend(arg_ins) - elif expr.func == sympy.Eq: - expr = Expression.fromsympy(expr.args[0] - expr.args[1]) - equalities.append(expr) - else: - if expr.func == sympy.Lt: - expr = Expression.fromsympy(expr.args[1] - expr.args[0] - 1) - elif expr.func == sympy.Le: - expr = Expression.fromsympy(expr.args[1] - expr.args[0]) - elif expr.func == sympy.Ge: - expr = Expression.fromsympy(expr.args[0] - expr.args[1]) - elif expr.func == sympy.Gt: - expr = Expression.fromsympy(expr.args[0] - expr.args[1] - 1) - else: - raise ValueError('non-polyhedral expression: {!r}'.format(expr)) - inequalities.append(expr) - return equalities, inequalities - - @classmethod - def fromsympy(cls, expr): - import sympy - equalities, inequalities = cls._fromsympy(expr) - return cls(equalities, inequalities) - - 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) - - -def _polymorphic(func): - @functools.wraps(func) - def wrapper(left, right): - if isinstance(left, numbers.Rational): - left = Constant(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 = Constant(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([])