+
+Module Reference
+================
+
+Symbols
+-------
+
+*Symbols* are the basic components to build expressions and constraints.
+They correspond to mathematical variables.
+
+.. class:: Symbol(name)
+
+ Return a symbol with the name string given in argument.
+ Alternatively, the function :func:`symbols` allows to create several symbols at once.
+ Symbols are instances of class :class:`LinExpr` and, as such, inherit its functionalities.
+
+ >>> x = Symbol('x')
+ >>> x
+ x
+
+ Two instances of :class:`Symbol` are equal if they have the same name.
+
+ .. attribute:: name
+
+ The name of the symbol.
+
+ .. method:: asdummy()
+
+ Return a new :class:`Dummy` symbol instance with the same name.
+
+ .. method:: sortkey()
+
+ 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 :class:`LinExpr`).
+
+ >>> sort(symbols, key=Symbol.sortkey)
+
+
+.. function:: 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'])
+
+
+Sometimes, you need to have a unique symbol, for example as a temporary one in some calculation, which is going to be substituted for something else at the end anyway.
+This is achieved using ``Dummy('x')``.
+
+.. class:: Dummy(name=None)
+
+ A variation of :class:`Symbol` which are all unique, 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 :class:`Symbol`, :class:`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
+
+
+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 :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`.
+
+.. class:: LinExpr(coefficients=None, constant=0)
+ LinExpr(string)
+
+ 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 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)
+
+ although 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')
+
+ :class:`LinExpr` instances are hashable, and should be treated as immutable.
+
+ A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance.
+ A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.
+
+ .. method:: coefficient(symbol)
+ __getitem__(symbol)
+
+ Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.
+
+ .. method:: coefficients()
+
+ Iterate over the pairs ``(symbol, value)`` of linear terms in the expression.
+ The constant term is ignored.
+
+ .. attribute:: constant
+
+ The constant term of the expression.
+
+ .. attribute:: symbols
+
+ The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`.
+
+ .. attribute:: dimension
+
+ The dimension of the expression, i.e. the number of symbols present in it.
+
+ .. method:: isconstant()
+
+ Return ``True`` if the expression only consists of a constant term.
+ In this case, it is a :class:`Rational` instance.
+
+ .. method:: issymbol()
+
+ Return ``True`` if an expression only consists of a symbol with coefficient ``1``.
+ In this case, it is a :class:`Symbol` instance.
+
+ .. method:: values()
+
+ Iterate over the coefficient values in the expression, and the constant term.
+
+ .. method:: __add__(expr)
+
+ Return the sum of two linear expressions.
+
+ .. method:: __sub__(expr)
+
+ Return the difference between two linear expressions.
+
+ .. method:: __mul__(value)
+
+ Return the product of the linear expression by a rational.
+
+ .. method:: __truediv__(value)
+
+ Return the quotient of the linear expression by a rational.
+
+ .. method:: __eq__(expr)
+
+ Test whether two linear expressions are equal.
+
+ As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
+
+ .. method:: __lt__(expr)
+ __le__(expr)
+ __ge__(expr)
+ __gt__(expr)
+
+ Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
+ As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.
+
+ >>> x, y = symbols('x y')
+ >>> x < y
+ Le(x - y + 1, 0)
+
+
+ .. method:: scaleint()
+
+ Return the expression multiplied by its lowest common denominator to make all values integer.
+
+ .. method:: subs(symbol, expression)
+ subs(pairs)
+
+ Substitute the given symbol by an expression and return the resulting expression.
+ Raise :exc:`TypeError` is 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
+
+ .. classmethod:: fromstring(string)
+
+ Create an expression from a string.
+ Raise :exc:`SyntaxError` if the string is not properly formatted.
+
+ There are also methods to convert linear expressions to and from `SymPy <http://sympy.org>`_ expressions:
+
+ .. classmethod:: fromsympy(expr)
+
+ Create a linear expression from a :mod:`sympy` expression.
+ Raise :exc:`ValueError` is the :mod:`sympy` expression is not linear.
+
+ .. method:: tosympy()
+
+ Convert the linear expression to a sympy expression.
+
+
+Apart from :mod:`Symbol`, 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 :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
+
+.. class:: Rational(numerator, denominator=1)
+ Rational(string)
+
+ The first version requires that *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with value ``numerator/denominator``.
+ If denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
+ The other version of the constructor expects a string.
+ The usual form for this instance is::
+
+ [sign] numerator ['/' denominator]
+
+ where the optional ``sign`` may be either '+' or '-' and ``numerator`` and ``denominator`` (if present) are strings of decimal digits.
+
+ See the documentation of :class:`fractions.Fraction` for more information and examples.
+
+Polyhedra
+---------
+
+A *convex polyhedron* (or simply polyhedron) is the space defined by a system of linear equalities and inequalities.
+This space can be unbounded.
+
+.. class:: Polyhedron(equalities, inequalities)
+ Polyhedron(string)
+ Polyhedron(geometric object)
+
+ 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])
+
+ It may be easier to use comparison operators :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, or functions :func:`Lt`, :func:`Le`, :func:`Eq`, :func:`Ge` and :func:`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)
+
+ It is also possible to build a polyhedron from a string.
+
+ >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
+
+ Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
+ This way, it is possible to compute the polyhedral hull of a :class:`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)
+
+ A polyhedron is a :class:`Domain` instance, and, as such, inherits the functionalities of this class.
+ It is also a :class:`GeometricObject` instance.
+
+ .. attribute:: equalities
+
+ The tuple of equalities.
+ This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.
+
+ .. attribute:: inequalities
+
+ The tuple of inequalities.
+ This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.
+
+ .. attribute:: constraints
+
+ The tuple of constraints, i.e., equalities and inequalities.
+ This is semantically equivalent to: ``equalities + inequalities``.
+
+ .. method:: widen(polyhedron)
+
+ Compute the standard widening of two polyhedra, à la Halbwachs.
+
+
+.. data:: Empty
+
+ The empty polyhedron, whose set of constraints is not satisfiable.
+
+.. data:: Universe
+
+ The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
+
+Domains
+-------
+
+A *domain* is a union of polyhedra.
+Unlike polyhedra, domains allow exact computation of union and complementary operations.
+
+.. class:: Domain(*polyhedra)
+ Domain(string)
+ Domain(geometric object)
+
+ Return a domain from a sequence of polyhedra.
+
+ >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
+ >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
+ >>> dom = Domain([square, square2])
+
+ It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__and__`, :meth:`Domain.__or__` or functions :func:`And` and :func:`Or`, using one of the following instructions:
+
+ >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
+ >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
+ >>> dom = square | square2
+ >>> dom = Or(square, square2)
+
+ Alternatively, a domain can be built from a string:
+
+ >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')
+
+ Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
+
+ A domain is also a :class:`GeometricObject` instance.
+ A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
+
+ .. attribute:: polyhedra
+
+ The tuple of polyhedra present in the domain.
+
+ .. attribute:: symbols
+
+ The tuple of symbols present in the domain expression, sorted according to :meth:`Symbol.sortkey`.
+
+ .. attribute:: dimension
+
+ The dimension of the domain, i.e. the number of symbols present in it.
+
+ .. method:: isempty()
+
+ Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
+
+ .. method:: __bool__()
+
+ Return ``True`` if the domain is non-empty.
+
+ .. method:: isuniverse()
+
+ Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
+
+ .. method:: isbounded()
+
+ Return ``True`` is the domain is bounded.
+
+ .. method:: __eq__(domain)
+
+ Return ``True`` if two domains are equal.
+
+ .. method:: isdisjoint(domain)
+
+ Return ``True`` if two domains have a null intersection.
+
+ .. method:: issubset(domain)
+ __le__(domain)
+
+ Report whether another domain contains the domain.
+
+ .. method:: __lt__(domain)
+
+ Report whether another domain is contained within the domain.
+
+ .. method:: complement()
+ __invert__()
+
+ Return the complementary domain of the domain.
+
+ .. method:: make_disjoint()
+
+ Return an equivalent domain, whose polyhedra are disjoint.
+
+ .. method:: coalesce()
+
+ Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
+
+ .. method:: detect_equalities()
+
+ Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
+
+ .. method:: remove_redundancies()
+
+ Remove redundant constraints in the domain, and return the resulting domain.
+
+ .. method:: project(symbols)
+
+ Project out the sequence of symbols given in arguments, and return the resulting domain.
+
+ .. method:: sample()
+
+ Return a sample of the domain, as an integer instance of :class:`Point`.
+ If the domain is empty, a :exc:`ValueError` exception is raised.
+
+ .. method:: intersection(domain[, ...])
+ __and__(domain)
+
+ Return the intersection of two or more domains as a new domain.
+ As an alternative, function :func:`And` can be used.
+
+ .. method:: union(domain[, ...])
+ __or__(domain)
+ __add__(domain)
+
+ Return the union of two or more domains as a new domain.
+ As an alternative, function :func:`Or` can be used.
+
+ .. method:: difference(domain)
+ __sub__(domain)
+
+ Return the difference between two domains as a new domain.
+
+ .. method:: lexmin()
+
+ Return the lexicographic minimum of the elements in the domain.
+
+ .. method:: lexmax()
+
+ Return the lexicographic maximum of the elements in the domain.
+
+ .. method:: vertices()
+
+ Return the vertices of the domain, as a list of rational instances of :class:`Point`.
+
+ .. method:: points()
+
+ Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
+ If the domain is not bounded, a :exc:`ValueError` exception is raised.
+
+ .. method:: __contains__(point)
+
+ Return ``True`` if the :class:`Point` is contained within the domain.
+
+ .. method:: faces()
+
+ Return the list of faces of a bounded domain.
+ Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
+ If the domain is not bounded, a :exc:`ValueError` exception is raised.
+
+ .. method:: plot(plot=None, **options)
+
+ Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
+ Draw it to the current *plot* object if present, otherwise create a new one.
+ *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
+ Raise :exc:`ValueError` is the domain is not 2D or 3D.
+
+ .. method:: subs(symbol, expression)
+ subs(pairs)
+
+ Substitute the given symbol by an expression in the domain constraints.
+ To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
+ The syntax of this function is similar to :func:`LinExpr.subs`.
+
+ .. classmethod:: fromstring(string)
+
+ Create a domain from a string.
+ Raise :exc:`SyntaxError` if the string is not properly formatted.
+
+ There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:
+
+ .. classmethod:: fromsympy(expr)
+
+ Create a domain from a sympy expression.
+
+ .. method:: tosympy()
+
+ Convert the domain to a sympy expression.
+
+
+Comparison and Logic Operators
+------------------------------
+
+The following functions allow to create :class:`Polyhedron` or :class:`Domain` instances by comparison of :class:`LinExpr` instances:
+
+.. function:: Lt(expr1, expr2[, expr3, ...])
+
+ Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
+
+.. function:: Le(expr1, expr2[, expr3, ...])
+
+ Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
+
+.. function:: Eq(expr1, expr2[, expr3, ...])
+
+ Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
+
+.. function:: Ne(expr1, expr2[, expr3, ...])
+
+ Create the domain such that ``expr1 != expr2 != expr3 ...``.
+ The result is a :class:`Domain`, not a :class:`Polyhedron`.
+
+.. function:: Ge(expr1, expr2[, expr3, ...])
+
+ Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
+
+.. function:: Gt(expr1, expr2[, expr3, ...])
+
+ Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
+
+The following functions allow to combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
+
+.. function:: Or(domain1, domain2[, ...])
+
+ Create the union domain of domains given in arguments.
+
+.. function:: And(domain1, domain2[, ...])
+
+ Create the intersection domain of domains given in arguments.
+
+.. function:: Not(domain)
+
+ Create the complementary domain of the domain given in argument.
+
+
+Geometric Objects
+-----------------
+
+.. class:: GeometricObject
+
+ :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
+ Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
+ The following elements must be provided:
+
+ .. attribute:: symbols
+
+ The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
+
+ .. attribute:: dimension
+
+ The dimension of the object, i.e. the number of symbols present in it.
+
+ .. method:: aspolyedron()
+
+ Return a :class:`Polyhedron` object that approximates the geometric object.
+
+ .. method:: asdomain()
+
+ Return a :class:`Domain` object that approximates the geometric object.
+
+.. class:: Point(coordinates)
+
+ Create a point from a dictionnary or a sequence that maps symbols to their coordinates.
+ Coordinates must be rational numbers.
+
+ For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
+
+ >>> x, y = symbols('x y')
+ >>> p = Point({x: 1, y: 2})
+ >>> p = Point([(x, 1), (y, 2)])
+
+ :class:`Point` instances are hashable, and should be treated as immutable.
+
+ A point is a :class:`GeometricObject` instance.
+
+ .. attribute:: symbols
+
+ The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
+
+ .. attribute:: dimension
+
+ The dimension of the point, i.e. the number of symbols present in it.
+
+ .. method:: coordinate(symbol)
+ __getitem__(symbol)
+
+ Return the coordinate value of the given symbol.
+ Raise :exc:`KeyError` if the symbol is not involved in the point.
+
+ .. method:: coordinates()
+
+ Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
+
+ .. method:: values()
+
+ Iterate over the coordinate values in the point.
+
+ .. method:: isorigin()
+
+ Return ``True`` if all coordinates are ``0``.
+
+ .. method:: __bool__()
+
+ Return ``True`` if not all coordinates are ``0``.
+
+ .. method:: __add__(vector)
+
+ Translate the point by a :class:`Vector` instance and return the resulting point.
+
+ .. method:: __sub__(point)
+ __sub__(vector)
+
+ The first version substract a point from another and return the resulting vector.
+ The second version translates the point by the opposite vector of *vector* and returns the resulting point.
+
+ .. method:: __eq__(point)
+
+ Test whether two points are equal.
+
+
+.. class:: Vector(coordinates)
+
+ Create a point from a dictionnary or a sequence that maps symbols to their coordinates, similarly to :meth:`Point`.
+ Coordinates must be rational numbers.
+
+ :class:`Vector` instances are hashable, and should be treated as immutable.
+
+ .. attribute:: symbols
+
+ The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
+
+ .. attribute:: dimension
+
+ The dimension of the point, i.e. the number of symbols present in it.
+
+ .. method:: coordinate(symbol)
+ __getitem__(symbol)
+
+ Return the coordinate value of the given symbol.
+ Raise :exc:`KeyError` if the symbol is not involved in the point.
+
+ .. method:: coordinates()
+
+ Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
+
+ .. method:: values()
+
+ Iterate over the coordinate values in the point.
+
+ .. method:: isnull()
+
+ Return ``True`` if all coordinates are ``0``.
+
+ .. method:: __bool__()
+
+ Return ``True`` if not all coordinates are ``0``.
+
+ .. method:: __add__(point)
+ __add__(vector)
+
+ The first version translates the point *point* to the vector and returns the resulting point.
+ The second version adds vector *vector* to the vector and returns the resulting vector.
+
+ .. method:: __sub__(point)
+ __sub__(vector)
+
+ The first version substracts a point from a vector and returns the resulting point.
+ The second version returns the difference vector between two vectors.
+
+ .. method:: __neg__()
+
+ Return the opposite vector.
+
+ .. method:: angle(vector)
+
+ Retrieve the angle required to rotate the vector into the vector passed in argument.
+ The result is an angle in radians, ranging between ``-pi`` and ``pi``.
+
+ .. method:: cross(vector)
+
+ Compute the cross product of two 3D vectors.
+ If either one of the vectors is not tridimensional, a :exc:`ValueError` exception is raised.
+
+ .. method:: dot(vector)
+
+ Compute the dot product of two vectors.
+
+ .. method:: __eq__(vector)
+
+ Test whether two vectors are equal.
+
+ .. method:: __mul__(value)
+
+ Multiply the vector by a scalar value and return the resulting vector.
+
+ .. method:: __truediv__(value)
+
+ Divide the vector by a scalar value and return the resulting vector.
+
+ .. method:: norm()
+
+ Return the norm of the vector.
+
+ .. method:: norm2()
+
+ Return the square norm of the vector.
+
+ .. method:: asunit()
+
+ Return the normalized vector, i.e. the vector of same direction but with norm 1.
projects / linpy.git / commitdiff