index aedf170..82d75d0 100644 (file)
@@ -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 + 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:
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,6 +116,10 @@ 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))
@@ -89,31 +127,58 @@ class Expression:
__getitem__ = coefficient

def coefficients(self):
+        """
+        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)

@property
def constant(self):
+        """
+        The constant term of the expression.
+        """
return Rational(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):
+        """
+        Iterate over the coefficient values in the expression, and the constant
+        term.
+        """
for coefficient in self._coefficients.values():
yield Rational(coefficient)
yield Rational(self._constant)
@@ -129,49 +194,62 @@ class Expression:

@_polymorphic
+        """
+        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)

@_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 \
+        """
+        Test whether two linear expressions are equal.
+        """
+        return isinstance(other, LinExpr) and \
self._coefficients == other._coefficients and \
self._constant == other._constant

@@ -192,11 +270,30 @@ class Expression:
return Gt(self, other)

def scaleint(self):
+        """
+        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()])
return self * lcm

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()
@@ -212,7 +309,7 @@ class Expression:
if othersymbol != symbol]
coefficient = result._coefficients.get(symbol, 0)
constant = result._constant
-            result = Expression(coefficients, constant) + coefficient*expression
+            result = LinExpr(coefficients, constant) + coefficient*expression
return result

@classmethod
@@ -244,8 +341,12 @@ class Expression:

@classmethod
def fromstring(cls, 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 = Expression._RE_NUM_VAR.sub(r'\1*\2', string)
+        string = LinExpr._RE_NUM_VAR.sub(r'\1*\2', string)
tree = ast.parse(string, 'eval')
return cls._fromast(tree)

@@ -306,6 +407,10 @@ class Expression:

@classmethod
def fromsympy(cls, expr):
+        """
+        Create a linear expression from a sympy expression. Raise ValueError is
+        the sympy expression is not linear.
+        """
import sympy
coefficients = []
constant = 0
@@ -318,9 +423,12 @@ class Expression:
coefficients.append((symbol, coefficient))
else:
raise ValueError('non-linear expression: {!r}'.format(expr))
-        return Expression(coefficients, constant)
+        return LinExpr(coefficients, constant)

def tosympy(self):
+        """
+        Convert the linear expression to a sympy expression.
+        """
import sympy
expr = 0
for symbol, coefficient in self.coefficients():
@@ -330,9 +438,19 @@ class Expression:
return expr

-class Symbol(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.
+    """

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')
self = object().__new__(cls)
@@ -345,12 +463,22 @@ class Symbol(Expression):

@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):
@@ -360,6 +488,9 @@ class Symbol(Expression):
return self.sortkey() == other.sortkey()

def asdummy(self):
+        """
+        Return a new Dummy symbol instance with the same name.
+        """
return Dummy(self.name)

@classmethod
@@ -390,10 +521,31 @@ class Symbol(Expression):

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):
@@ -422,12 +574,27 @@ class Dummy(Symbol):

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 Rational(Expression, Fraction):
+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.
+    """

def __new__(cls, numerator=0, denominator=None):
self = object().__new__(cls)