X-Git-Url: https://svn.cri.ensmp.fr/git/linpy.git/blobdiff_plain/4162c0430092e0ba2b8d8d62b5de24cdd71abe3b..refs/heads/master:/linpy/polyhedra.py?ds=inline diff --git a/linpy/polyhedra.py b/linpy/polyhedra.py index 1ccbe9c..9e740a4 100644 --- a/linpy/polyhedra.py +++ b/linpy/polyhedra.py @@ -16,29 +16,34 @@ # 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. A - Z-polyhedron (simply called "polyhedron" in LinPy) is the set of integer + 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. """ @@ -51,9 +56,9 @@ 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') @@ -62,8 +67,9 @@ class Polyhedron(Domain): 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') >>> square1 = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2) @@ -74,9 +80,9 @@ class Polyhedron(Domain): >>> 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: + 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') @@ -94,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) @@ -140,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 @@ -172,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): @@ -214,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 = [] @@ -222,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 @@ -248,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) @@ -321,7 +341,8 @@ class Polyhedron(Domain): def fromsympy(cls, expression): domain = Domain.fromsympy(expression) if not isinstance(domain, Polyhedron): - raise ValueError('non-polyhedral expression: {!r}'.format(expression)) + raise ValueError('non-polyhedral expression: {!r}'.format( + expression)) return domain def tosympy(self): @@ -388,10 +409,11 @@ def _pseudoconstructor(func): expression = Rational(expression) else: raise TypeError('arguments must be rational numbers ' - 'or linear expressions') + 'or linear expressions') return func(*expressions) return wrapper + @_pseudoconstructor def Lt(*expressions): """ @@ -402,6 +424,7 @@ def Lt(*expressions): inequalities.append(right - left - 1) return Polyhedron([], inequalities) + @_pseudoconstructor def Le(*expressions): """ @@ -412,6 +435,7 @@ def Le(*expressions): inequalities.append(right - left) return Polyhedron([], inequalities) + @_pseudoconstructor def Eq(*expressions): """ @@ -422,6 +446,7 @@ def Eq(*expressions): equalities.append(left - right) return Polyhedron(equalities, []) + @_pseudoconstructor def Ne(*expressions): """ @@ -433,6 +458,7 @@ def Ne(*expressions): domain &= ~Eq(left, right) return domain + @_pseudoconstructor def Ge(*expressions): """ @@ -443,6 +469,7 @@ def Ge(*expressions): inequalities.append(left - right) return Polyhedron([], inequalities) + @_pseudoconstructor def Gt(*expressions): """