X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/23787dd83c4990ca14e52ce3ddff256e26397cdc..3ac55f687734376c59d2d3d95b9350ad1a9c6e27:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index d1aa882..9584609 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,11 +1,9 @@ -''' -VERY MESSY, made notes on where I will change things -''' - import functools import numbers +import json import ctypes, ctypes.util from pypol import isl +from . import isl, islhelper from fractions import Fraction, gcd @@ -21,8 +19,16 @@ __all__ = [ 'empty', 'universe' ] +ids = {} -_CONTEXT = isl.Context() +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) @@ -48,6 +54,28 @@ 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 + + + class Expression: """ @@ -98,6 +126,7 @@ class Expression: __getitem__ = coefficient + @property def coefficients(self): for symbol in self.symbols(): yield symbol, self.coefficient(symbol) @@ -140,8 +169,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: @@ -153,8 +182,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: @@ -162,12 +191,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 @@ -250,7 +280,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) @@ -283,19 +313,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): @@ -363,10 +393,12 @@ class Polyhedron: 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) + #put this here just to test from isl method + #from_isl = self.from_isl(self._bset) + #print(from_isl) + #rint(self) return self @@ -397,15 +429,9 @@ class Polyhedron: 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) - return s - + s.update(constraint.symbols()) + return sorted(s) + @property def dimension(self): return len(self.symbols()) @@ -495,7 +521,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): @@ -508,35 +534,83 @@ class Polyhedron: def fromstring(cls, string): raise NotImplementedError - def to_isl(self): - space = libisl.isl_space_set_alloc(_CONTEXT, 0, len(self.symbol_count())) - bset = libisl.isl_basic_set_universe(libisl.isl_space_copy(space)) - copy = libisl.isl_basic_set_copy(bset) - ls = libisl.isl_local_space_from_space(libisl.isl_space_copy(space)) + def _symbolunion(self, *others): + print(self) + 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() + print(symbols) + print('>>>', self) + print('eq:', list(self.equalities)) + print('ineq:', list(self.inequalities)) + 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)) + ls = libisl.isl_local_space_from_space(space) ceq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(ls)) - for value in self.equalities: - for value in self.equalities: - #need method to get expression value - if self._equalities: - value = self._equalities.method_get_value_from_expression() - ceq = libisl.isl_constraint_set_constant_val(ceq, value ) - #ceq = libisl.isl_constraint_set_coefficient_si(ceq, libisl.isl_set_dim, self.symbols(), value) - ''' cin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(ls)) - for item in self.inequalities: - for item in self.inequalities: - if isinstance(item, int): - cin = libisl.isl_constraint_set_constant_si(cin, item) - else: - cin = libisl.isl_constraint_set_coefficient_si(cin, libisl.isl_set_dim, self.symbols(), item) - ''' - bsetfinal = libisl.isl_basic_set_add_contraint(copy, ceq) - #bsetfinal = libisl.isl_basic_set_add_contraint(copy, cin) - string = libisl.isl_printer_print_basic_set(bsetfinal) + '''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) + 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) + 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) + 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) - return self - -empty = eq(1, 1) - - -universe = Polyhedron() + 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 = 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()