X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/ddefc755b0637b08a0a2788be3a0678b52942f5b..ce8dda550018a59520e2d632f10d3fe5650e9d0d:/linpy/polyhedra.py?ds=inline diff --git a/linpy/polyhedra.py b/linpy/polyhedra.py index bfc7efe..9e740a4 100644 --- a/linpy/polyhedra.py +++ b/linpy/polyhedra.py @@ -16,29 +16,35 @@ # along with LinPy. If not, see . import functools -import math import numbers from . import islhelper -from .islhelper import mainctx, libisl +from .domains import Domain from .geometry import GeometricObject, Point +from .islhelper import libisl, mainctx from .linexprs import LinExpr, Rational -from .domains import Domain __all__ = [ + 'Empty', + 'Eq', + 'Ge', + 'Gt', + 'Le', + 'Lt', + 'Ne', 'Polyhedron', - 'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt', - 'Empty', 'Universe', + 'Universe', ] class Polyhedron(Domain): """ A convex polyhedron (or simply "polyhedron") is the space defined by a - system of linear equalities and inequalities. This space can be - unbounded. + system of linear equalities and inequalities. This space can be unbounded. + A Z-polyhedron (simply called "polyhedron" in LinPy) is the set of integer + points in a convex polyhedron. """ __slots__ = ( @@ -50,34 +56,38 @@ class Polyhedron(Domain): def __new__(cls, equalities=None, inequalities=None): """ - Return a polyhedron from two sequences of linear expressions: equalities - is a list of expressions equal to 0, and inequalities is a list of - expressions greater or equal to 0. For example, the polyhedron + Return a polyhedron from two sequences of linear expressions: + equalities is a list of expressions equal to 0, and inequalities is a + list of expressions greater or equal to 0. For example, the polyhedron 0 <= x <= 2, 0 <= y <= 2 can be constructed with: >>> x, y = symbols('x y') - >>> square = Polyhedron([], [x, 2 - x, y, 2 - y]) + >>> square1 = Polyhedron([], [x, 2 - x, y, 2 - y]) + >>> square1 + And(0 <= x, x <= 2, 0 <= y, y <= 2) It may be easier to use comparison operators LinExpr.__lt__(), - LinExpr.__le__(), LinExpr.__ge__(), LinExpr.__gt__(), or functions Lt(), - Le(), Eq(), Ge() and Gt(), using one of the following instructions: + LinExpr.__le__(), LinExpr.__ge__(), LinExpr.__gt__(), or + functions Lt(), Le(), Eq(), Ge() and Gt(), using one of the following + instructions: >>> x, y = symbols('x y') - >>> square = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2) - >>> square = Le(0, x, 2) & Le(0, y, 2) + >>> square1 = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2) + >>> square1 = Le(0, x, 2) & Le(0, y, 2) It is also possible to build a polyhedron from a string. - >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2') + >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2') Finally, a polyhedron can be constructed from a GeometricObject - instance, calling the GeometricObject.aspolyedron() method. This way, it - is possible to compute the polyhedral hull of a Domain instance, i.e., - the convex hull of two polyhedra: - - >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2') - >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4') - >>> Polyhedron(square | square2) + instance, calling the GeometricObject.aspolyedron() method. This way, + it is possible to compute the polyhedral hull of a Domain instance, + i.e., the convex hull of two polyhedra: + + >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2') + >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3') + >>> Polyhedron(square1 | square2) + And(0 <= x, 0 <= y, x <= y + 2, y <= x + 2, x <= 3, y <= 3) """ if isinstance(equalities, str): if inequalities is not None: @@ -90,15 +100,23 @@ class Polyhedron(Domain): sc_equalities = [] if equalities is not None: for equality in equalities: - if not isinstance(equality, LinExpr): - raise TypeError('equalities must be linear expressions') - sc_equalities.append(equality.scaleint()) + if isinstance(equality, LinExpr): + sc_equalities.append(equality.scaleint()) + elif isinstance(equality, numbers.Rational): + sc_equalities.append(Rational(equality).scaleint()) + else: + raise TypeError('equalities must be linear expressions ' + 'or rational numbers') sc_inequalities = [] if inequalities is not None: for inequality in inequalities: - if not isinstance(inequality, LinExpr): - raise TypeError('inequalities must be linear expressions') - sc_inequalities.append(inequality.scaleint()) + if isinstance(inequality, LinExpr): + sc_inequalities.append(inequality.scaleint()) + elif isinstance(inequality, numbers.Rational): + sc_inequalities.append(Rational(inequality).scaleint()) + else: + raise TypeError('inequalities must be linear expressions ' + 'or rational numbers') symbols = cls._xsymbols(sc_equalities + sc_inequalities) islbset = cls._toislbasicset(sc_equalities, sc_inequalities, symbols) return cls._fromislbasicset(islbset, symbols) @@ -136,7 +154,7 @@ class Polyhedron(Domain): def isuniverse(self): islbset = self._toislbasicset(self.equalities, self.inequalities, - self.symbols) + self.symbols) universe = bool(libisl.isl_basic_set_is_universe(islbset)) libisl.isl_basic_set_free(islbset) return universe @@ -168,9 +186,9 @@ class Polyhedron(Domain): def subs(self, symbol, expression=None): equalities = [equality.subs(symbol, expression) - for equality in self.equalities] + for equality in self.equalities] inequalities = [inequality.subs(symbol, expression) - for inequality in self.inequalities] + for inequality in self.inequalities] return Polyhedron(equalities, inequalities) def asinequalities(self): @@ -210,6 +228,10 @@ class Polyhedron(Domain): @classmethod def _fromislbasicset(cls, islbset, symbols): + if bool(libisl.isl_basic_set_is_empty(islbset)): + return Empty + if bool(libisl.isl_basic_set_is_universe(islbset)): + return Universe islconstraints = islhelper.isl_basic_set_constraints(islbset) equalities = [] inequalities = [] @@ -218,8 +240,8 @@ class Polyhedron(Domain): constant = islhelper.isl_val_to_int(constant) coefficients = {} for index, symbol in enumerate(symbols): - coefficient = libisl.isl_constraint_get_coefficient_val(islconstraint, - libisl.isl_dim_set, index) + coefficient = libisl.isl_constraint_get_coefficient_val( + islconstraint, libisl.isl_dim_set, index) coefficient = islhelper.isl_val_to_int(coefficient) if coefficient != 0: coefficients[symbol] = coefficient @@ -244,26 +266,28 @@ class Polyhedron(Domain): islbset = libisl.isl_basic_set_universe(libisl.isl_space_copy(islsp)) islls = libisl.isl_local_space_from_space(islsp) for equality in equalities: - isleq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(islls)) + isleq = libisl.isl_equality_alloc( + libisl.isl_local_space_copy(islls)) for symbol, coefficient in equality.coefficients(): islval = str(coefficient).encode() islval = libisl.isl_val_read_from_str(mainctx, islval) index = indices[symbol] - isleq = libisl.isl_constraint_set_coefficient_val(isleq, - libisl.isl_dim_set, index, islval) + isleq = libisl.isl_constraint_set_coefficient_val( + isleq, libisl.isl_dim_set, index, islval) if equality.constant != 0: islval = str(equality.constant).encode() islval = libisl.isl_val_read_from_str(mainctx, islval) isleq = libisl.isl_constraint_set_constant_val(isleq, islval) islbset = libisl.isl_basic_set_add_constraint(islbset, isleq) for inequality in inequalities: - islin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(islls)) + islin = libisl.isl_inequality_alloc( + libisl.isl_local_space_copy(islls)) for symbol, coefficient in inequality.coefficients(): islval = str(coefficient).encode() islval = libisl.isl_val_read_from_str(mainctx, islval) index = indices[symbol] - islin = libisl.isl_constraint_set_coefficient_val(islin, - libisl.isl_dim_set, index, islval) + islin = libisl.isl_constraint_set_coefficient_val( + islin, libisl.isl_dim_set, index, islval) if inequality.constant != 0: islval = str(inequality.constant).encode() islval = libisl.isl_val_read_from_str(mainctx, islval) @@ -313,19 +337,12 @@ class Polyhedron(Domain): else: return 'And({})'.format(', '.join(strings)) - def _repr_latex_(self): - strings = [] - for equality in self.equalities: - strings.append('{} = 0'.format(equality._repr_latex_().strip('$'))) - for inequality in self.inequalities: - strings.append('{} \\ge 0'.format(inequality._repr_latex_().strip('$'))) - return '$${}$$'.format(' \\wedge '.join(strings)) - @classmethod - def fromsympy(cls, expr): - domain = Domain.fromsympy(expr) + def fromsympy(cls, expression): + domain = Domain.fromsympy(expression) if not isinstance(domain, Polyhedron): - raise ValueError('non-polyhedral expression: {!r}'.format(expr)) + raise ValueError('non-polyhedral expression: {!r}'.format( + expression)) return domain def tosympy(self): @@ -359,9 +376,6 @@ class EmptyType(Polyhedron): def __repr__(self): return 'Empty' - def _repr_latex_(self): - return '$$\\emptyset$$' - Empty = EmptyType() @@ -382,83 +396,86 @@ class UniverseType(Polyhedron): def __repr__(self): return 'Universe' - def _repr_latex_(self): - return '$$\\Omega$$' - Universe = UniverseType() def _pseudoconstructor(func): @functools.wraps(func) - def wrapper(expr1, expr2, *exprs): - exprs = (expr1, expr2) + exprs - for expr in exprs: - if not isinstance(expr, LinExpr): - if isinstance(expr, numbers.Rational): - expr = Rational(expr) + def wrapper(expression1, expression2, *expressions): + expressions = (expression1, expression2) + expressions + for expression in expressions: + if not isinstance(expression, LinExpr): + if isinstance(expression, numbers.Rational): + expression = Rational(expression) else: raise TypeError('arguments must be rational numbers ' - 'or linear expressions') - return func(*exprs) + 'or linear expressions') + return func(*expressions) return wrapper + @_pseudoconstructor -def Lt(*exprs): +def Lt(*expressions): """ Create the polyhedron with constraints expr1 < expr2 < expr3 ... """ inequalities = [] - for left, right in zip(exprs, exprs[1:]): + for left, right in zip(expressions, expressions[1:]): inequalities.append(right - left - 1) return Polyhedron([], inequalities) + @_pseudoconstructor -def Le(*exprs): +def Le(*expressions): """ Create the polyhedron with constraints expr1 <= expr2 <= expr3 ... """ inequalities = [] - for left, right in zip(exprs, exprs[1:]): + for left, right in zip(expressions, expressions[1:]): inequalities.append(right - left) return Polyhedron([], inequalities) + @_pseudoconstructor -def Eq(*exprs): +def Eq(*expressions): """ Create the polyhedron with constraints expr1 == expr2 == expr3 ... """ equalities = [] - for left, right in zip(exprs, exprs[1:]): + for left, right in zip(expressions, expressions[1:]): equalities.append(left - right) return Polyhedron(equalities, []) + @_pseudoconstructor -def Ne(*exprs): +def Ne(*expressions): """ Create the domain such that expr1 != expr2 != expr3 ... The result is a Domain object, not a Polyhedron. """ domain = Universe - for left, right in zip(exprs, exprs[1:]): + for left, right in zip(expressions, expressions[1:]): domain &= ~Eq(left, right) return domain + @_pseudoconstructor -def Ge(*exprs): +def Ge(*expressions): """ Create the polyhedron with constraints expr1 >= expr2 >= expr3 ... """ inequalities = [] - for left, right in zip(exprs, exprs[1:]): + for left, right in zip(expressions, expressions[1:]): inequalities.append(left - right) return Polyhedron([], inequalities) + @_pseudoconstructor -def Gt(*exprs): +def Gt(*expressions): """ Create the polyhedron with constraints expr1 > expr2 > expr3 ... """ inequalities = [] - for left, right in zip(exprs, exprs[1:]): + for left, right in zip(expressions, expressions[1:]): inequalities.append(left - right - 1) return Polyhedron([], inequalities)