X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/62fbaa7984d8035cccc97555f1de3188e280e475..ce8dda550018a59520e2d632f10d3fe5650e9d0d:/linpy/domains.py?ds=sidebyside diff --git a/linpy/domains.py b/linpy/domains.py index 9fdc7d5..a431a02 100644 --- a/linpy/domains.py +++ b/linpy/domains.py @@ -23,14 +23,16 @@ import math from fractions import Fraction from . import islhelper -from .islhelper import mainctx, libisl -from .linexprs import LinExpr, Symbol, Rational from .geometry import GeometricObject, Point, Vector +from .islhelper import libisl +from .linexprs import LinExpr, Symbol __all__ = [ + 'And', 'Domain', - 'And', 'Or', 'Not', + 'Not', + 'Or', ] @@ -38,7 +40,7 @@ __all__ = [ class Domain(GeometricObject): """ A domain is a union of polyhedra. Unlike polyhedra, domains allow exact - computation of union and complementary operations. + computation of union, subtraction and complementary operations. A domain with a unique polyhedron is automatically subclassed as a Polyhedron instance. @@ -54,22 +56,23 @@ class Domain(GeometricObject): """ Return a domain from a sequence of polyhedra. - >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2') - >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4') - >>> dom = Domain([square, square2]) + >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2') + >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3') + >>> dom = Domain(square1, square2) + >>> dom + Or(And(x <= 2, 0 <= x, y <= 2, 0 <= y), + And(x <= 3, 1 <= x, y <= 3, 1 <= y)) It is also possible to build domains from polyhedra using arithmetic - operators Domain.__and__(), Domain.__or__() or functions And() and Or(), - using one of the following instructions: + operators Domain.__or__(), Domain.__invert__() or functions Or() and + Not(), using one of the following instructions: - >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2') - >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4') - >>> dom = square | square2 - >>> dom = Or(square, square2) + >>> dom = square1 | square2 + >>> dom = Or(square1, square2) Alternatively, a domain can be built from a string: - >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4') + >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 1 <= x <= 3, 1 <= y <= 3') Finally, a domain can be built from a GeometricObject instance, calling the GeometricObject.asdomain() method. @@ -83,7 +86,7 @@ class Domain(GeometricObject): return argument.aspolyhedron() else: raise TypeError('argument must be a string ' - 'or a GeometricObject instance') + 'or a GeometricObject instance') else: for polyhedron in polyhedra: if not isinstance(polyhedron, Polyhedron): @@ -234,7 +237,7 @@ class Domain(GeometricObject): Return an equivalent domain, whose polyhedra are disjoint. """ islset = self._toislset(self.polyhedra, self.symbols) - islset = libisl.isl_set_make_disjoint(mainctx, islset) + islset = libisl.isl_set_make_disjoint(islset) return self._fromislset(islset, self.symbols) def coalesce(self): @@ -288,11 +291,12 @@ class Domain(GeometricObject): if symbol in symbols: n += 1 elif n > 0: - islset = libisl.isl_set_project_out(islset, - libisl.isl_dim_set, index + 1, n) + islset = libisl.isl_set_project_out( + islset, libisl.isl_dim_set, index + 1, n) n = 0 if n > 0: - islset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, 0, n) + islset = libisl.isl_set_project_out( + islset, libisl.isl_dim_set, 0, n) symbols = [symbol for symbol in self.symbols if symbol not in symbols] return Domain._fromislset(islset, symbols) @@ -308,8 +312,8 @@ class Domain(GeometricObject): raise ValueError('domain must be non-empty') point = {} for index, symbol in enumerate(self.symbols): - coordinate = libisl.isl_point_get_coordinate_val(islpoint, - libisl.isl_dim_set, index) + coordinate = libisl.isl_point_get_coordinate_val( + islpoint, libisl.isl_dim_set, index) coordinate = islhelper.isl_val_to_int(coordinate) point[symbol] = coordinate libisl.isl_point_free(islpoint) @@ -391,43 +395,48 @@ class Domain(GeometricObject): islset = libisl.isl_set_lexmax(islset) return self._fromislset(islset, self.symbols) - _RE_COORDINATE = re.compile(r'\((?P\-?\d+)\)(/(?P\d+))?') + if islhelper.isl_version >= '0.13': + _RE_COORDINATE = re.compile(r'\((?P\-?\d+)\)(/(?P\d+))?') + else: + _RE_COORDINATE = None def vertices(self): """ Return the vertices of the domain, as a list of rational instances of Point. """ - from .polyhedra import Polyhedron if not self.isbounded(): raise ValueError('domain must be bounded') islbset = self._toislbasicset(self.equalities, self.inequalities, - self.symbols) - vertices = libisl.isl_basic_set_compute_vertices(islbset); + self.symbols) + vertices = libisl.isl_basic_set_compute_vertices(islbset) vertices = islhelper.isl_vertices_vertices(vertices) points = [] for vertex in vertices: - expr = libisl.isl_vertex_get_expr(vertex) + expression = libisl.isl_vertex_get_expr(vertex) coordinates = [] - if islhelper.isl_version < '0.13': - constraints = islhelper.isl_basic_set_constraints(expr) + if self._RE_COORDINATE is None: + constraints = islhelper.isl_basic_set_constraints(expression) for constraint in constraints: - constant = libisl.isl_constraint_get_constant_val(constraint) + constant = libisl.isl_constraint_get_constant_val( + constraint) constant = islhelper.isl_val_to_int(constant) for index, symbol in enumerate(self.symbols): - coefficient = libisl.isl_constraint_get_coefficient_val(constraint, - libisl.isl_dim_set, index) + coefficient = \ + libisl.isl_constraint_get_coefficient_val( + constraint, libisl.isl_dim_set, index) coefficient = islhelper.isl_val_to_int(coefficient) if coefficient != 0: coordinate = -Fraction(constant, coefficient) coordinates.append((symbol, coordinate)) else: - string = islhelper.isl_multi_aff_to_str(expr) + string = islhelper.isl_multi_aff_to_str(expression) matches = self._RE_COORDINATE.finditer(string) for symbol, match in zip(self.symbols, matches): numerator = int(match.group('num')) denominator = match.group('den') - denominator = 1 if denominator is None else int(denominator) + denominator = \ + 1 if denominator is None else int(denominator) coordinate = Fraction(numerator, denominator) coordinates.append((symbol, coordinate)) points.append(Point(coordinates)) @@ -436,20 +445,19 @@ class Domain(GeometricObject): def points(self): """ Return the integer points of a bounded domain, as a list of integer - instances of Point. If the domain is not bounded, a ValueError exception - is raised. + instances of Point. If the domain is not bounded, a ValueError + exception is raised. """ if not self.isbounded(): raise ValueError('domain must be bounded') - from .polyhedra import Universe, Eq islset = self._toislset(self.polyhedra, self.symbols) islpoints = islhelper.isl_set_points(islset) points = [] for islpoint in islpoints: coordinates = {} for index, symbol in enumerate(self.symbols): - coordinate = libisl.isl_point_get_coordinate_val(islpoint, - libisl.isl_dim_set, index) + coordinate = libisl.isl_point_get_coordinate_val( + islpoint, libisl.isl_dim_set, index) coordinate = islhelper.isl_val_to_int(coordinate) coordinates[symbol] = coordinate points.append(Point(coordinates)) @@ -596,7 +604,7 @@ class Domain(GeometricObject): elif self.dimension == 3: return self._plot_3d(plot=plot, **kwargs) else: - raise ValueError('polyhedron must be 2 or 3-dimensional') + raise ValueError('domain must be two or three-dimensional') def subs(self, symbol, expression=None): """ @@ -606,7 +614,7 @@ class Domain(GeometricObject): similar to LinExpr.subs(). """ polyhedra = [polyhedron.subs(symbol, expression) - for polyhedron in self.polyhedra] + for polyhedron in self.polyhedra] return Domain(*polyhedra) @classmethod @@ -634,12 +642,12 @@ class Domain(GeometricObject): @classmethod def _toislset(cls, polyhedra, symbols): polyhedron = polyhedra[0] - islbset = polyhedron._toislbasicset(polyhedron.equalities, - polyhedron.inequalities, symbols) + islbset = polyhedron._toislbasicset( + polyhedron.equalities, polyhedron.inequalities, symbols) islset1 = libisl.isl_set_from_basic_set(islbset) for polyhedron in polyhedra[1:]: - islbset = polyhedron._toislbasicset(polyhedron.equalities, - polyhedron.inequalities, symbols) + islbset = polyhedron._toislbasicset( + polyhedron.equalities, polyhedron.inequalities, symbols) islset2 = libisl.isl_set_from_basic_set(islbset) islset1 = libisl.isl_set_union(islset1, islset2) return islset1 @@ -700,17 +708,17 @@ class Domain(GeometricObject): Create a domain from a string. Raise SyntaxError if the string is not properly formatted. """ - # remove curly brackets + # Remove curly brackets. string = cls._RE_BRACES.sub(r'', string) - # replace '=' by '==' + # Replace '=' by '=='. string = cls._RE_EQ.sub(r'\1==\2', string) - # replace 'and', 'or', 'not' + # Replace 'and', 'or', 'not'. string = cls._RE_AND.sub(r' & ', string) string = cls._RE_OR.sub(r' | ', string) string = cls._RE_NOT.sub(r' ~', string) - # add implicit multiplication operators, e.g. '5x' -> '5*x' + # Add implicit multiplication operators, e.g. '5x' -> '5*x'. string = cls._RE_NUM_VAR.sub(r'\1*\2', string) - # add parentheses to force precedence + # Add parentheses to force precedence. tokens = cls._RE_OPERATORS.split(string) for i, token in enumerate(tokens): if i % 2 == 0: @@ -725,16 +733,10 @@ class Domain(GeometricObject): strings = [repr(polyhedron) for polyhedron in self.polyhedra] return 'Or({})'.format(', '.join(strings)) - def _repr_latex_(self): - strings = [] - for polyhedron in self.polyhedra: - strings.append('({})'.format(polyhedron._repr_latex_().strip('$'))) - return '${}$'.format(' \\vee '.join(strings)) - @classmethod - def fromsympy(cls, expr): + def fromsympy(cls, expression): """ - Create a domain from a sympy expression. + Create a domain from a SymPy expression. """ import sympy from .polyhedra import Lt, Le, Eq, Ne, Ge, Gt @@ -744,19 +746,19 @@ class Domain(GeometricObject): sympy.Eq: Eq, sympy.Ne: Ne, sympy.Ge: Ge, sympy.Gt: Gt, } - if expr.func in funcmap: - args = [Domain.fromsympy(arg) for arg in expr.args] - return funcmap[expr.func](*args) - elif isinstance(expr, sympy.Expr): - return LinExpr.fromsympy(expr) - raise ValueError('non-domain expression: {!r}'.format(expr)) + if expression.func in funcmap: + args = [Domain.fromsympy(arg) for arg in expression.args] + return funcmap[expression.func](*args) + elif isinstance(expression, sympy.Expr): + return LinExpr.fromsympy(expression) + raise ValueError('non-domain expression: {!r}'.format(expression)) def tosympy(self): """ - Convert the domain to a sympy expression. + Convert the domain to a SymPy expression. """ import sympy - polyhedra = [polyhedron.tosympy() for polyhedron in polyhedra] + polyhedra = [polyhedron.tosympy() for polyhedron in self.polyhedra] return sympy.Or(*polyhedra) @@ -769,7 +771,7 @@ def And(*domains): return Universe else: return domains[0].intersection(*domains[1:]) -And.__doc__ = Domain.intersection.__doc__ + def Or(*domains): """ @@ -780,11 +782,10 @@ def Or(*domains): return Empty else: return domains[0].union(*domains[1:]) -Or.__doc__ = Domain.union.__doc__ + def Not(domain): """ Create the complementary domain of the domain given in argument. """ return ~domain -Not.__doc__ = Domain.complement.__doc__