Mention that we use Z-polyhedra
[linpy.git] / doc / reference.rst
index af5cd4d..56986c5 100644 (file)
@@ -1,7 +1,12 @@
 
+.. _reference:
+
 Module Reference
 ================
 
+
+.. _reference_symbols:
+
 Symbols
 -------
 
@@ -67,6 +72,8 @@ This is achieved using ``Dummy('x')``.
     True
 
 
+.. _reference_linexprs:
+
 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)
-              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.
 
-    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)
@@ -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:
 
-    >>> LinExpr('x + 2*y + 1')
+    >>> LinExpr('x + 2y + 1')
 
     :class:`LinExpr` instances are hashable, and should be treated as immutable.
 
@@ -103,7 +110,7 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
     A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.
 
     .. method:: coefficient(symbol)
-                   __getitem__(symbol)
+                __getitem__(symbol)
 
         Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.
 
@@ -148,37 +155,38 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
 
     .. method:: __mul__(value)
 
-        Return the product of the linear expression as a rational.
+        Return the product of the linear expression by a rational.
 
     .. method:: __truediv__(value)
 
-        Return the quotient of the linear expression as a rational.
+        Return the quotient of the linear expression by a rational.
 
     .. 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.
 
     .. method:: __lt__(expr)
-                   __le__(expr)
-                   __ge__(expr)
-                   __gt__(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)
-
+        x + 1 <= y
 
     .. method:: scaleint()
 
         Return the expression multiplied by its lowest common denominator to make all values integer.
 
     .. method:: subs(symbol, expression)
-                   subs(pairs)
+                subs(pairs)
 
         Substitute the given symbol by an expression and return the resulting expression.
         Raise :exc:`TypeError` if the resulting expression is not linear.
@@ -203,7 +211,7 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
     .. classmethod:: fromsympy(expr)
 
         Create a linear expression from a :mod:`sympy` expression.
-        Raise :exc:`ValueError` is the :mod:`sympy` expression is not linear.
+        Raise :exc:`TypeError` is the :mod:`sympy` expression is not linear.
 
     .. method:: tosympy()
 
@@ -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)
-              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`.
@@ -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.
 
+
+.. _reference_polyhedra:
+
 Polyhedra
 ---------
 
-A *convex polyhedron* (or simply polyhedron) is the space defined by a system of linear equalities and inequalities.
+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)
-              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')
-    >>> 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')
-    >>> 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.
 
-    >>> 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:
 
-    >>> 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.
@@ -278,9 +293,19 @@ This space can be unbounded.
         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.
+        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
@@ -291,32 +316,35 @@ This space can be unbounded.
 
     The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
 
+
+.. _reference_domains:
+
 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)
-              Domain(string)
-              Domain(geometric object)
+           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])
+    >>> 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:
 
-    >>> 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.
 
@@ -329,7 +357,7 @@ Unlike polyhedra, domains allow exact computation of union and complementary ope
 
     .. attribute:: symbols
 
-        The tuple of symbols present in the domain expression, sorted according to :meth:`Symbol.sortkey`.
+        The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.
 
     .. attribute:: dimension
 
@@ -435,7 +463,7 @@ Unlike polyhedra, domains allow exact computation of union and complementary ope
 
     .. method:: __contains__(point)
 
-        Return ``True`` if the :class:`Point` is contained within the domain.
+        Return ``True`` if the point is contained within the domain.
 
     .. method:: faces()
 
@@ -473,10 +501,12 @@ Unlike polyhedra, domains allow exact computation of union and complementary ope
         Convert the domain to a sympy expression.
 
 
+.. _reference_operators:
+
 Comparison and Logic Operators
 ------------------------------
 
-The following functions create :class:`Polyhedron` or :class:`Domain` instances by comparison of :class:`LinExpr` instances:
+The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:
 
 .. function:: Lt(expr1, expr2[, expr3, ...])
 
@@ -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 ...``.
-    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, ...])
 
@@ -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:
 
-.. 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:: 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.
 
 
+.. _reference_geometry:
+
 Geometric Objects
 -----------------
 
@@ -567,7 +599,7 @@ Geometric Objects
         The dimension of the point, i.e. the number of symbols present in it.
 
     .. method:: coordinate(symbol)
-                   __getitem__(symbol)
+                __getitem__(symbol)
 
         Return the coordinate value of the given symbol.
         Raise :exc:`KeyError` if the symbol is not involved in the point.
@@ -590,10 +622,10 @@ Geometric Objects
 
     .. method:: __add__(vector)
 
-        Translate the point by a :class:`Vector` instance and return the resulting point.
+        Translate the point by a :class:`Vector` object and return the resulting point.
 
     .. method:: __sub__(point)
-                   __sub__(vector)
+                __sub__(vector)
 
         The first version substracts a point from another and returns the resulting vector.
         The second version translates the point by the opposite vector of *vector* and returns the resulting point.
@@ -604,9 +636,10 @@ Geometric Objects
 
 
 .. class:: Vector(coordinates)
+           Vector(point1, point2)
 
-    Create a point from a dictionary or a sequence that maps the symbols to their coordinates, similar to :meth:`Point`.
-    Coordinates must be rational numbers.
+    The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
+    The second version creates a vector between two points.
 
     :class:`Vector` instances are hashable and should be treated as immutable.
 
@@ -619,7 +652,7 @@ Geometric Objects
         The dimension of the point, i.e. the number of symbols present in it.
 
     .. method:: coordinate(symbol)
-                   __getitem__(symbol)
+                __getitem__(symbol)
 
         Return the coordinate value of the given symbol.
         Raise :exc:`KeyError` if the symbol is not involved in the point.
@@ -641,13 +674,13 @@ Geometric Objects
         Return ``True`` if not all coordinates are ``0``.
 
     .. method:: __add__(point)
-                   __add__(vector)
+                __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)
+                __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.
@@ -656,6 +689,18 @@ Geometric Objects
 
         Return the opposite vector.
 
+    .. 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:: __eq__(vector)
+
+        Test whether two vectors are equal.
+
     .. method:: angle(vector)
 
         Retrieve the angle required to rotate the vector into the vector passed in argument.
@@ -664,31 +709,19 @@ Geometric Objects
     .. 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)
 
         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.
+        Return the squared norm of the vector.
 
     .. method:: asunit()