X-Git-Url: https://scm.cri.mines-paristech.fr/git/linpy.git/blobdiff_plain/7b93cea1daf2889e9ee10ca9c22a1b5124404937..916d092d8a3bc9b0f2097c4f6c953f3a69b668e7:/linpy/linexprs.py diff --git a/linpy/linexprs.py b/linpy/linexprs.py index aedf170..3c00f22 100644 --- a/linpy/linexprs.py +++ b/linpy/linexprs.py @@ -25,7 +25,7 @@ from fractions import Fraction, gcd __all__ = [ - 'Expression', + 'LinExpr', 'Symbol', 'Dummy', 'symbols', 'Rational', ] @@ -34,7 +34,7 @@ __all__ = [ def _polymorphic(func): @functools.wraps(func) def wrapper(left, right): - if isinstance(right, Expression): + if isinstance(right, LinExpr): return func(left, right) elif isinstance(right, numbers.Rational): right = Rational(right) @@ -43,16 +43,50 @@ def _polymorphic(func): return wrapper -class Expression: +class LinExpr: """ - This class implements linear expressions. + A linear expression consists of a list of coefficient-variable pairs + that capture the linear terms, plus a constant term. Linear expressions + are used to build constraints. They are temporary objects that typically + have short lifespans. + + Linear expressions are generally built using overloaded operators. For + example, if x is a Symbol, then x + 1 is an instance of LinExpr. + + LinExpr instances are hashable, and should be treated as immutable. """ def __new__(cls, coefficients=None, constant=0): + """ + Return a linear expression from a dictionary or a sequence, that maps + symbols to their coefficients, and a constant term. The coefficients and + the constant term must be rational numbers. + + For example, the linear expression x + 2*y + 1 can be constructed using + one of the following instructions: + + >>> x, y = symbols('x y') + >>> LinExpr({x: 1, y: 2}, 1) + >>> LinExpr([(x, 1), (y, 2)], 1) + + However, it may be easier to use overloaded operators: + + >>> x, y = symbols('x y') + >>> x + 2*y + 1 + + Alternatively, linear expressions can be constructed from a string: + + >>> LinExpr('x + 2y + 1') + + A linear expression with a single symbol of coefficient 1 and no + constant term is automatically subclassed as a Symbol instance. A linear + expression with no symbol, only a constant term, is automatically + subclassed as a Rational instance. + """ if isinstance(coefficients, str): if constant != 0: raise TypeError('too many arguments') - return Expression.fromstring(coefficients) + return LinExpr.fromstring(coefficients) if coefficients is None: return Rational(constant) if isinstance(coefficients, Mapping): @@ -82,41 +116,70 @@ class Expression: return self def coefficient(self, symbol): + """ + Return the coefficient value of the given symbol, or 0 if the symbol + does not appear in the expression. + """ if not isinstance(symbol, Symbol): raise TypeError('symbol must be a Symbol instance') - return Rational(self._coefficients.get(symbol, 0)) + return self._coefficients.get(symbol, Fraction(0)) __getitem__ = coefficient def coefficients(self): - for symbol, coefficient in self._coefficients.items(): - yield symbol, Rational(coefficient) + """ + Iterate over the pairs (symbol, value) of linear terms in the + expression. The constant term is ignored. + """ + yield from self._coefficients.items() @property def constant(self): - return Rational(self._constant) + """ + The constant term of the expression. + """ + return self._constant @property def symbols(self): + """ + The tuple of symbols present in the expression, sorted according to + Symbol.sortkey(). + """ return self._symbols @property def dimension(self): + """ + The dimension of the expression, i.e. the number of symbols present in + it. + """ return self._dimension def __hash__(self): return hash((tuple(self._coefficients.items()), self._constant)) def isconstant(self): + """ + Return True if the expression only consists of a constant term. In this + case, it is a Rational instance. + """ return False def issymbol(self): + """ + Return True if an expression only consists of a symbol with coefficient + 1. In this case, it is a Symbol instance. + """ return False def values(self): - for coefficient in self._coefficients.values(): - yield Rational(coefficient) - yield Rational(self._constant) + """ + Iterate over the coefficient values in the expression, and the constant + term. + """ + yield from self._coefficients.values() + yield self._constant def __bool__(self): return True @@ -129,90 +192,124 @@ class Expression: @_polymorphic def __add__(self, other): + """ + Return the sum of two linear expressions. + """ coefficients = defaultdict(Fraction, self._coefficients) for symbol, coefficient in other._coefficients.items(): coefficients[symbol] += coefficient constant = self._constant + other._constant - return Expression(coefficients, constant) + return LinExpr(coefficients, constant) __radd__ = __add__ @_polymorphic def __sub__(self, other): + """ + Return the difference between two linear expressions. + """ coefficients = defaultdict(Fraction, self._coefficients) for symbol, coefficient in other._coefficients.items(): coefficients[symbol] -= coefficient constant = self._constant - other._constant - return Expression(coefficients, constant) + return LinExpr(coefficients, constant) @_polymorphic def __rsub__(self, other): return other - self def __mul__(self, other): + """ + Return the product of the linear expression by a rational. + """ if isinstance(other, numbers.Rational): coefficients = ((symbol, coefficient * other) for symbol, coefficient in self._coefficients.items()) constant = self._constant * other - return Expression(coefficients, constant) + return LinExpr(coefficients, constant) return NotImplemented __rmul__ = __mul__ def __truediv__(self, other): + """ + Return the quotient of the linear expression by a rational. + """ if isinstance(other, numbers.Rational): coefficients = ((symbol, coefficient / other) for symbol, coefficient in self._coefficients.items()) constant = self._constant / other - return Expression(coefficients, constant) + return LinExpr(coefficients, constant) return NotImplemented @_polymorphic def __eq__(self, other): - # returns a boolean, not a constraint - # see http://docs.sympy.org/dev/tutorial/gotchas.html#equals-signs - return isinstance(other, Expression) and \ - self._coefficients == other._coefficients and \ + """ + Test whether two linear expressions are equal. Unlike methods + LinExpr.__lt__(), LinExpr.__le__(), LinExpr.__ge__(), LinExpr.__gt__(), + the result is a boolean value, not a polyhedron. To express that two + linear expressions are equal or not equal, use functions Eq() and Ne() + instead. + """ + return self._coefficients == other._coefficients and \ self._constant == other._constant - def __le__(self, other): - from .polyhedra import Le - return Le(self, other) - + @_polymorphic def __lt__(self, other): - from .polyhedra import Lt - return Lt(self, other) + from .polyhedra import Polyhedron + return Polyhedron([], [other - self - 1]) + + @_polymorphic + def __le__(self, other): + from .polyhedra import Polyhedron + return Polyhedron([], [other - self]) + @_polymorphic def __ge__(self, other): - from .polyhedra import Ge - return Ge(self, other) + from .polyhedra import Polyhedron + return Polyhedron([], [self - other]) + @_polymorphic def __gt__(self, other): - from .polyhedra import Gt - return Gt(self, other) + from .polyhedra import Polyhedron + return Polyhedron([], [self - other - 1]) def scaleint(self): - lcm = functools.reduce(lambda a, b: a*b // gcd(a, b), + """ + Return the expression multiplied by its lowest common denominator to + make all values integer. + """ + lcd = functools.reduce(lambda a, b: a*b // gcd(a, b), [value.denominator for value in self.values()]) - return self * lcm + return self * lcd def subs(self, symbol, expression=None): + """ + Substitute the given symbol by an expression and return the resulting + expression. Raise TypeError if the resulting expression is not linear. + + >>> x, y = symbols('x y') + >>> e = x + 2*y + 1 + >>> e.subs(y, x - 1) + 3*x - 1 + + To perform multiple substitutions at once, pass a sequence or a + dictionary of (old, new) pairs to subs. + + >>> e.subs({x: y, y: x}) + 2*x + y + 1 + """ if expression is None: - if isinstance(symbol, Mapping): - symbol = symbol.items() - substitutions = symbol + substitutions = dict(symbol) else: - substitutions = [(symbol, expression)] - result = self - for symbol, expression in substitutions: + substitutions = {symbol: expression} + for symbol in substitutions: if not isinstance(symbol, Symbol): raise TypeError('symbols must be Symbol instances') - coefficients = [(othersymbol, coefficient) - for othersymbol, coefficient in result._coefficients.items() - if othersymbol != symbol] - coefficient = result._coefficients.get(symbol, 0) - constant = result._constant - result = Expression(coefficients, constant) + coefficient*expression + result = self._constant + for symbol, coefficient in self._coefficients.items(): + expression = substitutions.get(symbol, symbol) + result += coefficient * expression return result @classmethod @@ -240,14 +337,21 @@ class Expression: return left / right raise SyntaxError('invalid syntax') - _RE_NUM_VAR = re.compile(r'(\d+|\))\s*([^\W\d_]\w*|\()') + _RE_NUM_VAR = re.compile(r'(\d+|\))\s*([^\W\d]\w*|\()') @classmethod def fromstring(cls, string): - # add implicit multiplication operators, e.g. '5x' -> '5*x' - string = Expression._RE_NUM_VAR.sub(r'\1*\2', string) + """ + Create an expression from a string. Raise SyntaxError if the string is + not properly formatted. + """ + # Add implicit multiplication operators, e.g. '5x' -> '5*x'. + string = LinExpr._RE_NUM_VAR.sub(r'\1*\2', string) tree = ast.parse(string, 'eval') - return cls._fromast(tree) + expression = cls._fromast(tree) + if not isinstance(expression, cls): + raise SyntaxError('invalid syntax') + return expression def __repr__(self): string = '' @@ -273,30 +377,6 @@ class Expression: string += ' - {}'.format(-constant) return string - def _repr_latex_(self): - string = '' - for i, (symbol, coefficient) in enumerate(self.coefficients()): - if coefficient == 1: - if i != 0: - string += ' + ' - elif coefficient == -1: - string += '-' if i == 0 else ' - ' - elif i == 0: - string += '{}'.format(coefficient._repr_latex_().strip('$')) - elif coefficient > 0: - string += ' + {}'.format(coefficient._repr_latex_().strip('$')) - elif coefficient < 0: - string += ' - {}'.format((-coefficient)._repr_latex_().strip('$')) - string += '{}'.format(symbol._repr_latex_().strip('$')) - constant = self.constant - if len(string) == 0: - string += '{}'.format(constant._repr_latex_().strip('$')) - elif constant > 0: - string += ' + {}'.format(constant._repr_latex_().strip('$')) - elif constant < 0: - string += ' - {}'.format((-constant)._repr_latex_().strip('$')) - return '$${}$$'.format(string) - def _parenstr(self, always=False): string = str(self) if not always and (self.isconstant() or self.issymbol()): @@ -305,106 +385,168 @@ class Expression: return '({})'.format(string) @classmethod - def fromsympy(cls, expr): + def fromsympy(cls, expression): + """ + Create a linear expression from a SymPy expression. Raise TypeError is + the sympy expression is not linear. + """ import sympy coefficients = [] constant = 0 - for symbol, coefficient in expr.as_coefficients_dict().items(): + for symbol, coefficient in expression.as_coefficients_dict().items(): coefficient = Fraction(coefficient.p, coefficient.q) if symbol == sympy.S.One: constant = coefficient + elif isinstance(symbol, sympy.Dummy): + # We cannot properly convert dummy symbols with respect to + # symbol equalities. + raise TypeError('cannot convert dummy symbols') elif isinstance(symbol, sympy.Symbol): symbol = Symbol(symbol.name) coefficients.append((symbol, coefficient)) else: - raise ValueError('non-linear expression: {!r}'.format(expr)) - return Expression(coefficients, constant) + raise TypeError('non-linear expression: {!r}'.format(expression)) + expression = LinExpr(coefficients, constant) + if not isinstance(expression, cls): + raise TypeError('cannot convert to a {} instance'.format(cls.__name__)) + return expression def tosympy(self): + """ + Convert the linear expression to a SymPy expression. + """ import sympy - expr = 0 + expression = 0 for symbol, coefficient in self.coefficients(): term = coefficient * sympy.Symbol(symbol.name) - expr += term - expr += self.constant - return expr + expression += term + expression += self.constant + return expression + + +class Symbol(LinExpr): + """ + Symbols are the basic components to build expressions and constraints. + They correspond to mathematical variables. Symbols are instances of + class LinExpr and inherit its functionalities. + Two instances of Symbol are equal if they have the same name. + """ -class Symbol(Expression): + __slots__ = ( + '_name', + '_constant', + '_symbols', + '_dimension', + ) def __new__(cls, name): + """ + Return a symbol with the name string given in argument. + """ if not isinstance(name, str): raise TypeError('name must be a string') + node = ast.parse(name) + try: + name = node.body[0].value.id + except (AttributeError, SyntaxError): + raise SyntaxError('invalid syntax') self = object().__new__(cls) - self._name = name.strip() - self._coefficients = {self: Fraction(1)} + self._name = name self._constant = Fraction(0) self._symbols = (self,) self._dimension = 1 return self + @property + def _coefficients(self): + # This is not implemented as an attribute, because __hash__ is not + # callable in __new__ in class Dummy. + return {self: Fraction(1)} + @property def name(self): + """ + The name of the symbol. + """ return self._name def __hash__(self): return hash(self.sortkey()) def sortkey(self): + """ + Return a sorting key for the symbol. It is useful to sort a list of + symbols in a consistent order, as comparison functions are overridden + (see the documentation of class LinExpr). + + >>> sort(symbols, key=Symbol.sortkey) + """ return self.name, def issymbol(self): return True def __eq__(self, other): - return self.sortkey() == other.sortkey() + if isinstance(other, Symbol): + return self.sortkey() == other.sortkey() + return NotImplemented def asdummy(self): + """ + Return a new Dummy symbol instance with the same name. + """ return Dummy(self.name) - @classmethod - def _fromast(cls, node): - if isinstance(node, ast.Module) and len(node.body) == 1: - return cls._fromast(node.body[0]) - elif isinstance(node, ast.Expr): - return cls._fromast(node.value) - elif isinstance(node, ast.Name): - return Symbol(node.id) - raise SyntaxError('invalid syntax') - def __repr__(self): return self.name - def _repr_latex_(self): - return '$${}$$'.format(self.name) - @classmethod - def fromsympy(cls, expr): - import sympy - if isinstance(expr, sympy.Dummy): - return Dummy(expr.name) - elif isinstance(expr, sympy.Symbol): - return Symbol(expr.name) - else: - raise TypeError('expr must be a sympy.Symbol instance') +def symbols(names): + """ + This function returns a tuple of symbols whose names are taken from a comma + or whitespace delimited string, or a sequence of strings. It is useful to + define several symbols at once. + + >>> x, y = symbols('x y') + >>> x, y = symbols('x, y') + >>> x, y = symbols(['x', 'y']) + """ + if isinstance(names, str): + names = names.replace(',', ' ').split() + return tuple(Symbol(name) for name in names) class Dummy(Symbol): + """ + A variation of Symbol in which all symbols are unique and identified by + an internal count index. If a name is not supplied then a string value + of the count index will be used. This is useful when a unique, temporary + variable is needed and the name of the variable used in the expression + is not important. + + Unlike Symbol, Dummy instances with the same name are not equal: + + >>> x = Symbol('x') + >>> x1, x2 = Dummy('x'), Dummy('x') + >>> x == x1 + False + >>> x1 == x2 + False + >>> x1 == x1 + True + """ _count = 0 def __new__(cls, name=None): + """ + Return a fresh dummy symbol with the name string given in argument. + """ if name is None: name = 'Dummy_{}'.format(Dummy._count) - elif not isinstance(name, str): - raise TypeError('name must be a string') - self = object().__new__(cls) + self = super().__new__(cls, name) self._index = Dummy._count - self._name = name.strip() - self._coefficients = {self: Fraction(1)} - self._constant = Fraction(0) - self._symbols = (self,) - self._dimension = 1 Dummy._count += 1 return self @@ -417,17 +559,21 @@ class Dummy(Symbol): def __repr__(self): return '_{}'.format(self.name) - def _repr_latex_(self): - return '$${}_{{{}}}$$'.format(self.name, self._index) - - -def symbols(names): - if isinstance(names, str): - names = names.replace(',', ' ').split() - return tuple(Symbol(name) for name in names) +class Rational(LinExpr, Fraction): + """ + A particular case of linear expressions are rational values, i.e. linear + expressions consisting only of a constant term, with no symbol. They are + implemented by the Rational class, that inherits from both LinExpr and + fractions.Fraction classes. + """ -class Rational(Expression, Fraction): + __slots__ = ( + '_coefficients', + '_constant', + '_symbols', + '_dimension', + ) + Fraction.__slots__ def __new__(cls, numerator=0, denominator=None): self = object().__new__(cls) @@ -457,23 +603,3 @@ class Rational(Expression, Fraction): return '{!r}'.format(self.numerator) else: return '{!r}/{!r}'.format(self.numerator, self.denominator) - - def _repr_latex_(self): - if self.denominator == 1: - return '$${}$$'.format(self.numerator) - elif self.numerator < 0: - return '$$-\\frac{{{}}}{{{}}}$$'.format(-self.numerator, - self.denominator) - else: - return '$$\\frac{{{}}}{{{}}}$$'.format(self.numerator, - self.denominator) - - @classmethod - def fromsympy(cls, expr): - import sympy - if isinstance(expr, sympy.Rational): - return Rational(expr.p, expr.q) - elif isinstance(expr, numbers.Rational): - return Rational(expr) - else: - raise TypeError('expr must be a sympy.Rational instance')