author Vivien Maisonneuve Mon, 18 Aug 2014 12:21:19 +0000 (14:21 +0200) committer Vivien Maisonneuve Mon, 18 Aug 2014 12:21:19 +0000 (14:21 +0200)
 doc/reference.rst patch | blob | history linpy/__init__.py patch | blob | history linpy/domains.py patch | blob | history linpy/geometry.py patch | blob | history linpy/linexprs.py patch | blob | history linpy/polyhedra.py patch | blob | history

index 20168e4..e0efdde 100644 (file)
@@ -103,7 +103,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)
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.

Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.

@@ -161,9 +161,9 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
As explained below, it is possible to create polyhedra from linear expressions using comparison methods.

.. method:: __lt__(expr)
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.

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.
@@ -178,7 +178,7 @@ For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :cl
Return the expression multiplied by its lowest common denominator to make all values integer.

.. method:: subs(symbol, expression)
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.

Substitute the given symbol by an expression and return the resulting expression.
Raise :exc:`TypeError` if the resulting expression is not linear.
@@ -280,7 +280,7 @@ This space can be unbounded.

.. method:: widen(polyhedron)

.. method:: widen(polyhedron)

-        Compute the standard widening of two polyhedra, à la Halbwachs.
+        Compute the *standard widening* of two polyhedra, à la Halbwachs.

.. data:: Empty

.. data:: Empty
@@ -329,7 +329,7 @@ Unlike polyhedra, domains allow exact computation of union and complementary ope

.. attribute:: symbols

.. 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

.. attribute:: dimension

@@ -435,7 +435,7 @@ Unlike polyhedra, domains allow exact computation of union and complementary ope

.. method:: __contains__(point)

.. 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()

.. method:: faces()

@@ -567,7 +567,7 @@ Geometric Objects
The dimension of the point, i.e. the number of symbols present in it.

.. method:: coordinate(symbol)
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.

Return the coordinate value of the given symbol.
Raise :exc:`KeyError` if the symbol is not involved in the point.
@@ -590,10 +590,10 @@ Geometric Objects

-        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)

.. 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.

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 +604,10 @@ Geometric Objects

.. class:: Vector(coordinates)

.. 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.

:class:`Vector` instances are hashable and should be treated as immutable.

@@ -619,7 +620,7 @@ Geometric Objects
The dimension of the point, i.e. the number of symbols present in it.

.. method:: coordinate(symbol)
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.

Return the coordinate value of the given symbol.
Raise :exc:`KeyError` if the symbol is not involved in the point.
@@ -641,13 +642,13 @@ Geometric Objects
Return ``True`` if not all coordinates are ``0``.

Return ``True`` if not all coordinates are ``0``.

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)

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.

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 +657,18 @@ Geometric Objects

Return the opposite vector.

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.
.. method:: angle(vector)

Retrieve the angle required to rotate the vector into the vector passed in argument.
@@ -670,25 +683,13 @@ Geometric Objects

Compute the dot product of two vectors.

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()

.. 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()

.. method:: asunit()

index 2fdc73e..1e32751 100644 (file)
@@ -19,7 +19,7 @@
A polyhedral library based on ISL
"""

A polyhedral library based on ISL
"""

-from .geometry import Point, Vector
+from .geometry import GeometricObject, Point, Vector
from .linexprs import LinExpr, Symbol, Dummy, symbols, Rational
from .polyhedra import Polyhedron, Eq, Ne, Le, Lt, Ge, Gt, Ne, Empty, Universe
from .domains import Domain, And, Or, Not
from .linexprs import LinExpr, Symbol, Dummy, symbols, Rational
from .polyhedra import Polyhedron, Eq, Ne, Le, Lt, Ge, Gt, Ne, Empty, Universe
from .domains import Domain, And, Or, Not
@@ -27,7 +27,7 @@ from .domains import Domain, And, Or, Not

__all__ = [
'LinExpr', 'Symbol', 'Dummy', 'symbols', 'Rational',

__all__ = [
'LinExpr', 'Symbol', 'Dummy', 'symbols', 'Rational',
-    'Point', 'Vector',
+    'GeometricObject', 'Point', 'Vector',
'Polyhedron', 'Eq', 'Ne', 'Le', 'Lt', 'Ge', 'Gt', 'Empty', 'Universe',
'Domain', 'And', 'Or', 'Not',
]
'Polyhedron', 'Eq', 'Ne', 'Le', 'Lt', 'Ge', 'Gt', 'Empty', 'Universe',
'Domain', 'And', 'Or', 'Not',
]
index 238248b..4cd46a4 100644 (file)
# You should have received a copy of the GNU General Public License
# along with LinPy.  If not, see <http://www.gnu.org/licenses/>.

# You should have received a copy of the GNU General Public License
# along with LinPy.  If not, see <http://www.gnu.org/licenses/>.

-"""
-Polyhedral domains
-
-This module provides classes and functions to deal with polyhedral
-domains, i.e. unions of polyhedra.
-"""
-
import ast
import functools
import re
import ast
import functools
import re
@@ -44,7 +37,11 @@ __all__ = [
@functools.total_ordering
class Domain(GeometricObject):
"""
@functools.total_ordering
class Domain(GeometricObject):
"""
-    This class represents polyhedral domains, i.e. unions of polyhedra.
+    A domain is a union of polyhedra. Unlike polyhedra, domains allow exact
+    computation of union and complementary operations.
+
+    A domain with a unique polyhedron is automatically subclassed as a
+    Polyhedron instance.
"""

__slots__ = (
"""

__slots__ = (
@@ -55,7 +52,27 @@ class Domain(GeometricObject):

def __new__(cls, *polyhedra):
"""

def __new__(cls, *polyhedra):
"""
-        Create and return a new domain from a string or a list 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])
+
+        It is also possible to build domains from polyhedra using arithmetic
+        operators Domain.__and__(), Domain.__or__() or functions And() and 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 GeometricObject instance, calling
+        the GeometricObject.asdomain() method.
"""
from .polyhedra import Polyhedron
if len(polyhedra) == 1:
"""
from .polyhedra import Polyhedron
if len(polyhedra) == 1:
@@ -88,35 +105,28 @@ class Domain(GeometricObject):
@property
def polyhedra(self):
"""
@property
def polyhedra(self):
"""
-        The tuple of polyhedra which constitute the domain.
+        The tuple of polyhedra present in the domain.
"""
return self._polyhedra

@property
def symbols(self):
"""
"""
return self._polyhedra

@property
def symbols(self):
"""
-        The tuple of symbols present in the domain equations.
+        The tuple of symbols present in the domain equations, sorted according
+        to Symbol.sortkey().
"""
return self._symbols

@property
def dimension(self):
"""
"""
return self._symbols

@property
def dimension(self):
"""
-        The dimension of the domain, i.e. the number of symbols.
+        The dimension of the domain, i.e. the number of symbols present in it.
"""
return self._dimension

"""
return self._dimension

-    def make_disjoint(self):
-        """
-        Return an equivalent domain, whose polyhedra are disjoint.
-        """
-        islset = self._toislset(self.polyhedra, self.symbols)
-        islset = libisl.isl_set_make_disjoint(mainctx, islset)
-        return self._fromislset(islset, self.symbols)
-
def isempty(self):
"""
def isempty(self):
"""
-        Return True if the domain is empty.
+        Return True if the domain is empty, that is, equal to Empty.
"""
islset = self._toislset(self.polyhedra, self.symbols)
empty = bool(libisl.isl_set_is_empty(islset))
"""
islset = self._toislset(self.polyhedra, self.symbols)
empty = bool(libisl.isl_set_is_empty(islset))
@@ -131,7 +141,7 @@ class Domain(GeometricObject):

def isuniverse(self):
"""

def isuniverse(self):
"""
-        Return True if the domain is universal, i.e. with no constraint.
+        Return True if the domain is universal, that is, equal to Universe.
"""
islset = self._toislset(self.polyhedra, self.symbols)
universe = bool(libisl.isl_set_plain_is_universe(islset))
"""
islset = self._toislset(self.polyhedra, self.symbols)
universe = bool(libisl.isl_set_plain_is_universe(islset))
@@ -149,7 +159,7 @@ class Domain(GeometricObject):

def __eq__(self, other):
"""

def __eq__(self, other):
"""
-        Return True if the two domains are equal.
+        Return True if two domains are equal.
"""
symbols = self._xsymbols([self, other])
islset1 = self._toislset(self.polyhedra, symbols)
"""
symbols = self._xsymbols([self, other])
islset1 = self._toislset(self.polyhedra, symbols)
@@ -211,10 +221,18 @@ class Domain(GeometricObject):
return self.complement()
__invert__.__doc__ = complement.__doc__

return self.complement()
__invert__.__doc__ = complement.__doc__

+    def make_disjoint(self):
+        """
+        Return an equivalent domain, whose polyhedra are disjoint.
+        """
+        islset = self._toislset(self.polyhedra, self.symbols)
+        islset = libisl.isl_set_make_disjoint(mainctx, islset)
+        return self._fromislset(islset, self.symbols)
+
def coalesce(self):
"""
Simplify the representation of the domain by trying to combine pairs of
def coalesce(self):
"""
Simplify the representation of the domain by trying to combine pairs of
-        polyhedra into a single polyhedron.
+        polyhedra into a single polyhedron, and return the resulting domain.
"""
islset = self._toislset(self.polyhedra, self.symbols)
islset = libisl.isl_set_coalesce(islset)
"""
islset = self._toislset(self.polyhedra, self.symbols)
islset = libisl.isl_set_coalesce(islset)
@@ -223,7 +241,7 @@ class Domain(GeometricObject):
def detect_equalities(self):
"""
Simplify the representation of the domain by detecting implicit
def detect_equalities(self):
"""
Simplify the representation of the domain by detecting implicit
-        equalities.
+        equalities, and return the resulting domain.
"""
islset = self._toislset(self.polyhedra, self.symbols)
islset = libisl.isl_set_detect_equalities(islset)
"""
islset = self._toislset(self.polyhedra, self.symbols)
islset = libisl.isl_set_detect_equalities(islset)
@@ -231,16 +249,14 @@ class Domain(GeometricObject):

def remove_redundancies(self):
"""

def remove_redundancies(self):
"""
-        Remove redundant constraints in the domain.
+        Remove redundant constraints in the domain, and return the resulting
+        domain.
"""
islset = self._toislset(self.polyhedra, self.symbols)
islset = libisl.isl_set_remove_redundancies(islset)
return self._fromislset(islset, self.symbols)

def aspolyhedron(self):
"""
islset = self._toislset(self.polyhedra, self.symbols)
islset = libisl.isl_set_remove_redundancies(islset)
return self._fromislset(islset, self.symbols)

def aspolyhedron(self):
-        """
-        Return the polyhedral hull of the domain.
-        """
from .polyhedra import Polyhedron
islset = self._toislset(self.polyhedra, self.symbols)
islbset = libisl.isl_set_polyhedral_hull(islset)
from .polyhedra import Polyhedron
islset = self._toislset(self.polyhedra, self.symbols)
islbset = libisl.isl_set_polyhedral_hull(islset)
@@ -251,7 +267,8 @@ class Domain(GeometricObject):

def project(self, symbols):
"""

def project(self, symbols):
"""
-        Project out the symbols given in arguments.
+        Project out the sequence of symbols given in arguments, and return the
+        resulting domain.
"""
islset = self._toislset(self.polyhedra, self.symbols)
n = 0
"""
islset = self._toislset(self.polyhedra, self.symbols)
n = 0
@@ -269,7 +286,8 @@ class Domain(GeometricObject):

def sample(self):
"""

def sample(self):
"""
-        Return a sample of the domain.
+        Return a sample of the domain, as an integer instance of Point. If the
+        domain is empty, a ValueError exception is raised.
"""
islset = self._toislset(self.polyhedra, self.symbols)
islpoint = libisl.isl_set_sample_point(islset)
"""
islset = self._toislset(self.polyhedra, self.symbols)
islpoint = libisl.isl_set_sample_point(islset)
@@ -287,7 +305,8 @@ class Domain(GeometricObject):

def intersection(self, *others):
"""

def intersection(self, *others):
"""
-        Return the intersection of two domains as a new domain.
+        Return the intersection of two or more domains as a new domain. As an
+        alternative, function And() can be used.
"""
if len(others) == 0:
return self
"""
if len(others) == 0:
return self
@@ -304,7 +323,8 @@ class Domain(GeometricObject):

def union(self, *others):
"""

def union(self, *others):
"""
-        Return the union of two domains as a new domain.
+        Return the union of two or more domains as a new domain. As an
+        alternative, function Or() can be used.
"""
if len(others) == 0:
return self
"""
if len(others) == 0:
return self
@@ -357,7 +377,8 @@ class Domain(GeometricObject):

def vertices(self):
"""

def vertices(self):
"""
-        Return the vertices of the domain.
+        Return the vertices of the domain, as a list of rational instances of
+        Point.
"""
from .polyhedra import Polyhedron
if not self.isbounded():
"""
from .polyhedra import Polyhedron
if not self.isbounded():
@@ -396,7 +417,9 @@ class Domain(GeometricObject):

def points(self):
"""

def points(self):
"""
-        Return the points with integer coordinates contained in the domain.
+        Return the integer points of a bounded domain, as a list of integer
+        instances of Point. If the domain is not bounded, a ValueError exception
+        is raised.
"""
if not self.isbounded():
raise ValueError('domain must be bounded')
"""
if not self.isbounded():
raise ValueError('domain must be bounded')
@@ -414,6 +437,15 @@ class Domain(GeometricObject):
points.append(Point(coordinates))
return points

points.append(Point(coordinates))
return points

+    def __contains__(self, point):
+        """
+        Return True if the point if contained within the domain.
+        """
+        for polyhedron in self.polyhedra:
+            if point in polyhedron:
+                return True
+        return False
+
@classmethod
def _polygon_inner_point(cls, points):
symbols = points.symbols
@classmethod
def _polygon_inner_point(cls, points):
symbols = points.symbols
@@ -467,7 +499,9 @@ class Domain(GeometricObject):

def faces(self):
"""

def faces(self):
"""
-        Return the vertices of the domain, grouped by face.
+        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 Point. If
+        the domain is not bounded, a ValueError exception is raised.
"""
faces = []
for polyhedron in self.polyhedra:
"""
faces = []
for polyhedron in self.polyhedra:
@@ -531,7 +565,11 @@ class Domain(GeometricObject):

def plot(self, plot=None, **kwargs):
"""

def plot(self, plot=None, **kwargs):
"""
-        Plot the domain using matplotlib.
+        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 ValueError is the domain is
+        not 2D or 3D.
"""
if not self.isbounded():
raise ValueError('domain must be bounded')
"""
if not self.isbounded():
raise ValueError('domain must be bounded')
@@ -542,19 +580,12 @@ class Domain(GeometricObject):
else:
raise ValueError('polyhedron must be 2 or 3-dimensional')

else:
raise ValueError('polyhedron must be 2 or 3-dimensional')

-    def __contains__(self, point):
-        """
-        Return True if point if contained within the domain.
-        """
-        for polyhedron in self.polyhedra:
-            if point in polyhedron:
-                return True
-        return False
-
def subs(self, symbol, expression=None):
"""
def subs(self, symbol, expression=None):
"""
-        Subsitute symbol by expression in equations and return the resulting
-        domain.
+        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 LinExpr.subs().
"""
polyhedra = [polyhedron.subs(symbol, expression)
for polyhedron in self.polyhedra]
"""
polyhedra = [polyhedron.subs(symbol, expression)
for polyhedron in self.polyhedra]
@@ -648,7 +679,8 @@ class Domain(GeometricObject):
@classmethod
def fromstring(cls, string):
"""
@classmethod
def fromstring(cls, string):
"""
-        Convert a string into a domain.
+        Create a domain from a string. Raise SyntaxError if the string is not
+        properly formatted.
"""
# remove curly brackets
string = cls._RE_BRACES.sub(r'', string)
"""
# remove curly brackets
string = cls._RE_BRACES.sub(r'', string)
@@ -671,9 +703,6 @@ class Domain(GeometricObject):
return cls._fromast(tree)

def __repr__(self):
return cls._fromast(tree)

def __repr__(self):
-        """
-        Return repr(self).
-        """
assert len(self.polyhedra) >= 2
strings = [repr(polyhedron) for polyhedron in self.polyhedra]
return 'Or({})'.format(', '.join(strings))
assert len(self.polyhedra) >= 2
strings = [repr(polyhedron) for polyhedron in self.polyhedra]
return 'Or({})'.format(', '.join(strings))
@@ -687,7 +716,7 @@ class Domain(GeometricObject):
@classmethod
def fromsympy(cls, expr):
"""
@classmethod
def fromsympy(cls, expr):
"""
-        Convert a SymPy expression into a domain.
+        Create a domain from a sympy expression.
"""
import sympy
from .polyhedra import Lt, Le, Eq, Ne, Ge, Gt
"""
import sympy
from .polyhedra import Lt, Le, Eq, Ne, Ge, Gt
@@ -706,7 +735,7 @@ class Domain(GeometricObject):

def tosympy(self):
"""

def tosympy(self):
"""
-        Convert a domain into a SymPy expression.
+        Convert the domain to a sympy expression.
"""
import sympy
polyhedra = [polyhedron.tosympy() for polyhedron in polyhedra]
"""
import sympy
polyhedra = [polyhedron.tosympy() for polyhedron in polyhedra]
@@ -714,6 +743,9 @@ class Domain(GeometricObject):

def And(*domains):

def And(*domains):
+    """
+    Create the intersection domain of the domains given in arguments.
+    """
if len(domains) == 0:
from .polyhedra import Universe
return Universe
if len(domains) == 0:
from .polyhedra import Universe
return Universe
@@ -722,6 +754,9 @@ def And(*domains):
And.__doc__ = Domain.intersection.__doc__

def Or(*domains):
And.__doc__ = Domain.intersection.__doc__

def Or(*domains):
+    """
+    Create the union domain of the domains given in arguments.
+    """
if len(domains) == 0:
from .polyhedra import Empty
return Empty
if len(domains) == 0:
from .polyhedra import Empty
return Empty
@@ -730,5 +765,8 @@ def Or(*domains):
Or.__doc__ = Domain.union.__doc__

def Not(domain):
Or.__doc__ = Domain.union.__doc__

def Not(domain):
+    """
+    Create the complementary domain of the domain given in argument.
+    """
return ~domain
Not.__doc__ = Domain.complement.__doc__
return ~domain
Not.__doc__ = Domain.complement.__doc__
index 335a826..1a56269 100644 (file)
@@ -33,30 +33,55 @@ __all__ = [

class GeometricObject(ABC):

class GeometricObject(ABC):
+    """
+    GeometricObject is an abstract class to represent objects with a
+    geometric representation in space. Subclasses of GeometricObject are
+    Polyhedron, Domain and Point.
+    """

@abstractproperty
def symbols(self):

@abstractproperty
def symbols(self):
+        """
+        The tuple of symbols present in the object expression, sorted according
+        to Symbol.sortkey().
+        """
pass

@property
def dimension(self):
pass

@property
def dimension(self):
+        """
+        The dimension of the object, i.e. the number of symbols present in it.
+        """
return len(self.symbols)

@abstractmethod
def aspolyhedron(self):
return len(self.symbols)

@abstractmethod
def aspolyhedron(self):
+        """
+        Return a Polyhedron object that approximates the geometric object.
+        """
pass

def asdomain(self):
pass

def asdomain(self):
+        """
+        Return a Domain object that approximates the geometric object.
+        """
return self.aspolyhedron()

class Coordinates:
return self.aspolyhedron()

class Coordinates:
+    """
+    This class represents coordinate systems.
+    """

__slots__ = (
'_coordinates',
)

def __new__(cls, coordinates):

__slots__ = (
'_coordinates',
)

def __new__(cls, coordinates):
+        """
+        Create a coordinate system from a dictionary or a sequence that maps the
+        symbols to their coordinates. Coordinates must be rational numbers.
+        """
if isinstance(coordinates, Mapping):
coordinates = coordinates.items()
self = object().__new__(cls)
if isinstance(coordinates, Mapping):
coordinates = coordinates.items()
self = object().__new__(cls)
@@ -72,26 +97,48 @@ class Coordinates:

@property
def symbols(self):

@property
def symbols(self):
+        """
+        The tuple of symbols present in the coordinate system, sorted according
+        to Symbol.sortkey().
+        """
return tuple(self._coordinates)

@property
def dimension(self):
return tuple(self._coordinates)

@property
def dimension(self):
+        """
+        The dimension of the coordinate system, i.e. the number of symbols
+        present in it.
+        """
return len(self.symbols)

return len(self.symbols)

-    def coordinates(self):
-        yield from self._coordinates.items()
-
def coordinate(self, symbol):
def coordinate(self, symbol):
+        """
+        Return the coordinate value of the given symbol. Raise KeyError if the
+        symbol is not involved in the coordinate system.
+        """
if not isinstance(symbol, Symbol):
raise TypeError('symbol must be a Symbol instance')
return self._coordinates[symbol]

__getitem__ = coordinate

if not isinstance(symbol, Symbol):
raise TypeError('symbol must be a Symbol instance')
return self._coordinates[symbol]

__getitem__ = coordinate

+    def coordinates(self):
+        """
+        Iterate over the pairs (symbol, value) of coordinates in the coordinate
+        system.
+        """
+        yield from self._coordinates.items()
+
def values(self):
def values(self):
+        """
+        Iterate over the coordinate values in the coordinate system.
+        """
yield from self._coordinates.values()

def __bool__(self):
yield from self._coordinates.values()

def __bool__(self):
+        """
+        Return True if not all coordinates are 0.
+        """
return any(self._coordinates.values())

def __hash__(self):
return any(self._coordinates.values())

def __hash__(self):
@@ -121,11 +168,13 @@ class Coordinates:
class Point(Coordinates, GeometricObject):
"""
This class represents points in space.
class Point(Coordinates, GeometricObject):
"""
This class represents points in space.
+
+    Point instances are hashable and should be treated as immutable.
"""

def isorigin(self):
"""
"""

def isorigin(self):
"""
-        Return True if a Point is the origin.
+        Return True if all coordinates are 0.
"""
return not bool(self)

"""
return not bool(self)

@@ -134,7 +183,7 @@ class Point(Coordinates, GeometricObject):

"""

"""
-        Adds a Point to a Vector and returns the result as a Point.
+        Translate the point by a Vector object and return the resulting point.
"""
if not isinstance(other, Vector):
return NotImplemented
"""
if not isinstance(other, Vector):
return NotImplemented
@@ -143,7 +192,9 @@ class Point(Coordinates, GeometricObject):

def __sub__(self, other):
"""

def __sub__(self, other):
"""
-        Returns the difference between two Points as a Vector.
+        If other is a point, substract a point from another and returns the
+        resulting vector. If other is a vector, translate the point by the
+        opposite vector and returns the resulting point.
"""
coordinates = []
if isinstance(other, Point):
"""
coordinates = []
if isinstance(other, Point):
@@ -157,15 +208,12 @@ class Point(Coordinates, GeometricObject):

def __eq__(self, other):
"""

def __eq__(self, other):
"""
-        Compares two Points for equality.
+        Test whether two points are equal.
"""
return isinstance(other, Point) and \
self._coordinates == other._coordinates

def aspolyhedron(self):
"""
return isinstance(other, Point) and \
self._coordinates == other._coordinates

def aspolyhedron(self):
-        """
-        Return a Point as a polyhedron.
-        """
from .polyhedra import Polyhedron
equalities = []
for symbol, coordinate in self.coordinates():
from .polyhedra import Polyhedron
equalities = []
for symbol, coordinate in self.coordinates():
@@ -175,10 +223,16 @@ class Point(Coordinates, GeometricObject):

class Vector(Coordinates):
"""

class Vector(Coordinates):
"""
-    This class represents displacements in space.
+    This class represents vectors in space.
+
+    Vector instances are hashable and should be treated as immutable.
"""

def __new__(cls, initial, terminal=None):
"""

def __new__(cls, initial, terminal=None):
+        """
+        Create a vector from a dictionary or a sequence that maps the symbols to
+        their coordinates, or as the difference between two points.
+        """
if not isinstance(initial, Point):
initial = Point(initial)
if terminal is None:
if not isinstance(initial, Point):
initial = Point(initial)
if terminal is None:
@@ -191,7 +245,7 @@ class Vector(Coordinates):

def isnull(self):
"""

def isnull(self):
"""
-        Returns true if a Vector is null.
+        Return True if all coordinates are 0.
"""
return not bool(self)

"""
return not bool(self)

@@ -200,13 +254,59 @@ class Vector(Coordinates):

"""

"""
-        Adds either a Point or Vector to a Vector.
+        If other is a point, translate it with the vector self and return the
+        resulting point. If other is a vector, return the vector self + other.
"""
if isinstance(other, (Point, Vector)):
return other.__class__(coordinates)
return NotImplemented

"""
if isinstance(other, (Point, Vector)):
return other.__class__(coordinates)
return NotImplemented

+    def __sub__(self, other):
+        """
+        If other is a point, substract it from the vector self and return the
+        resulting point. If other is a vector, return the vector self - other.
+        """
+        if isinstance(other, (Point, Vector)):
+            coordinates = self._map2(other, operator.sub)
+            return other.__class__(coordinates)
+        return NotImplemented
+
+    def __neg__(self):
+        """
+        Return the vector -self.
+        """
+        coordinates = self._map(operator.neg)
+        return Vector(coordinates)
+
+    def __mul__(self, other):
+        """
+        Multiplies a Vector by a scalar value.
+        """
+        if not isinstance(other, numbers.Real):
+            return NotImplemented
+        coordinates = self._map(lambda coordinate: other * coordinate)
+        return Vector(coordinates)
+
+    __rmul__ = __mul__
+
+    def __truediv__(self, other):
+        """
+        Divide the vector by the specified scalar and returns the result as a
+        vector.
+        """
+        if not isinstance(other, numbers.Real):
+            return NotImplemented
+        coordinates = self._map(lambda coordinate: coordinate / other)
+        return Vector(coordinates)
+
+    def __eq__(self, other):
+        """
+        Test whether two vectors are equal.
+        """
+        return isinstance(other, Vector) and \
+            self._coordinates == other._coordinates
+
def angle(self, other):
"""
Retrieve the angle required to rotate the vector into the vector passed
def angle(self, other):
"""
Retrieve the angle required to rotate the vector into the vector passed
@@ -220,7 +320,8 @@ class Vector(Coordinates):

def cross(self, other):
"""

def cross(self, other):
"""
-        Calculate the cross product of two Vector3D structures.
+        Compute the cross product of two 3D vectors. If either one of the
+        vectors is not tridimensional, a ValueError exception is raised.
"""
if not isinstance(other, Vector):
raise TypeError('other must be a Vector instance')
"""
if not isinstance(other, Vector):
raise TypeError('other must be a Vector instance')
@@ -235,19 +336,9 @@ class Vector(Coordinates):
coordinates.append((z, self[x]*other[y] - self[y]*other[x]))
return Vector(coordinates)

coordinates.append((z, self[x]*other[y] - self[y]*other[x]))
return Vector(coordinates)

-    def __truediv__(self, other):
-        """
-        Divide the vector by the specified scalar and returns the result as a
-        vector.
-        """
-        if not isinstance(other, numbers.Real):
-            return NotImplemented
-        coordinates = self._map(lambda coordinate: coordinate / other)
-        return Vector(coordinates)
-
def dot(self, other):
"""
def dot(self, other):
"""
-        Calculate the dot product of two vectors.
+        Compute the dot product of two vectors.
"""
if not isinstance(other, Vector):
raise TypeError('argument must be a Vector instance')
"""
if not isinstance(other, Vector):
raise TypeError('argument must be a Vector instance')
@@ -256,54 +347,27 @@ class Vector(Coordinates):
result += coordinate1 * coordinate2
return result

result += coordinate1 * coordinate2
return result

-    def __eq__(self, other):
-        """
-        Compares two Vectors for equality.
-        """
-        return isinstance(other, Vector) and \
-            self._coordinates == other._coordinates
-
def __hash__(self):
return hash(tuple(self.coordinates()))

def __hash__(self):
return hash(tuple(self.coordinates()))

-    def __mul__(self, other):
-        """
-        Multiplies a Vector by a scalar value.
-        """
-        if not isinstance(other, numbers.Real):
-            return NotImplemented
-        coordinates = self._map(lambda coordinate: other * coordinate)
-        return Vector(coordinates)
-
-    __rmul__ = __mul__
-
-    def __neg__(self):
-        """
-        Returns the negated form of a Vector.
-        """
-        coordinates = self._map(operator.neg)
-        return Vector(coordinates)
-
def norm(self):
"""
def norm(self):
"""
-        Normalizes a Vector.
+        Return the norm of the vector.
"""
return math.sqrt(self.norm2())

def norm2(self):
"""
return math.sqrt(self.norm2())

def norm2(self):
+        """
+        Return the squared norm of the vector.
+        """
result = 0
for coordinate in self._coordinates.values():
result += coordinate ** 2
return result

def asunit(self):
result = 0
for coordinate in self._coordinates.values():
result += coordinate ** 2
return result

def asunit(self):
-        return self / self.norm()
-
-    def __sub__(self, other):
"""
"""
-        Subtract a Point or Vector from a Vector.
+        Return the normalized vector, i.e. the vector of same direction but with
+        norm 1.
"""
"""
-        if isinstance(other, (Point, Vector)):
-            coordinates = self._map2(other, operator.sub)
-            return other.__class__(coordinates)
-        return NotImplemented
+        return self / self.norm()
index 8267be1..82d75d0 100644 (file)
@@ -45,12 +45,43 @@ def _polymorphic(func):

class LinExpr:
"""

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):
"""
"""

def __new__(cls, coefficients=None, constant=0):
"""
-        Create a new expression.
+        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:
"""
if isinstance(coefficients, str):
if constant != 0:
@@ -86,7 +117,8 @@ class LinExpr:

def coefficient(self, symbol):
"""

def coefficient(self, symbol):
"""
-        Return the coefficient value of the given 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')
"""
if not isinstance(symbol, Symbol):
raise TypeError('symbol must be a Symbol instance')
@@ -96,7 +128,8 @@ class LinExpr:

def coefficients(self):
"""

def coefficients(self):
"""
-        Return a list of the coefficients of an expression
+        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)
"""
for symbol, coefficient in self._coefficients.items():
yield symbol, Rational(coefficient)
@@ -104,21 +137,23 @@ class LinExpr:
@property
def constant(self):
"""
@property
def constant(self):
"""
-        Return the constant value of an expression.
+        The constant term of the expression.
"""
return Rational(self._constant)

@property
def symbols(self):
"""
"""
return Rational(self._constant)

@property
def symbols(self):
"""
-        Return a list of symbols in an expression.
+        The tuple of symbols present in the expression, sorted according to
+        Symbol.sortkey().
"""
return self._symbols

@property
def dimension(self):
"""
"""
return self._symbols

@property
def dimension(self):
"""
-        Create and return a new linear expression from a string or a list of coefficients and a constant.
+        The dimension of the expression, i.e. the number of symbols present in
+        it.
"""
return self._dimension

"""
return self._dimension

@@ -127,19 +162,22 @@ class LinExpr:

def isconstant(self):
"""

def isconstant(self):
"""
-        Return true if an expression is a constant.
+        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 False

def issymbol(self):
"""
-        Return true if an expression is a symbol.
+        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):
"""
"""
return False

def values(self):
"""
-        Return the coefficient and constant values of an expression.
+        Iterate over the coefficient values in the expression, and the constant
+        term.
"""
for coefficient in self._coefficients.values():
yield Rational(coefficient)
"""
for coefficient in self._coefficients.values():
yield Rational(coefficient)
@@ -157,7 +195,7 @@ class LinExpr:
@_polymorphic
"""
@_polymorphic
"""
-        Return the sum of two expressions.
+        Return the sum of two linear expressions.
"""
coefficients = defaultdict(Fraction, self._coefficients)
for symbol, coefficient in other._coefficients.items():
"""
coefficients = defaultdict(Fraction, self._coefficients)
for symbol, coefficient in other._coefficients.items():
@@ -170,7 +208,7 @@ class LinExpr:
@_polymorphic
def __sub__(self, other):
"""
@_polymorphic
def __sub__(self, other):
"""
-        Return the difference between two expressions.
+        Return the difference between two linear expressions.
"""
coefficients = defaultdict(Fraction, self._coefficients)
for symbol, coefficient in other._coefficients.items():
"""
coefficients = defaultdict(Fraction, self._coefficients)
for symbol, coefficient in other._coefficients.items():
@@ -184,7 +222,7 @@ class LinExpr:

def __mul__(self, other):
"""

def __mul__(self, other):
"""
-        Return the product of two expressions if other is a rational number.
+        Return the product of the linear expression by a rational.
"""
if isinstance(other, numbers.Rational):
coefficients = ((symbol, coefficient * other)
"""
if isinstance(other, numbers.Rational):
coefficients = ((symbol, coefficient * other)
@@ -196,6 +234,9 @@ class LinExpr:
__rmul__ = __mul__

def __truediv__(self, other):
__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())
if isinstance(other, numbers.Rational):
coefficients = ((symbol, coefficient / other)
for symbol, coefficient in self._coefficients.items())
@@ -206,7 +247,7 @@ class LinExpr:
@_polymorphic
def __eq__(self, other):
"""
@_polymorphic
def __eq__(self, other):
"""
-        Test whether two expressions are equal
+        Test whether two linear expressions are equal.
"""
return isinstance(other, LinExpr) and \
self._coefficients == other._coefficients and \
"""
return isinstance(other, LinExpr) and \
self._coefficients == other._coefficients and \
@@ -230,7 +271,8 @@ class LinExpr:

def scaleint(self):
"""

def scaleint(self):
"""
-        Multiply an expression by a scalar to make all coefficients integer values.
+        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()])
"""
lcm = functools.reduce(lambda a, b: a*b // gcd(a, b),
[value.denominator for value in self.values()])
@@ -238,8 +280,19 @@ class LinExpr:

def subs(self, symbol, expression=None):
"""

def subs(self, symbol, expression=None):
"""
-        Subsitute symbol by expression in equations and return the resulting
-        expression.
+        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):
"""
if expression is None:
if isinstance(symbol, Mapping):
@@ -289,7 +342,8 @@ class LinExpr:
@classmethod
def fromstring(cls, string):
"""
@classmethod
def fromstring(cls, string):
"""
-        Create an expression from a 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 = LinExpr._RE_NUM_VAR.sub(r'\1*\2', string)
"""
# add implicit multiplication operators, e.g. '5x' -> '5*x'
string = LinExpr._RE_NUM_VAR.sub(r'\1*\2', string)
@@ -354,7 +408,8 @@ class LinExpr:
@classmethod
def fromsympy(cls, expr):
"""
@classmethod
def fromsympy(cls, expr):
"""
-        Convert sympy object to an expression.
+        Create a linear expression from a sympy expression. Raise ValueError is
+        the sympy expression is not linear.
"""
import sympy
coefficients = []
"""
import sympy
coefficients = []
@@ -372,7 +427,7 @@ class LinExpr:

def tosympy(self):
"""

def tosympy(self):
"""
-        Return an expression as a sympy object.
+        Convert the linear expression to a sympy expression.
"""
import sympy
expr = 0
"""
import sympy
expr = 0
@@ -384,10 +439,17 @@ class LinExpr:

class Symbol(LinExpr):

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):
"""

def __new__(cls, name):
"""
-        Create and return a symbol from a string.
+        Return a symbol with the name string given in argument.
"""
if not isinstance(name, str):
raise TypeError('name must be a string')
"""
if not isinstance(name, str):
raise TypeError('name must be a string')
@@ -401,12 +463,22 @@ class Symbol(LinExpr):

@property
def name(self):

@property
def name(self):
+        """
+        The name of the symbol.
+        """
return self._name

def __hash__(self):
return hash(self.sortkey())

def sortkey(self):
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):
return self.name,

def issymbol(self):
@@ -417,7 +489,7 @@ class Symbol(LinExpr):

def asdummy(self):
"""

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

"""
return Dummy(self.name)

@@ -450,13 +522,29 @@ class Symbol(LinExpr):

class Dummy(Symbol):
"""

class Dummy(Symbol):
"""
-    This class returns a dummy symbol to ensure that no variables are repeated in an expression
+    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):
"""
_count = 0

def __new__(cls, name=None):
"""
-        Create and return a new dummy symbol.
+        Return a fresh dummy symbol with the name string given in argument.
"""
if name is None:
name = 'Dummy_{}'.format(Dummy._count)
"""
if name is None:
name = 'Dummy_{}'.format(Dummy._count)
@@ -487,7 +575,13 @@ class Dummy(Symbol):

def symbols(names):
"""

def symbols(names):
"""
-    Transform strings into instances of the Symbol class
+    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()
"""
if isinstance(names, str):
names = names.replace(',', ' ').split()
@@ -496,7 +590,10 @@ def symbols(names):

class Rational(LinExpr, Fraction):
"""

class Rational(LinExpr, Fraction):
"""
-    This class represents integers and rational numbers of any size.
+    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):
"""

def __new__(cls, numerator=0, denominator=None):
@@ -514,15 +611,9 @@ class Rational(LinExpr, Fraction):

@property
def constant(self):

@property
def constant(self):
-        """
-        Return rational as a constant.
-        """
return self

def isconstant(self):
return self

def isconstant(self):
-        """
-        Test whether a value is a constant.
-        """
return True

def __bool__(self):
return True

def __bool__(self):
@@ -546,9 +637,6 @@ class Rational(LinExpr, Fraction):

@classmethod
def fromsympy(cls, expr):

@classmethod
def fromsympy(cls, expr):
-        """
-        Create a rational object from a sympy expression
-        """
import sympy
if isinstance(expr, sympy.Rational):
return Rational(expr.p, expr.q)
import sympy
if isinstance(expr, sympy.Rational):
return Rational(expr.p, expr.q)
index 346ffff..b486be1 100644 (file)
@@ -36,8 +36,11 @@ __all__ = [

class Polyhedron(Domain):
"""

class Polyhedron(Domain):
"""
-    Polyhedron class allows users to build and inspect polyherons. Polyhedron inherits from Domain.
+    A convex polyhedron (or simply "polyhedron") is the space defined by a
+    system of linear equalities and inequalities. This space can be
+    unbounded.
"""
"""
+
__slots__ = (
'_equalities',
'_inequalities',
__slots__ = (
'_equalities',
'_inequalities',
@@ -48,9 +51,35 @@ class Polyhedron(Domain):

def __new__(cls, equalities=None, inequalities=None):
"""

def __new__(cls, equalities=None, inequalities=None):
"""
-        Create and return a new Polyhedron from a string or list of equalities and inequalities.
-        """
+        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 LinExpr.__lt__(),
+        LinExpr.__le__(), LinExpr.__ge__(), LinExpr.__gt__(), or functions Lt(),
+        Le(), Eq(), Ge() and 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 GeometricObject
+        instance, calling the GeometricObject.aspolyedron() method. This way, it
+        is possible to compute the polyhedral hull of a 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)
+        """
if isinstance(equalities, str):
if inequalities is not None:
raise TypeError('too many arguments')
if isinstance(equalities, str):
if inequalities is not None:
raise TypeError('too many arguments')
@@ -80,21 +109,24 @@ class Polyhedron(Domain):
@property
def equalities(self):
"""
@property
def equalities(self):
"""
-        Return a list of the equalities in a polyhedron.
+        The tuple of equalities. This is a list of LinExpr instances that are
+        equal to 0 in the polyhedron.
"""
return self._equalities

@property
def inequalities(self):
"""
"""
return self._equalities

@property
def inequalities(self):
"""
-        Return a list of the inequalities in a polyhedron.
+        The tuple of inequalities. This is a list of LinExpr instances that are
+        greater or equal to 0 in the polyhedron.
"""
return self._inequalities

@property
def constraints(self):
"""
"""
return self._inequalities

@property
def constraints(self):
"""
-        Return the list of the constraints of a polyhedron.
+        The tuple of constraints, i.e., equalities and inequalities. This is
+        semantically equivalent to: equalities + inequalities.
"""
return self._constraints

"""
return self._constraints

@@ -103,15 +135,9 @@ class Polyhedron(Domain):
return self,

def make_disjoint(self):
return self,

def make_disjoint(self):
-        """
-        Return a polyhedron as disjoint.
-        """
return self

def isuniverse(self):
return self

def isuniverse(self):
-        """
-        Return true if a polyhedron is the Universe set.
-        """
islbset = self._toislbasicset(self.equalities, self.inequalities,
self.symbols)
universe = bool(libisl.isl_basic_set_is_universe(islbset))
islbset = self._toislbasicset(self.equalities, self.inequalities,
self.symbols)
universe = bool(libisl.isl_basic_set_is_universe(islbset))
@@ -119,15 +145,9 @@ class Polyhedron(Domain):
return universe

def aspolyhedron(self):
return universe

def aspolyhedron(self):
-        """
-        Return the polyhedral hull of a polyhedron.
-        """
return self

def __contains__(self, point):
return self

def __contains__(self, point):
-        """
-        Report whether a polyhedron constains an integer point
-        """
if not isinstance(point, Point):
raise TypeError('point must be a Point instance')
if self.symbols != point.symbols:
if not isinstance(point, Point):
raise TypeError('point must be a Point instance')
if self.symbols != point.symbols:
@@ -141,10 +161,6 @@ class Polyhedron(Domain):
return True

def subs(self, symbol, expression=None):
return True

def subs(self, symbol, expression=None):
-        """
-        Subsitute the given value into an expression and return the resulting
-        expression.
-        """
equalities = [equality.subs(symbol, expression)
for equality in self.equalities]
inequalities = [inequality.subs(symbol, expression)
equalities = [equality.subs(symbol, expression)
for equality in self.equalities]
inequalities = [inequality.subs(symbol, expression)
@@ -158,6 +174,9 @@ class Polyhedron(Domain):
return inequalities

def widen(self, other):
return inequalities

def widen(self, other):
+        """
+        Compute the standard widening of two polyhedra, à la Halbwachs.
+        """
if not isinstance(other, Polyhedron):
raise ValueError('argument must be a Polyhedron instance')
inequalities1 = self._asinequalities()
if not isinstance(other, Polyhedron):
raise ValueError('argument must be a Polyhedron instance')
inequalities1 = self._asinequalities()
@@ -242,9 +261,6 @@ class Polyhedron(Domain):

@classmethod
def fromstring(cls, string):

@classmethod
def fromstring(cls, string):
-        """
-        Create and return a Polyhedron from a string.
-        """
domain = Domain.fromstring(string)
if not isinstance(domain, Polyhedron):
raise ValueError('non-polyhedral expression: {!r}'.format(string))
domain = Domain.fromstring(string)
if not isinstance(domain, Polyhedron):
raise ValueError('non-polyhedral expression: {!r}'.format(string))
@@ -261,7 +277,6 @@ class Polyhedron(Domain):
else:
return 'And({})'.format(', '.join(strings))

else:
return 'And({})'.format(', '.join(strings))

-
def _repr_latex_(self):
strings = []
for equality in self.equalities:
def _repr_latex_(self):
strings = []
for equality in self.equalities:
@@ -272,18 +287,12 @@ class Polyhedron(Domain):

@classmethod
def fromsympy(cls, expr):

@classmethod
def fromsympy(cls, expr):
-        """
-        Convert a sympy object to a polyhedron.
-        """
domain = Domain.fromsympy(expr)
if not isinstance(domain, Polyhedron):
raise ValueError('non-polyhedral expression: {!r}'.format(expr))
return domain

def tosympy(self):
domain = Domain.fromsympy(expr)
if not isinstance(domain, Polyhedron):
raise ValueError('non-polyhedral expression: {!r}'.format(expr))
return domain

def tosympy(self):
-        """
-        Return a polyhedron as a sympy object.
-        """
import sympy
constraints = []
for equality in self.equalities:
import sympy
constraints = []
for equality in self.equalities:
@@ -294,6 +303,9 @@ class Polyhedron(Domain):

class EmptyType(Polyhedron):

class EmptyType(Polyhedron):
+    """
+    The empty polyhedron, whose set of constraints is not satisfiable.
+    """

__slots__ = Polyhedron.__slots__

__slots__ = Polyhedron.__slots__

@@ -321,6 +333,10 @@ Empty = EmptyType()

class UniverseType(Polyhedron):

class UniverseType(Polyhedron):
+    """
+    The universe polyhedron, whose set of constraints is always satisfiable,
+    i.e. is empty.
+    """

__slots__ = Polyhedron.__slots__

__slots__ = Polyhedron.__slots__

@@ -363,41 +379,42 @@ def _polymorphic(func):
@_polymorphic
def Lt(left, right):
"""
@_polymorphic
def Lt(left, right):
"""
-    Returns a Polyhedron instance with a single constraint as left less than right.
+    Create the polyhedron with constraints expr1 < expr2 < expr3 ...
"""
return Polyhedron([], [right - left - 1])

@_polymorphic
def Le(left, right):
"""
"""
return Polyhedron([], [right - left - 1])

@_polymorphic
def Le(left, right):
"""
-    Returns a Polyhedron instance with a single constraint as left less than or equal to right.
+    Create the polyhedron with constraints expr1 <= expr2 <= expr3 ...
"""
return Polyhedron([], [right - left])

@_polymorphic
def Eq(left, right):
"""
"""
return Polyhedron([], [right - left])

@_polymorphic
def Eq(left, right):
"""
-    Returns a Polyhedron instance with a single constraint as left equal to right.
+    Create the polyhedron with constraints expr1 == expr2 == expr3 ...
"""
return Polyhedron([left - right], [])

@_polymorphic
def Ne(left, right):
"""
"""
return Polyhedron([left - right], [])

@_polymorphic
def Ne(left, right):
"""
-    Returns a Polyhedron instance with a single constraint as left not equal to right.
+    Create the domain such that expr1 != expr2 != expr3 ... The result is a
+    Domain, not a Polyhedron.
"""
return ~Eq(left, right)

@_polymorphic
def Gt(left, right):
"""
"""
return ~Eq(left, right)

@_polymorphic
def Gt(left, right):
"""
-    Returns a Polyhedron instance with a single constraint as left greater than right.
+    Create the polyhedron with constraints expr1 > expr2 > expr3 ...
"""
return Polyhedron([], [left - right - 1])

@_polymorphic
def Ge(left, right):
"""
"""
return Polyhedron([], [left - right - 1])

@_polymorphic
def Ge(left, right):
"""
-    Returns a Polyhedron instance with a single constraint as left greater than or equal to right.
+    Create the polyhedron with constraints expr1 >= expr2 >= expr3 ...
"""
return Polyhedron([], [left - right])
"""
return Polyhedron([], [left - right])