X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/bec8e9379d875b91dd49058aeae0075bda66d6d8..3bbc19830f1dc2432f91bba40123bb60936a0be3:/pypol/linear.py?ds=sidebyside diff --git a/pypol/linear.py b/pypol/linear.py index 5dfddfe..8e96f35 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,14 +1,12 @@ +import ctypes, ctypes.util import functools import numbers -import json -import ctypes, ctypes.util -from pypol import isl 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', @@ -18,28 +16,6 @@ __all__ = [ 'empty', 'universe' ] -''' -def symbolToInt(self): - make dictionary of key:value (letter:integer) - iterate through the dictionary to find matching symbol - return the given integer value - d = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 6, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, - 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26} - if self in d: - num = d.get(self) - return num -''' - -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) @@ -65,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: @@ -137,6 +94,7 @@ class Expression: __getitem__ = coefficient + @property def coefficients(self): for symbol in self.symbols(): yield symbol, self.coefficient(symbol) @@ -158,7 +116,6 @@ class Expression: return self.coefficient(symbol) return int(self.constant) - def symbol(self): if not self.issymbol(): raise ValueError('not a symbol: {}'.format(self)) @@ -179,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: @@ -192,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: @@ -203,11 +160,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 @@ -290,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) @@ -323,24 +280,24 @@ 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): if denominator is None and isinstance(numerator, numbers.Rational): - return Expression(constant=3) + return Expression(constant=numerator) else: return Expression(constant=Fraction(numerator, denominator)) @@ -402,16 +359,9 @@ 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._bset - - + self._inequalities.append(constraint) + return self + @property def equalities(self): yield from self._equalities @@ -419,15 +369,14 @@ class Polyhedron: @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)) @@ -435,13 +384,12 @@ class Polyhedron: yield from self.equalities yield from self.inequalities - 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): return len(self.symbols()) @@ -452,7 +400,6 @@ class Polyhedron: return False else: return True - def __contains__(self, value): # is the value in the polyhedron? @@ -484,9 +431,9 @@ class Polyhedron: # test whether every element in other is in the polyhedron for value in other: if value == self.constraints(): - return True + return True else: - return False + return False raise NotImplementedError def __ge__(self, other): @@ -531,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): @@ -543,58 +490,68 @@ class Polyhedron: @classmethod def fromstring(cls, string): raise NotImplementedError - - def to_isl(self): - #d = Expression().__dict__ #write expression values to dictionary in form {'_constant': value, '_coefficients': value} - d = {'_constant': 2, '_coefficients': {'b':1}} - coeff = d.get('_coefficients') - num_coefficients = len(coeff) - space = libisl.isl_space_set_alloc(Context(), 0, num_coefficients) - bset = libisl.isl_basic_set_empty(libisl.isl_space_copy(space)) - ls = libisl.isl_local_space_from_space(libisl.isl_space_copy(space)) + + 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 - 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: - if '_constant' in d: - value = d.get('_constant') - ceq = libisl.isl_constraint_set_constant_si(ceq, value) - if '_coefficients' in d: - value_co = d.get('_coefficients') - for co in value_co: - num = value_co.get(co) - ceq = libisl.isl_constraint_set_coefficient_si(ceq, 3, get_ids(co), num) #use 3 for type isl_dim_set - bset = libisl.isl_set_add_constraint(bset, ceq) - - if self._inequalities: - if '_constant' in d: - value = d.get('_constant') - cin = libisl.isl_constraint_set_constant_si(cin, value) - if '_coefficients' in d: - value_co = d.get('_coefficients') - for co in value_co: - num = value_co.get(co) - if value_co: #if dictionary not empty add coefficient as to constraint - cin = libisl.isl_constraint_set_coefficient_si(cin, 3, get_ids(co), num) #use 3 for type isl_dim_set - bset = libisl.isl_set_add_constraint(bset, cin) - ip = libisl.isl_printer_to_str(Context()) #create string printer - ip = libisl.isl_printer_print_set(ip, bset) #print set to printer - string = libisl.isl_printer_get_str(ip) #get string from printer - string = str(string) - print(string) - return string - - + '''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 idl form as: - "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}");''' - - poly = 0 - return poly - -empty = eq(1,1) - - -universe = 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)