X-Git-Url: https://scm.cri.ensmp.fr/git/linpy.git/blobdiff_plain/454a26a54cc7ff563ab278567f3bbad9c6ff42bb..a08ebc700e22f6aee8147cb5b5323a6c040b12db:/doc/reference.rst diff --git a/doc/reference.rst b/doc/reference.rst new file mode 100644 index 0000000..8184c43 --- /dev/null +++ b/doc/reference.rst @@ -0,0 +1,695 @@ + +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 `_ 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 `_. + 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 `_ 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.