X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/2849330c65ff7bbc0bfefddf0f062fce51bde7b9..5c08207a9606e513944a4ba01e6674ee8e13508a:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 2b064d4..75ae166 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,32 +1,27 @@ import functools import numbers -import ctypes, ctypes.util -from pypol import isl from fractions import Fraction, gcd -libisl = ctypes.CDLL(ctypes.util.find_library('isl')) +from pypol import isl +from pypol.isl import libisl -libisl.isl_printer_get_str.restype = ctypes.c_char_p __all__ = [ - 'Expression', - 'constant', 'symbol', 'symbols', + 'Expression', 'Constant', 'Symbol', 'symbols', 'eq', 'le', 'lt', 'ge', 'gt', 'Polyhedron', 'empty', 'universe' ] -_CONTEXT = isl.Context() - 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) + b = Constant(b) return func(a, b) return NotImplemented return wrapper @@ -37,7 +32,7 @@ def _polymorphic_operator(func): @functools.wraps(func) def wrapper(a, b): if isinstance(a, numbers.Rational): - a = constant(a) + a = Constant(a) return func(a, b) elif isinstance(a, Expression): return func(a, b) @@ -45,6 +40,9 @@ def _polymorphic_operator(func): return wrapper +_main_ctx = isl.Context() + + class Expression: """ This class implements linear expressions. @@ -55,38 +53,56 @@ class Expression: if constant: raise TypeError('too many arguments') return cls.fromstring(coefficients) - self = super().__new__(cls) - self._coefficients = {} if isinstance(coefficients, dict): coefficients = coefficients.items() - if coefficients is not None: - for symbol, coefficient in coefficients: - if isinstance(symbol, Expression) and symbol.issymbol(): - symbol = str(symbol) - elif not isinstance(symbol, str): - raise TypeError('symbols must be strings') - if not isinstance(coefficient, numbers.Rational): - raise TypeError('coefficients must be rational numbers') - if coefficient != 0: - self._coefficients[symbol] = coefficient + if coefficients is None: + return Constant(constant) + coefficients = [(symbol, coefficient) + for symbol, coefficient in coefficients if coefficient != 0] + if len(coefficients) == 0: + return Constant(constant) + elif len(coefficients) == 1 and constant == 0: + symbol, coefficient = coefficients[0] + if coefficient == 1: + return Symbol(symbol) + self = object().__new__(cls) + self._coefficients = {} + for symbol, coefficient in coefficients: + if isinstance(symbol, Symbol): + symbol = str(symbol) + elif not isinstance(symbol, str): + raise TypeError('symbols must be strings or Symbol instances') + if isinstance(coefficient, Constant): + coefficient = coefficient.constant + if not isinstance(coefficient, numbers.Rational): + raise TypeError('coefficients must be rational numbers or Constant instances') + self._coefficients[symbol] = coefficient + if isinstance(constant, Constant): + constant = constant.constant if not isinstance(constant, numbers.Rational): - raise TypeError('constant must be a rational number') + raise TypeError('constant must be a rational number or a Constant instance') self._constant = constant + self._symbols = tuple(sorted(self._coefficients)) + self._dimension = len(self._symbols) return self + @classmethod + def fromstring(cls, string): + raise NotImplementedError + @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(): + if isinstance(symbol, Symbol): symbol = str(symbol) elif not isinstance(symbol, str): - raise TypeError('symbol must be a string') + raise TypeError('symbol must be a string or a Symbol instance') try: return self._coefficients[symbol] except KeyError: @@ -95,7 +111,7 @@ class Expression: __getitem__ = coefficient def coefficients(self): - for symbol in self.symbols(): + for symbol in self.symbols: yield symbol, self.coefficient(symbol) @property @@ -103,30 +119,22 @@ class Expression: return self._constant def isconstant(self): - return len(self._coefficients) == 0 + return False 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(): - return symbol + raise ValueError('not a symbol: {}'.format(self)) def issymbol(self): - return len(self._coefficients) == 1 and self._constant == 0 + return False def __bool__(self): - return (not self.isconstant()) or bool(self.constant) + return True def __pos__(self): return self @@ -158,7 +166,8 @@ 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): @@ -201,10 +210,9 @@ class Expression: def __str__(self): string = '' - symbols = sorted(self.symbols()) i = 0 - for symbol in symbols: - coefficient = self[symbol] + for symbol in self.symbols: + coefficient = self.coefficient(symbol) if coefficient == 1: if i == 0: string += symbol @@ -253,10 +261,6 @@ class Expression: string += '}}, {!r})'.format(self.constant) return string - @classmethod - def fromstring(cls, string): - raise NotImplementedError - @_polymorphic_method def __eq__(self, other): # "normal" equality @@ -266,70 +270,112 @@ class Expression: self.constant == other.constant def __hash__(self): - return hash((self._coefficients, self._constant)) + return hash((tuple(sorted(self._coefficients.items())), 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_method def _eq(self, other): - return Polyhedron(equalities=[(self - other)._canonify()]) + return Polyhedron(equalities=[(self - other)._toint()]) @_polymorphic_method def __le__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify()]) + return Polyhedron(inequalities=[(other - self)._toint()]) @_polymorphic_method def __lt__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify() + 1]) + return Polyhedron(inequalities=[(other - self)._toint() - 1]) @_polymorphic_method def __ge__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify()]) + return Polyhedron(inequalities=[(self - other)._toint()]) @_polymorphic_method def __gt__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify() + 1]) + return Polyhedron(inequalities=[(self - other)._toint() - 1]) + + +class Constant(Expression): + + def __new__(cls, numerator=0, denominator=None): + self = object().__new__(cls) + if denominator is None: + if isinstance(numerator, numbers.Rational): + self._constant = numerator + elif isinstance(numerator, Constant): + self._constant = numerator.constant + else: + raise TypeError('constant must be a rational number or a Constant instance') + else: + self._constant = Fraction(numerator, denominator) + self._coefficients = {} + self._symbols = () + self._dimension = 0 + return self + + def isconstant(self): + return True + + def __bool__(self): + return bool(self.constant) + def __repr__(self): + return '{}({!r})'.format(self.__class__.__name__, self._constant) + + +class Symbol(Expression): + + def __new__(cls, name): + if isinstance(name, Symbol): + name = name.symbol + elif not isinstance(name, str): + raise TypeError('name must be a string or a Symbol instance') + self = object().__new__(cls) + self._coefficients = {name: 1} + self._constant = 0 + self._symbols = tuple(name) + self._symbol = name + self._dimension = 1 + return self -def constant(numerator=0, denominator=None): - if denominator is None and isinstance(numerator, numbers.Rational): - return Expression(constant=numerator) - else: - return Expression(constant=Fraction(numerator, denominator)) + @property + def symbol(self): + return self._symbol + + def issymbol(self): + return True -def symbol(name): - if not isinstance(name, str): - raise TypeError('name must be a string') - return Expression(coefficients={name: 1}) + def __repr__(self): + return '{}({!r})'.format(self.__class__.__name__, self._symbol) def symbols(names): if isinstance(names, str): names = names.replace(',', ' ').split() - return (symbol(name) for name in names) + return (Symbol(name) for name in names) @_polymorphic_operator def eq(a, b): - return a._eq(b) + return a.__eq__(b) @_polymorphic_operator def le(a, b): - return a <= b + return a.__le__(b) @_polymorphic_operator def lt(a, b): - return a < b + return a.__lt__(b) @_polymorphic_operator def ge(a, b): - return a >= b + return a.__ge__(b) @_polymorphic_operator def gt(a, b): - return a > b + return a.__gt__(b) class Polyhedron: @@ -351,6 +397,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: @@ -358,102 +405,96 @@ class Polyhedron: if value.denominator != 1: raise TypeError('non-integer constraint: ' '{} <= 0'.format(constraint)) - self._inequalities.append(constraint) - print('in polyhedron') - #print(self.constraints()) - self._bset = self.to_isl() - #print(self._bset) - return self - - + 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 + + @classmethod + def fromstring(cls, string): + raise NotImplementedError + @property def equalities(self): - yield from self._equalities + return self._equalities @property 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)) + 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) - - def symbol_count(self): - s = [] - for constraint in self.constraints(): - s.append(constraint.symbols) - print(s) - return 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 - if self._equalities or self._inequalities: - return False - else: - return True - + return not self.is_empty() def __contains__(self, value): # is the value in the polyhedron? raise NotImplementedError def __eq__(self, other): - raise NotImplementedError + # works correctly when symbols is not passed + # should be equal if values are the same even if symbols are different + bset = self._toisl() + other = other._toisl() + return bool(libisl.isl_basic_set_plain_is_equal(bset, other)) - def is_empty(self): - return + def isempty(self): + bset = self._toisl() + return bool(libisl.isl_basic_set_is_empty(bset)) def isuniverse(self): - return self == universe + bset = self._toisl() + return bool(libisl.isl_basic_set_is_universe(bset)) def isdisjoint(self, other): # return true if the polyhedron has no elements in common with other - raise NotImplementedError + #symbols = self._symbolunion(other) + bset = self._toisl() + other = other._toisl() + return bool(libisl.isl_set_is_disjoint(bset, other)) def issubset(self, other): - raise NotImplementedError + # check if self(bset) is a subset of other + symbols = self._symbolunion(other) + bset = self._toisl(symbols) + other = other._toisl(symbols) + return bool(libisl.isl_set_is_strict_subset(other, bset)) def __le__(self, other): return self.issubset(other) def __lt__(self, other): - raise NotImplementedError + symbols = self._symbolunion(other) + bset = self._toisl(symbols) + other = other._toisl(symbols) + return bool(libisl.isl_set_is_strict_subset(other, bset)) 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): return self.issuperset(other) def __gt__(self, other): + symbols = self._symbolunion(other) + bset = self._toisl(symbols) + other = other._toisl(symbols) + bool(libisl.isl_set_is_strict_subset(other, bset)) raise NotImplementedError def union(self, *others): @@ -479,10 +520,14 @@ class Polyhedron: def __and__(self, other): return self.intersection(other) - def difference(self, *others): - # return a new polyhedron with elements in the polyhedron that are not - # in the others - raise NotImplementedError + def difference(self, other): + # return a new polyhedron with elements in the polyhedron that are not in the other + symbols = self._symbolunion(other) + bset = self._toisl(symbols) + other = other._toisl(symbols) + difference = libisl.isl_set_subtract(bset, other) + return difference + def __sub__(self, other): return self.difference(other) @@ -492,7 +537,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): @@ -501,57 +546,67 @@ class Polyhedron: return '{}(equalities={!r}, inequalities={!r})' \ ''.format(self.__class__.__name__, equalities, inequalities) + def _symbolunion(self, *others): + symbols = set(self.symbols) + for other in others: + symbols.update(other.symbols) + return sorted(symbols) + + def _toisl(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) + #if there are equalities/inequalities, take each constant and coefficient and add as a constraint to the basic set + for eq in self.equalities: + ceq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(ls)) + coeff_eq = dict(eq.coefficients()) + if eq.constant: + value = str(eq.constant).encode() + val = libisl.isl_val_read_from_str(_main_ctx, value) + ceq = libisl.isl_constraint_set_constant_val(ceq, val) + for eq in coeff_eq: + number = str(coeff_eq.get(eq)).encode() + num = libisl.isl_val_read_from_str(_main_ctx, number) + iden = symbols.index(eq) + ceq = libisl.isl_constraint_set_coefficient_val(ceq, libisl.isl_dim_set, iden, num) #use 3 for type isl_dim_set + bset = libisl.isl_basic_set_add_constraint(bset, ceq) + for ineq in self.inequalities: + cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls)) + coeff_in = dict(ineq.coefficients()) + if ineq.constant: + value = str(ineq.constant).encode() + val = libisl.isl_val_read_from_str(_main_ctx, value) + cin = libisl.isl_constraint_set_constant_val(cin, val) + for ineq in coeff_in: + number = str(coeff_in.get(ineq)).encode() + num = libisl.isl_val_read_from_str(_main_ctx, number) + iden = symbols.index(ineq) + cin = libisl.isl_constraint_set_coefficient_val(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 + @classmethod - def fromstring(cls, string): + def _fromisl(cls, bset): raise NotImplementedError - - def printer(self): - - ip = libisl.isl_printer_to_str(_CONTEXT) - ip = libisl.isl_printer_print_val(ip, self) - string = libisl.isl_printer_get_str(ip).decode() - print(string) - return string - - - def to_isl(self): - space = libisl.isl_space_set_alloc(_CONTEXT, 0, len(self.symbol_count())) - bset = libisl.isl_basic_set_empty(libisl.isl_space_copy(space)) - ls = libisl.isl_local_space_from_space(libisl.isl_space_copy(space)) - ceq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(ls)) - cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls)) - dict_ex = Expression().__dict__ - ''' - if there are equalities/inequalities, take each constant and coefficient and add as a constraint to the basic set - need to change the symbols method to a lookup table for the integer value for each letter that could be a symbol - ''' - if self.equalities: - for _constant in dict_ex: - value = dict_ex.get('_constant') - ceq = libisl.isl_constraint_set_constant_val(ceq, value) - for _coefficients in dict_ex: - value_co = dict_ex.get('_coefficients') - if value_co: - ceq = libisl.isl_constraint_set_coefficient_si(ceq, libisl.isl_set_dim, self.symbols(), value_co) - bset = libisl.isl_set_add_constraint(bset, ceq) - - elif self.inequalities: - for _constant in dict_ex: - value = dict_ex.get('_constant') - cin = libisl.isl_constraint_set_constant_val(cin, value) - for _coefficients in dict_ex: - value_co = dict_ex.get('_coefficients') - if value_co: - cin = libisl.isl_constraint_set_coefficient_si(cin, libisl.isl_set_dim, self.symbols(), value_co) - bset = libisl.isl_set_add_contraint(bset, cin) - string = self.printer() - #string = libisl.isl_printer_print_basic_set(bset) - print('here') - print(string) - print(self) - return string - -empty = eq(1, 1) - - -universe = Polyhedron() + equalities = ... + inequalities = ... + return cls(equalities, inequalities) + '''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: + { [i0, i1] : 2i1 >= -2 - i0 } ''' + +empty = None #eq(0,1) +universe = None #Polyhedron() + +if __name__ == '__main__': + ex1 = Expression(coefficients={'a': 6, 'b': 6}, constant= 3) #this is the expression that does not work (even without adding values) + ex2 = Expression(coefficients={'x': 4, 'y': 2}, constant= 3) + p = Polyhedron(equalities=[ex2]) + p2 = Polyhedron(equalities=[ex2]) + print(p._toisl()) # checking is values works for toisl