X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/37b02d24c845fa3c75c48a99e5e658d772b72289..36939fa400ed913afd44b37b8bb9c1a7a932e442:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index bd7037b..3cd7633 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -1,18 +1,17 @@ -import ctypes, ctypes.util import functools import numbers from fractions import Fraction, gcd -from . import isl -from .isl import libisl +from pypol import isl +from pypol.isl import libisl __all__ = [ 'Expression', 'Constant', 'Symbol', 'symbols', 'eq', 'le', 'lt', 'ge', 'gt', 'Polyhedron', - 'empty', 'universe' + 'Empty', 'Universe' ] @@ -62,7 +61,7 @@ class Expression: for symbol, coefficient in coefficients if coefficient != 0] if len(coefficients) == 0: return Constant(constant) - elif len(coefficients) == 1: + elif len(coefficients) == 1 and constant == 0: symbol, coefficient = coefficients[0] if coefficient == 1: return Symbol(symbol) @@ -135,7 +134,7 @@ class Expression: return False def __bool__(self): - True + return True def __pos__(self): return self @@ -271,7 +270,7 @@ 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 _toint(self): lcm = functools.reduce(lambda a, b: a*b // gcd(a, b), @@ -355,28 +354,28 @@ class Symbol(Expression): 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: @@ -447,27 +446,42 @@ class 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 isempty(self): bset = self._toisl() return bool(libisl.isl_basic_set_is_empty(bset)) def isuniverse(self): - raise NotImplementedError + 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 @@ -477,6 +491,10 @@ class Polyhedron: 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): @@ -502,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) @@ -519,10 +541,15 @@ class Polyhedron: return '{{{}}}'.format(', '.join(constraints)) def __repr__(self): - equalities = list(self.equalities) - inequalities = list(self.inequalities) - return '{}(equalities={!r}, inequalities={!r})' \ - ''.format(self.__class__.__name__, equalities, inequalities) + if self.isempty(): + return 'Empty' + elif self.isuniverse(): + return 'Universe' + else: + equalities = list(self.equalities) + inequalities = list(self.inequalities) + return '{}(equalities={!r}, inequalities={!r})' \ + ''.format(self.__class__.__name__, equalities, inequalities) def _symbolunion(self, *others): symbols = set(self.symbols) @@ -537,30 +564,32 @@ class Polyhedron: 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 + #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) - 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 + 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 @@ -575,24 +604,14 @@ class 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() + { [i0, i1] : 2i1 >= -2 - i0 } ''' +Empty = eq(0,1) +Universe = 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._toisl() - print(bs) - print('empty ?', p.isempty()) - print('empty ?', eq(0, 1).isempty()) + 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