X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/3ac55f687734376c59d2d3d95b9350ad1a9c6e27..af10bce9dc286c2b3ffe6520c4ed0047a4475320:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 9584609..5f3c559 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,15 +1,12 @@ +import ctypes, ctypes.util import functools import numbers -import json -import ctypes, ctypes.util -from pypol import isl -from . import isl, islhelper from fractions import Fraction, gcd -libisl = ctypes.CDLL(ctypes.util.find_library('isl')) +from . import isl +from .isl import libisl -libisl.isl_printer_get_str.restype = ctypes.c_char_p __all__ = [ 'Expression', @@ -19,16 +16,6 @@ __all__ = [ 'empty', 'universe' ] -ids = {} - -def get_ids(co): - if co in ids: - return ids.get(co) - else: - idd = len(ids) - ids[co] = idd - #print(ids) - return idd def _polymorphic_method(func): @functools.wraps(func) @@ -54,27 +41,8 @@ def _polymorphic_operator(func): raise TypeError('arguments must be linear expressions') return wrapper -class Context: - - __slots__ = ('_ic') - - def __init__(self): - self._ic = libisl.isl_ctx_alloc() - - @property - def _as_parameter_(self): - return self._ic - - #comment out so does not delete itself after being created - #def __del__(self): - # libisl.isl_ctx_free(self) - - def __eq__(self, other): - if not isinstance(other, Context): - return False - return self._ic == other._ic - +_main_ctx = isl.Context() class Expression: @@ -104,15 +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(): @@ -126,9 +96,8 @@ class Expression: __getitem__ = coefficient - @property def coefficients(self): - for symbol in self.symbols(): + for symbol in self.symbols: yield symbol, self.coefficient(symbol) @property @@ -139,20 +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(): + 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): @@ -169,8 +138,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: @@ -182,8 +151,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: @@ -193,11 +162,11 @@ class Expression: 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 @@ -235,7 +204,6 @@ class Expression: def __str__(self): string = '' - symbols = sorted(self.symbols()) i = 0 for symbol in symbols: coefficient = self[symbol] @@ -280,7 +248,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) @@ -302,30 +270,30 @@ 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_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=[(other - self)._canonify()]) + return Polyhedron(inequalities=[(other - self)._toint()]) @_polymorphic_method def __lt__(self, other): - return Polyhedron(inequalities=[(other - self)._canonify() - 1]) + return Polyhedron(inequalities=[(other - self)._toint() - 1]) @_polymorphic_method def __ge__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify()]) + return Polyhedron(inequalities=[(self - other)._toint()]) @_polymorphic_method def __gt__(self, other): - return Polyhedron(inequalities=[(self - other)._canonify() - 1]) + return Polyhedron(inequalities=[(self - other)._toint() - 1]) def constant(numerator=0, denominator=None): @@ -385,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: @@ -392,57 +361,37 @@ class Polyhedron: if value.denominator != 1: raise TypeError('non-integer constraint: ' '{} <= 0'.format(constraint)) - self._inequalities.append(constraint) - self._bset = self.to_isl() - #print(self._bset) - #put this here just to test from isl method - #from_isl = self.from_isl(self._bset) - #print(from_isl) - #rint(self) - 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 + @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()) - return 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 - 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? @@ -451,11 +400,12 @@ class Polyhedron: def __eq__(self, other): raise NotImplementedError - def is_empty(self): - return + def isempty(self): + 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 @@ -472,11 +422,6 @@ 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): @@ -533,84 +478,76 @@ class Polyhedron: @classmethod def fromstring(cls, string): raise NotImplementedError - - def _symbolunion(self, *others): - print(self) - symbols = set(self.symbols()) + + def _symbolunion(self, *others): + symbols = set(self.symbols) for other in others: - symbols.update(other.symbols()) + symbols.update(other.symbols) return sorted(symbols) - - def to_isl(self, symbols=None): + + def _to_isl(self, symbols=None): if symbols is None: - symbols = self.symbols() - print(symbols) - print('>>>', self) - print('eq:', list(self.equalities)) - print('ineq:', list(self.inequalities)) + symbols = self.symbols num_coefficients = len(symbols) - ctx = Context() - space = libisl.isl_space_set_alloc(ctx, 0, num_coefficients) - bset = libisl.isl_basic_set_universe(libisl.isl_space_copy(space)) + 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) + 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) - print('id of var {} is {}, coeff is {}'.format(eq, iden, num)) - ceq = libisl.isl_constraint_set_coefficient_si(ceq, islhelper.isl_dim_set, iden, num) #use 3 for type isl_dim_set - bset = libisl.isl_basic_set_add_constraint(bset, ceq) + 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) + 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) - print('id of var {} is {}, coeff is {}'.format(ineq, iden, num)) - cin = libisl.isl_constraint_set_coefficient_si(cin, islhelper.isl_dim_set, iden, num) #use 3 for type isl_dim_set - bset = libisl.isl_basic_set_add_constraint(bset, cin) - ip = libisl.isl_printer_to_str(ctx) #create string printer - ip = libisl.isl_printer_print_basic_set(ip, bset) #print basic set to printer - string = libisl.isl_printer_get_str(ip) #get string from printer - string = str(string.decode()) - print(string) + 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): + + @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 + # 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() -#empty = eq(0,1) -empty = None -universe = None 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]) - #p = eq(ex2, 0)# 2a+4 = 0, in fact 6a+3 = 0 - #p.to_isl() - -#universe = Polyhedron() + bs = p._to_isl() + print(bs) + print('empty ?', p.isempty()) + print('empty ?', eq(0, 1).isempty())