Version 1.0.3
[linpy.git] / doc / reference.rst
index de5300d..56986c5 100644 (file)
@@ -1,7 +1,12 @@
 
 
+.. _reference:
+
 Module Reference
 ================
 
 Module Reference
 ================
 
+
+.. _reference_symbols:
+
 Symbols
 -------
 
 Symbols
 -------
 
@@ -67,6 +72,8 @@ This is achieved using ``Dummy('x')``.
     True
 
 
     True
 
 
+.. _reference_linexprs:
+
 Linear Expressions
 ------------------
 
 Linear Expressions
 ------------------
 
@@ -77,12 +84,12 @@ 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)
 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)
+           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 term must be rational numbers.
 
 
     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:
+    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)
 
     >>> x, y = symbols('x y')
     >>> LinExpr({x: 1, y: 2}, 1)
@@ -95,7 +102,7 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
 
     Alternatively, linear expressions can be constructed from a string:
 
 
     Alternatively, linear expressions can be constructed from a string:
 
-    >>> LinExpr('x + 2*y + 1')
+    >>> LinExpr('x + 2y + 1')
 
     :class:`LinExpr` instances are hashable, and should be treated as immutable.
 
 
     :class:`LinExpr` instances are hashable, and should be treated as immutable.
 
@@ -157,6 +164,8 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
     .. method:: __eq__(expr)
 
         Test whether two linear expressions are equal.
     .. method:: __eq__(expr)
 
         Test whether two linear expressions are equal.
+        Unlike methods :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, the result is a boolean value, not a polyhedron.
+        To express that two linear expressions are equal or not equal, use functions :func:`Eq` and :func:`Ne` instead.
 
     As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
 
 
     As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
 
@@ -170,8 +179,7 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
 
         >>> x, y = symbols('x y')
         >>> x < y
 
         >>> x, y = symbols('x y')
         >>> x < y
-        Le(x - y + 1, 0)
-
+        x + 1 <= y
 
     .. method:: scaleint()
 
 
     .. method:: scaleint()
 
@@ -214,7 +222,7 @@ Apart from :mod:`Symbol`, a particular case of linear expressions are rational v
 They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
 
 .. class:: Rational(numerator, denominator=1)
 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)
+           Rational(string)
 
     The first version requires that the *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with the value ``numerator/denominator``.
     If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
 
     The first version requires that the *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with the value ``numerator/denominator``.
     If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
@@ -227,38 +235,45 @@ They are implemented by the :class:`Rational` class, that inherits from both :cl
 
     See the documentation of :class:`fractions.Fraction` for more information and examples.
 
 
     See the documentation of :class:`fractions.Fraction` for more information and examples.
 
+
+.. _reference_polyhedra:
+
 Polyhedra
 ---------
 
 A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
 This space can be unbounded.
 Polyhedra
 ---------
 
 A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
 This space can be unbounded.
+A *Z-polyhedron* (simply called "polyhedron" in LinPy) is the set of integer points in a convex polyhedron.
 
 .. class:: Polyhedron(equalities, inequalities)
 
 .. class:: Polyhedron(equalities, inequalities)
-              Polyhedron(string)
-              Polyhedron(geometric object)
+           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')
 
     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])
+    >>> square1 = Polyhedron([], [x, 2 - x, y, 2 - y])
+    >>> square1
+    And(0 <= x, x <= 2, 0 <= y, y <= 2)
 
     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')
 
     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)
+    >>> square1 = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
+    >>> square1 = Le(0, x, 2) & Le(0, y, 2)
 
     It is also possible to build a polyhedron from a string.
 
 
     It is also possible to build a polyhedron from a string.
 
-    >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
+    >>> square1 = 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:
 
 
     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)
+    >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
+    >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
+    >>> Polyhedron(square1 | square2)
+    And(0 <= x, 0 <= y, x <= y + 2, y <= x + 2, x <= 3, y <= 3)
 
     A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
     It is also a :class:`GeometricObject` instance.
 
     A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
     It is also a :class:`GeometricObject` instance.
@@ -278,10 +293,20 @@ This space can be unbounded.
         The tuple of constraints, i.e., equalities and inequalities.
         This is semantically equivalent to: ``equalities + inequalities``.
 
         The tuple of constraints, i.e., equalities and inequalities.
         This is semantically equivalent to: ``equalities + inequalities``.
 
+    .. method:: convex_union(polyhedron[, ...])
+
+        Return the convex union of two or more polyhedra.
+
+    .. method:: asinequalities()
+
+        Express the polyhedron using inequalities, given as a list of expressions greater or equal to 0.
+
     .. method:: widen(polyhedron)
 
         Compute the *standard widening* of two polyhedra, à la Halbwachs.
 
     .. method:: widen(polyhedron)
 
         Compute the *standard widening* of two polyhedra, à la Halbwachs.
 
+        In its current implementation, this method is slow and should not be used on large polyhedra.
+
 
 .. data:: Empty
 
 
 .. data:: Empty
 
@@ -291,32 +316,35 @@ This space can be unbounded.
 
     The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
 
 
     The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
 
+
+.. _reference_domains:
+
 Domains
 -------
 
 A *domain* is a union of polyhedra.
 Domains
 -------
 
 A *domain* is a union of polyhedra.
-Unlike polyhedra, domains allow exact computation of union and complementary operations.
+Unlike polyhedra, domains allow exact computation of union, subtraction and complementary operations.
 
 .. class:: Domain(*polyhedra)
 
 .. class:: Domain(*polyhedra)
-              Domain(string)
-              Domain(geometric object)
+           Domain(string)
+           Domain(geometric object)
 
     Return a domain from a sequence of polyhedra.
 
 
     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])
+    >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
+    >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
+    >>> dom = Domain(square1, square2)
+    >>> dom
+    Or(And(x <= 2, 0 <= x, y <= 2, 0 <= y), And(x <= 3, 1 <= x, y <= 3, 1 <= y))
 
 
-    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:
+    It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__or__`, :meth:`Domain.__invert__` or functions :func:`Or` and :func:`Not`, 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)
+    >>> dom = square1 | square2
+    >>> dom = Or(square1, square2)
 
     Alternatively, a domain can be built from a string:
 
 
     Alternatively, a domain can be built from a string:
 
-    >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')
+    >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 1 <= x <= 3, 1 <= y <= 3')
 
     Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
 
 
     Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
 
@@ -473,6 +501,8 @@ Unlike polyhedra, domains allow exact computation of union and complementary ope
         Convert the domain to a sympy expression.
 
 
         Convert the domain to a sympy expression.
 
 
+.. _reference_operators:
+
 Comparison and Logic Operators
 ------------------------------
 
 Comparison and Logic Operators
 ------------------------------
 
@@ -493,7 +523,7 @@ The following functions create :class:`Polyhedron` or :class:`Domain` instances
 .. function:: Ne(expr1, expr2[, expr3, ...])
 
     Create the domain such that ``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`.
+    The result is a :class:`Domain` object, not a :class:`Polyhedron`.
 
 .. function:: Ge(expr1, expr2[, expr3, ...])
 
 
 .. function:: Ge(expr1, expr2[, expr3, ...])
 
@@ -505,19 +535,21 @@ The following functions create :class:`Polyhedron` or :class:`Domain` instances
 
 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
 
 
 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
 
-.. function:: Or(domain1, domain2[, ...])
-
-    Create the union domain of the domains given in arguments.
-
 .. function:: And(domain1, domain2[, ...])
 
     Create the intersection domain of the domains given in arguments.
 
 .. function:: And(domain1, domain2[, ...])
 
     Create the intersection domain of the domains given in arguments.
 
+.. function:: Or(domain1, domain2[, ...])
+
+    Create the union domain of the domains given in arguments.
+
 .. function:: Not(domain)
 
     Create the complementary domain of the domain given in argument.
 
 
 .. function:: Not(domain)
 
     Create the complementary domain of the domain given in argument.
 
 
+.. _reference_geometry:
+
 Geometric Objects
 -----------------
 
 Geometric Objects
 -----------------
 
@@ -677,7 +709,7 @@ Geometric Objects
     .. method:: cross(vector)
 
         Compute the cross product of two 3D vectors.
     .. 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.
+        If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.
 
     .. method:: dot(vector)
 
 
     .. method:: dot(vector)