X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/98d00e8b628b571e133bcfa494c0e8f0ab781234..1d10c1b14b9544aba049dab42fff4b1224bb1640:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index fabf2a2..8e96f35 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', @@ -26,18 +29,22 @@ def _polymorphic_method(func): 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) - if isinstance(b, numbers.Rational): - b = constant(b) - if isinstance(a, Expression) and isinstance(b, Expression): + 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. @@ -67,6 +74,7 @@ class Expression: self._constant = constant return self + def symbols(self): yield from sorted(self._coefficients) @@ -86,6 +94,7 @@ class Expression: __getitem__ = coefficient + @property def coefficients(self): for symbol in self.symbols(): yield symbol, self.coefficient(symbol) @@ -102,6 +111,11 @@ class Expression: yield self.coefficient(symbol) yield self.constant + def values_int(self): + for symbol in self.symbols(): + return self.coefficient(symbol) + return int(self.constant) + def symbol(self): if not self.issymbol(): raise ValueError('not a symbol: {}'.format(self)) @@ -122,8 +136,8 @@ class Expression: @_polymorphic_method def __add__(self, other): - coefficients = dict(self.coefficients()) - for symbol, coefficient in other.coefficients(): + coefficients = dict(self.coefficients) + for symbol, coefficient in other.coefficients: if symbol in coefficients: coefficients[symbol] += coefficient else: @@ -135,8 +149,8 @@ class Expression: @_polymorphic_method def __sub__(self, other): - coefficients = dict(self.coefficients()) - for symbol, coefficient in other.coefficients(): + coefficients = dict(self.coefficients) + for symbol, coefficient in other.coefficients: if symbol in coefficients: coefficients[symbol] -= coefficient else: @@ -144,12 +158,13 @@ class Expression: constant = self.constant - other.constant return Expression(coefficients, constant) - __rsub__ = __sub__ + def __rsub__(self, other): + return -(self - other) @_polymorphic_method def __mul__(self, other): if other.isconstant(): - coefficients = dict(self.coefficients()) + coefficients = dict(self.coefficients) for symbol in coefficients: coefficients[symbol] *= other.constant constant = self.constant * other.constant @@ -176,7 +191,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) @@ -232,7 +247,7 @@ class Expression: def __repr__(self): string = '{}({{'.format(self.__class__.__name__) - for i, (symbol, coefficient) in enumerate(self.coefficients()): + for i, (symbol, coefficient) in enumerate(self.coefficients): if i != 0: string += ', ' string += '{!r}: {!r}'.format(symbol, coefficient) @@ -265,19 +280,19 @@ class Expression: @_polymorphic_method def __le__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify()]) + return Polyhedron(inequalities=[(other - self)._canonify()]) @_polymorphic_method def __lt__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify() + 1]) + return Polyhedron(inequalities=[(other - self)._canonify() - 1]) @_polymorphic_method def __ge__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify()]) + return Polyhedron(inequalities=[(self - other)._canonify()]) @_polymorphic_method def __gt__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify() + 1]) + return Polyhedron(inequalities=[(self - other)._canonify() - 1]) def constant(numerator=0, denominator=None): @@ -355,6 +370,16 @@ class Polyhedron: def inequalities(self): yield from self._inequalities + @property + def constant(self): + return self._constant + + def isconstant(self): + return len(self._coefficients) == 0 + + def isempty(self): + return bool(libisl.isl_basic_set_is_empty(self._bset)) + def constraints(self): yield from self.equalities yield from self.inequalities @@ -362,8 +387,8 @@ class Polyhedron: def symbols(self): s = set() for constraint in self.constraints(): - s.update(constraint.symbols) - yield from sorted(s) + s.update(constraint.symbols()) + return sorted(s) @property def dimension(self): @@ -371,7 +396,10 @@ class Polyhedron: def __bool__(self): # return false if the polyhedron is empty, true otherwise - raise NotImplementedError + if self._equalities or self._inequalities: + return False + else: + return True def __contains__(self, value): # is the value in the polyhedron? @@ -380,8 +408,8 @@ class Polyhedron: def __eq__(self, other): raise NotImplementedError - def isempty(self): - return self == empty + def is_empty(self): + return def isuniverse(self): return self == universe @@ -401,6 +429,11 @@ class Polyhedron: def issuperset(self, other): # test whether every element in other is in the polyhedron + for value in other: + if value == self.constraints(): + return True + else: + return False raise NotImplementedError def __ge__(self, other): @@ -445,7 +478,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): @@ -458,7 +491,67 @@ class Polyhedron: def fromstring(cls, string): raise NotImplementedError - -empty = le(1, 0) - -universe = Polyhedron() + 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 + + def from_isl(self, 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 }' ''' + #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)