X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/841943174bb4d3b602e8e055592d8b54d1bb086d..af10bce9dc286c2b3ffe6520c4ed0047a4475320:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 5b5d8aa..5f3c559 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,9 +1,12 @@ - +import ctypes, ctypes.util import functools import numbers from fractions import Fraction, gcd +from . import isl +from .isl import libisl + __all__ = [ 'Expression', @@ -14,6 +17,34 @@ __all__ = [ ] +def _polymorphic_method(func): + @functools.wraps(func) + def wrapper(a, b): + if isinstance(b, Expression): + return func(a, b) + if isinstance(b, numbers.Rational): + b = constant(b) + return func(a, b) + return NotImplemented + return wrapper + +def _polymorphic_operator(func): + # A polymorphic operator should call a polymorphic method, hence we just + # have to test the left operand. + @functools.wraps(func) + def wrapper(a, b): + if isinstance(a, numbers.Rational): + a = constant(a) + return func(a, b) + elif isinstance(a, Expression): + return func(a, b) + raise TypeError('arguments must be linear expressions') + return wrapper + + +_main_ctx = isl.Context() + + class Expression: """ This class implements linear expressions. @@ -41,14 +72,17 @@ class Expression: if not isinstance(constant, numbers.Rational): raise TypeError('constant must be a rational number') self._constant = constant + self._symbols = tuple(sorted(self._coefficients)) + self._dimension = len(self._symbols) return self + @property def symbols(self): - yield from sorted(self._coefficients) + return self._symbols @property def dimension(self): - return len(list(self.symbols())) + return self._dimension def coefficient(self, symbol): if isinstance(symbol, Expression) and symbol.issymbol(): @@ -63,7 +97,7 @@ class Expression: __getitem__ = coefficient def coefficients(self): - for symbol in self.symbols(): + for symbol in self.symbols: yield symbol, self.coefficient(symbol) @property @@ -74,14 +108,20 @@ class Expression: return len(self._coefficients) == 0 def values(self): - for symbol in self.symbols(): + for symbol in self.symbols: yield self.coefficient(symbol) yield self.constant + def values_int(self): + for symbol in self.symbols: + return self.coefficient(symbol) + return int(self.constant) + + @property def symbol(self): if not self.issymbol(): raise ValueError('not a symbol: {}'.format(self)) - for symbol in self.symbols(): + for symbol in self.symbols: return symbol def issymbol(self): @@ -96,18 +136,7 @@ class Expression: def __neg__(self): return self * -1 - def _polymorphic(func): - @functools.wraps(func) - def wrapper(self, other): - if isinstance(other, Expression): - return func(self, other) - if isinstance(other, numbers.Rational): - other = Expression(constant=other) - return func(self, other) - return NotImplemented - return wrapper - - @_polymorphic + @_polymorphic_method def __add__(self, other): coefficients = dict(self.coefficients()) for symbol, coefficient in other.coefficients(): @@ -120,7 +149,7 @@ class Expression: __radd__ = __add__ - @_polymorphic + @_polymorphic_method def __sub__(self, other): coefficients = dict(self.coefficients()) for symbol, coefficient in other.coefficients(): @@ -131,9 +160,10 @@ class Expression: constant = self.constant - other.constant return Expression(coefficients, constant) - __rsub__ = __sub__ + def __rsub__(self, other): + return -(self - other) - @_polymorphic + @_polymorphic_method def __mul__(self, other): if other.isconstant(): coefficients = dict(self.coefficients()) @@ -148,7 +178,7 @@ class Expression: __rmul__ = __mul__ - @_polymorphic + @_polymorphic_method def __truediv__(self, other): if other.isconstant(): coefficients = dict(self.coefficients()) @@ -163,7 +193,7 @@ class Expression: return NotImplemented def __rtruediv__(self, other): - if isinstance(other, Rational): + if isinstance(other, self): if self.isconstant(): constant = Fraction(other, self.constant) return Expression(constant=constant) @@ -174,7 +204,6 @@ class Expression: def __str__(self): string = '' - symbols = sorted(self.symbols()) i = 0 for symbol in symbols: coefficient = self[symbol] @@ -206,6 +235,8 @@ class Expression: elif constant < 0: constant *= -1 string += ' - {}'.format(constant) + if string == '': + string = '0' return string def _parenstr(self, always=False): @@ -228,7 +259,7 @@ class Expression: def fromstring(cls, string): raise NotImplementedError - @_polymorphic + @_polymorphic_method def __eq__(self, other): # "normal" equality # see http://docs.sympy.org/dev/tutorial/gotchas.html#equals-signs @@ -239,34 +270,37 @@ class Expression: def __hash__(self): return hash((self._coefficients, self._constant)) - def _canonify(self): + def _toint(self): lcm = functools.reduce(lambda a, b: a*b // gcd(a, b), [value.denominator for value in self.values()]) return self * lcm - @_polymorphic + @_polymorphic_method def _eq(self, other): - return Polyhedron(equalities=[(self - other)._canonify()]) + return Polyhedron(equalities=[(self - other)._toint()]) - @_polymorphic + @_polymorphic_method def __le__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify()]) + return Polyhedron(inequalities=[(other - self)._toint()]) - @_polymorphic + @_polymorphic_method def __lt__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify() + 1]) + return Polyhedron(inequalities=[(other - self)._toint() - 1]) - @_polymorphic + @_polymorphic_method def __ge__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify()]) + return Polyhedron(inequalities=[(self - other)._toint()]) - @_polymorphic + @_polymorphic_method def __gt__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify() + 1]) + return Polyhedron(inequalities=[(self - other)._toint() - 1]) def constant(numerator=0, denominator=None): - return Expression(constant=Fraction(numerator, denominator)) + if denominator is None and isinstance(numerator, numbers.Rational): + return Expression(constant=numerator) + else: + return Expression(constant=Fraction(numerator, denominator)) def symbol(name): if not isinstance(name, str): @@ -279,35 +313,23 @@ def symbols(names): return (symbol(name) for name in names) -def _operator(func): - @functools.wraps(func) - def wrapper(a, b): - if isinstance(a, numbers.Rational): - a = constant(a) - if isinstance(b, numbers.Rational): - b = constant(b) - if isinstance(a, Expression) and isinstance(b, Expression): - return func(a, b) - raise TypeError('arguments must be linear expressions') - return wrapper - -@_operator +@_polymorphic_operator def eq(a, b): return a._eq(b) -@_operator +@_polymorphic_operator def le(a, b): return a <= b -@_operator +@_polymorphic_operator def lt(a, b): return a < b -@_operator +@_polymorphic_operator def ge(a, b): return a >= b -@_operator +@_polymorphic_operator def gt(a, b): return a > b @@ -331,6 +353,7 @@ class Polyhedron: raise TypeError('non-integer constraint: ' '{} == 0'.format(constraint)) self._equalities.append(constraint) + self._equalities = tuple(self._equalities) self._inequalities = [] if inequalities is not None: for constraint in inequalities: @@ -339,33 +362,36 @@ class Polyhedron: raise TypeError('non-integer constraint: ' '{} <= 0'.format(constraint)) self._inequalities.append(constraint) + self._inequalities = tuple(self._inequalities) + self._constraints = self._equalities + self._inequalities + self._symbols = set() + for constraint in self._constraints: + self.symbols.update(constraint.symbols) + self._symbols = tuple(sorted(self._symbols)) return self @property def equalities(self): - yield from self._equalities + return self._equalities @property def inequalities(self): - yield from self._inequalities + return self._inequalities + @property def constraints(self): - yield from self.equalities - yield from self.inequalities + return self._constraints + @property def symbols(self): - s = set() - for constraint in self.constraints(): - s.update(constraint.symbols) - yield from sorted(s) + return self._symbols @property def dimension(self): - return len(self.symbols()) + return len(self.symbols) def __bool__(self): - # return false if the polyhedron is empty, true otherwise - raise NotImplementedError + return not self.is_empty() def __contains__(self, value): # is the value in the polyhedron? @@ -375,10 +401,11 @@ class Polyhedron: raise NotImplementedError def isempty(self): - return self == empty + bset = self._to_isl() + return bool(libisl.isl_basic_set_is_empty(bset)) def isuniverse(self): - return self == universe + raise NotImplementedError def isdisjoint(self, other): # return true if the polyhedron has no elements in common with other @@ -439,7 +466,7 @@ class Polyhedron: for constraint in self.equalities: constraints.append('{} == 0'.format(constraint)) for constraint in self.inequalities: - constraints.append('{} <= 0'.format(constraint)) + constraints.append('{} >= 0'.format(constraint)) return '{{{}}}'.format(', '.join(constraints)) def __repr__(self): @@ -452,7 +479,75 @@ class Polyhedron: def fromstring(cls, string): raise NotImplementedError + def _symbolunion(self, *others): + symbols = set(self.symbols) + for other in others: + symbols.update(other.symbols) + return sorted(symbols) + + def _to_isl(self, symbols=None): + if symbols is None: + symbols = self.symbols + num_coefficients = len(symbols) + space = libisl.isl_space_set_alloc(_main_ctx, 0, num_coefficients) + bset = libisl.isl_basic_set_universe(libisl.isl_space_copy(space)) + ls = libisl.isl_local_space_from_space(space) + ceq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(ls)) + cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls)) + '''if there are equalities/inequalities, take each constant and coefficient and add as a constraint to the basic set''' + if list(self.equalities): #check if any equalities exist + for eq in self.equalities: + coeff_eq = dict(eq.coefficients()) + if eq.constant: + value = eq.constant + ceq = libisl.isl_constraint_set_constant_si(ceq, value) + for eq in coeff_eq: + num = coeff_eq.get(eq) + iden = symbols.index(eq) + ceq = libisl.isl_constraint_set_coefficient_si(ceq, libisl.isl_dim_set, iden, num) #use 3 for type isl_dim_set + bset = libisl.isl_basic_set_add_constraint(bset, ceq) + if list(self.inequalities): #check if any inequalities exist + for ineq in self.inequalities: + coeff_in = dict(ineq.coefficients()) + if ineq.constant: + value = ineq.constant + cin = libisl.isl_constraint_set_constant_si(cin, value) + for ineq in coeff_in: + num = coeff_in.get(ineq) + iden = symbols.index(ineq) + cin = libisl.isl_constraint_set_coefficient_si(cin, libisl.isl_dim_set, iden, num) #use 3 for type isl_dim_set + bset = libisl.isl_basic_set_add_constraint(bset, cin) + bset = isl.BasicSet(bset) + return bset -empty = le(1, 0) - -universe = Polyhedron() + @classmethod + def _from_isl(cls, bset): + '''takes basic set in isl form and puts back into python version of polyhedron + isl example code gives isl form as: + "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}") + our printer is giving form as: + b'{ [i0] : 1 = 0 }' ''' + raise NotImplementedError + equalities = ... + inequalities = ... + return cls(equalities, inequalities) + #bset = self + # if self._equalities: + # constraints = libisl.isl_basic_set_equalities_matrix(bset, 3) + # elif self._inequalities: + # constraints = libisl.isl_basic_set_inequalities_matrix(bset, 3) + # print(constraints) + # return constraints + +empty = None #eq(0,1) +universe = None #Polyhedron() + + +if __name__ == '__main__': + ex1 = Expression(coefficients={'a': 1, 'x': 2}, constant=2) + ex2 = Expression(coefficients={'a': 3 , 'b': 2}, constant=3) + p = Polyhedron(inequalities=[ex1, ex2]) + bs = p._to_isl() + print(bs) + print('empty ?', p.isempty()) + print('empty ?', eq(0, 1).isempty())