X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/7afcb0a1ded9e9a331b131689d68c085f712143f..2e558859456a109279713a2cbdd6c48a70a171c6:/linpy/linexprs.py?ds=sidebyside diff --git a/linpy/linexprs.py b/linpy/linexprs.py index 8267be1..834c3b4 100644 --- a/linpy/linexprs.py +++ b/linpy/linexprs.py @@ -45,12 +45,43 @@ def _polymorphic(func): 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): """ - Create a new expression. + 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 + 2y + 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 + 2*y + 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: @@ -86,7 +117,8 @@ class LinExpr: def coefficient(self, symbol): """ - Return the coefficient value of the given 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') @@ -96,7 +128,8 @@ class LinExpr: def coefficients(self): """ - Return a list of the coefficients of an expression + Iterate over the pairs (symbol, value) of linear terms in the + expression. The constant term is ignored. """ for symbol, coefficient in self._coefficients.items(): yield symbol, Rational(coefficient) @@ -104,21 +137,23 @@ class LinExpr: @property def constant(self): """ - Return the constant value of an expression. + The constant term of the expression. """ return Rational(self._constant) @property def symbols(self): """ - Return a list of symbols in an expression. + The tuple of symbols present in the expression, sorted according to + Symbol.sortkey(). """ return self._symbols @property def dimension(self): """ - Create and return a new linear expression from a string or a list of coefficients and a constant. + The dimension of the expression, i.e. the number of symbols present in + it. """ return self._dimension @@ -127,19 +162,22 @@ class LinExpr: def isconstant(self): """ - Return true if an expression is a constant. + 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 is a symbol. + 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): """ - Return the coefficient and constant values of an expression. + Iterate over the coefficient values in the expression, and the constant + term. """ for coefficient in self._coefficients.values(): yield Rational(coefficient) @@ -157,7 +195,7 @@ class LinExpr: @_polymorphic def __add__(self, other): """ - Return the sum of two expressions. + Return the sum of two linear expressions. """ coefficients = defaultdict(Fraction, self._coefficients) for symbol, coefficient in other._coefficients.items(): @@ -170,7 +208,7 @@ class LinExpr: @_polymorphic def __sub__(self, other): """ - Return the difference between two expressions. + Return the difference between two linear expressions. """ coefficients = defaultdict(Fraction, self._coefficients) for symbol, coefficient in other._coefficients.items(): @@ -184,7 +222,7 @@ class LinExpr: def __mul__(self, other): """ - Return the product of two expressions if other is a rational number. + Return the product of the linear expression by a rational. """ if isinstance(other, numbers.Rational): coefficients = ((symbol, coefficient * other) @@ -196,6 +234,9 @@ class LinExpr: __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()) @@ -206,7 +247,7 @@ class LinExpr: @_polymorphic def __eq__(self, other): """ - Test whether two expressions are equal + Test whether two linear expressions are equal. """ return isinstance(other, LinExpr) and \ self._coefficients == other._coefficients and \ @@ -230,7 +271,8 @@ class LinExpr: def scaleint(self): """ - Multiply an expression by a scalar to make all coefficients integer values. + Return the expression multiplied by its lowest common denominator to + make all values integer. """ lcm = functools.reduce(lambda a, b: a*b // gcd(a, b), [value.denominator for value in self.values()]) @@ -238,8 +280,19 @@ class LinExpr: def subs(self, symbol, expression=None): """ - Subsitute symbol by expression in equations and return the resulting - expression. + 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): @@ -289,12 +342,16 @@ class LinExpr: @classmethod def fromstring(cls, string): """ - Create an expression from a 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) + expr = cls._fromast(tree) + if not isinstance(expr, cls): + raise SyntaxError('invalid syntax') + return expr def __repr__(self): string = '' @@ -354,7 +411,8 @@ class LinExpr: @classmethod def fromsympy(cls, expr): """ - Convert sympy object to an expression. + Create a linear expression from a sympy expression. Raise ValueError is + the sympy expression is not linear. """ import sympy coefficients = [] @@ -372,7 +430,7 @@ class LinExpr: def tosympy(self): """ - Return an expression as a sympy object. + Convert the linear expression to a sympy expression. """ import sympy expr = 0 @@ -384,15 +442,27 @@ class LinExpr: 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. + """ def __new__(cls, name): """ - Create and return a symbol from a string. + 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._name = name self._coefficients = {self: Fraction(1)} self._constant = Fraction(0) self._symbols = (self,) @@ -401,12 +471,22 @@ class Symbol(LinExpr): @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): @@ -417,20 +497,10 @@ class Symbol(LinExpr): def asdummy(self): """ - Return a symbol as a Dummy Symbol. + 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 @@ -450,13 +520,29 @@ class Symbol(LinExpr): class Dummy(Symbol): """ - This class returns a dummy symbol to ensure that no variables are repeated in an expression + 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): """ - Create and return a new dummy symbol. + Return a fresh dummy symbol with the name string given in argument. """ if name is None: name = 'Dummy_{}'.format(Dummy._count) @@ -487,7 +573,13 @@ class Dummy(Symbol): def symbols(names): """ - Transform strings into instances of the Symbol class + 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() @@ -496,7 +588,10 @@ def symbols(names): class Rational(LinExpr, Fraction): """ - This class represents integers and rational numbers of any size. + 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. """ def __new__(cls, numerator=0, denominator=None): @@ -514,15 +609,9 @@ class Rational(LinExpr, Fraction): @property def constant(self): - """ - Return rational as a constant. - """ return self def isconstant(self): - """ - Test whether a value is a constant. - """ return True def __bool__(self): @@ -546,9 +635,6 @@ class Rational(LinExpr, Fraction): @classmethod def fromsympy(cls, expr): - """ - Create a rational object from a sympy expression - """ import sympy if isinstance(expr, sympy.Rational): return Rational(expr.p, expr.q)