From ba15f3f33f837b1291f74bc94081e99b860d3228 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Mon, 18 Aug 2014 14:21:19 +0200 Subject: [PATCH] Docstrings --- doc/reference.rst | 59 +++++++-------- linpy/__init__.py | 4 +- linpy/domains.py | 146 ++++++++++++++++++++++-------------- linpy/geometry.py | 182 ++++++++++++++++++++++++++++++--------------- linpy/linexprs.py | 158 ++++++++++++++++++++++++++++++--------- linpy/polyhedra.py | 93 +++++++++++++---------- 6 files changed, 425 insertions(+), 217 deletions(-) diff --git a/doc/reference.rst b/doc/reference.rst index 20168e4..e0efdde 100644 --- a/doc/reference.rst +++ b/doc/reference.rst @@ -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) - __getitem__(symbol) + __getitem__(symbol) 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) - __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. @@ -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) - 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. @@ -280,7 +280,7 @@ This space can be unbounded. .. method:: widen(polyhedron) - Compute the standard widening of two polyhedra, à la Halbwachs. + Compute the *standard widening* of two polyhedra, à la Halbwachs. .. data:: Empty @@ -329,7 +329,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 +435,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() @@ -567,7 +567,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 +590,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 +604,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 +620,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 +642,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 +657,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. @@ -670,25 +683,13 @@ Geometric Objects 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() diff --git a/linpy/__init__.py b/linpy/__init__.py index 2fdc73e..1e32751 100644 --- a/linpy/__init__.py +++ b/linpy/__init__.py @@ -19,7 +19,7 @@ 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 @@ -27,7 +27,7 @@ from .domains import Domain, And, Or, Not __all__ = [ 'LinExpr', 'Symbol', 'Dummy', 'symbols', 'Rational', - 'Point', 'Vector', + 'GeometricObject', 'Point', 'Vector', 'Polyhedron', 'Eq', 'Ne', 'Le', 'Lt', 'Ge', 'Gt', 'Empty', 'Universe', 'Domain', 'And', 'Or', 'Not', ] diff --git a/linpy/domains.py b/linpy/domains.py index 238248b..4cd46a4 100644 --- a/linpy/domains.py +++ b/linpy/domains.py @@ -15,13 +15,6 @@ # You should have received a copy of the GNU General Public License # along with LinPy. If not, see . -""" -Polyhedral domains - -This module provides classes and functions to deal with polyhedral -domains, i.e. unions of polyhedra. -""" - import ast import functools import re @@ -44,7 +37,11 @@ __all__ = [ @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__ = ( @@ -55,7 +52,27 @@ class Domain(GeometricObject): 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: @@ -88,35 +105,28 @@ class Domain(GeometricObject): @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): """ - 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): """ - 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 - 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): """ - 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)) @@ -131,7 +141,7 @@ class Domain(GeometricObject): 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)) @@ -149,7 +159,7 @@ class Domain(GeometricObject): 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) @@ -211,10 +221,18 @@ class Domain(GeometricObject): 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 - 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) @@ -223,7 +241,7 @@ class Domain(GeometricObject): 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) @@ -231,16 +249,14 @@ class Domain(GeometricObject): 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): - """ - 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) @@ -251,7 +267,8 @@ class Domain(GeometricObject): 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 @@ -269,7 +286,8 @@ class Domain(GeometricObject): 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) @@ -287,7 +305,8 @@ class Domain(GeometricObject): 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 @@ -304,7 +323,8 @@ class Domain(GeometricObject): 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 @@ -357,7 +377,8 @@ class Domain(GeometricObject): 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(): @@ -396,7 +417,9 @@ class Domain(GeometricObject): 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') @@ -414,6 +437,15 @@ class Domain(GeometricObject): 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[0].symbols @@ -467,7 +499,9 @@ class Domain(GeometricObject): 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: @@ -531,7 +565,11 @@ class Domain(GeometricObject): 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') @@ -542,19 +580,12 @@ class Domain(GeometricObject): 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): """ - 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] @@ -648,7 +679,8 @@ class Domain(GeometricObject): @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) @@ -671,9 +703,6 @@ class Domain(GeometricObject): 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)) @@ -687,7 +716,7 @@ class Domain(GeometricObject): @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 @@ -706,7 +735,7 @@ class Domain(GeometricObject): 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] @@ -714,6 +743,9 @@ class Domain(GeometricObject): def And(*domains): + """ + Create the intersection domain of the domains given in arguments. + """ 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): + """ + Create the union domain of the domains given in arguments. + """ 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): + """ + Create the complementary domain of the domain given in argument. + """ return ~domain Not.__doc__ = Domain.complement.__doc__ diff --git a/linpy/geometry.py b/linpy/geometry.py index 335a826..1a56269 100644 --- a/linpy/geometry.py +++ b/linpy/geometry.py @@ -33,30 +33,55 @@ __all__ = [ 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): + """ + The tuple of symbols present in the object expression, sorted according + to Symbol.sortkey(). + """ 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 a Polyhedron object that approximates the geometric object. + """ pass def asdomain(self): + """ + Return a Domain object that approximates the geometric object. + """ return self.aspolyhedron() class Coordinates: + """ + This class represents coordinate systems. + """ __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) @@ -72,26 +97,48 @@ class Coordinates: @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): + """ + The dimension of the coordinate system, i.e. the number of symbols + present in it. + """ return len(self.symbols) - def coordinates(self): - yield from self._coordinates.items() - 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 + def coordinates(self): + """ + Iterate over the pairs (symbol, value) of coordinates in the coordinate + system. + """ + yield from self._coordinates.items() + def values(self): + """ + Iterate over the coordinate values in the coordinate system. + """ yield from self._coordinates.values() def __bool__(self): + """ + Return True if not all coordinates are 0. + """ return any(self._coordinates.values()) def __hash__(self): @@ -121,11 +168,13 @@ class Coordinates: class Point(Coordinates, GeometricObject): """ This class represents points in space. + + Point instances are hashable and should be treated as immutable. """ def isorigin(self): """ - Return True if a Point is the origin. + Return True if all coordinates are 0. """ return not bool(self) @@ -134,7 +183,7 @@ class Point(Coordinates, GeometricObject): def __add__(self, other): """ - 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 @@ -143,7 +192,9 @@ class Point(Coordinates, GeometricObject): 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): @@ -157,15 +208,12 @@ class Point(Coordinates, GeometricObject): 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 a Point as a polyhedron. - """ from .polyhedra import Polyhedron equalities = [] for symbol, coordinate in self.coordinates(): @@ -175,10 +223,16 @@ class Point(Coordinates, GeometricObject): 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): + """ + 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: @@ -191,7 +245,7 @@ class Vector(Coordinates): def isnull(self): """ - Returns true if a Vector is null. + Return True if all coordinates are 0. """ return not bool(self) @@ -200,13 +254,59 @@ class Vector(Coordinates): def __add__(self, other): """ - 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)): coordinates = self._map2(other, operator.add) 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 @@ -220,7 +320,8 @@ class Vector(Coordinates): 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') @@ -235,19 +336,9 @@ class 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): """ - 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') @@ -256,54 +347,27 @@ class Vector(Coordinates): 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 __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): """ - Normalizes a Vector. + Return the norm of the vector. """ 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): - 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() diff --git a/linpy/linexprs.py b/linpy/linexprs.py index 8267be1..82d75d0 100644 --- a/linpy/linexprs.py +++ b/linpy/linexprs.py @@ -45,12 +45,43 @@ def _polymorphic(func): 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): """ - 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: @@ -86,7 +117,8 @@ class LinExpr: 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') @@ -96,7 +128,8 @@ class LinExpr: 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) @@ -104,21 +137,23 @@ class LinExpr: @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 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): """ - 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 @@ -127,19 +162,22 @@ class LinExpr: 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 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 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) @@ -157,7 +195,7 @@ class LinExpr: @_polymorphic def __add__(self, other): """ - 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(): @@ -170,7 +208,7 @@ class LinExpr: @_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(): @@ -184,7 +222,7 @@ class LinExpr: 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) @@ -196,6 +234,9 @@ class LinExpr: __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()) @@ -206,7 +247,7 @@ class LinExpr: @_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 \ @@ -230,7 +271,8 @@ class LinExpr: 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()]) @@ -238,8 +280,19 @@ class LinExpr: 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): @@ -289,7 +342,8 @@ class LinExpr: @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) @@ -354,7 +408,8 @@ class LinExpr: @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 = [] @@ -372,7 +427,7 @@ class LinExpr: def tosympy(self): """ - Return an expression as a sympy object. + Convert the linear expression to a sympy expression. """ import sympy expr = 0 @@ -384,10 +439,17 @@ class 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): """ - 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') @@ -401,12 +463,22 @@ class Symbol(LinExpr): @property def name(self): + """ + The name of the symbol. + """ 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): @@ -417,7 +489,7 @@ class Symbol(LinExpr): def asdummy(self): """ - Return a symbol as a Dummy Symbol. + Return a new Dummy symbol instance with the same name. """ return Dummy(self.name) @@ -450,13 +522,29 @@ class Symbol(LinExpr): 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): """ - 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) @@ -487,7 +575,13 @@ class Dummy(Symbol): 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() @@ -496,7 +590,10 @@ def symbols(names): 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): @@ -514,15 +611,9 @@ class Rational(LinExpr, Fraction): @property def constant(self): - """ - Return rational as a constant. - """ return self def isconstant(self): - """ - Test whether a value is a constant. - """ return True def __bool__(self): @@ -546,9 +637,6 @@ class Rational(LinExpr, Fraction): @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) diff --git a/linpy/polyhedra.py b/linpy/polyhedra.py index 346ffff..b486be1 100644 --- a/linpy/polyhedra.py +++ b/linpy/polyhedra.py @@ -36,8 +36,11 @@ __all__ = [ 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', @@ -48,9 +51,35 @@ class Polyhedron(Domain): 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') @@ -80,21 +109,24 @@ class Polyhedron(Domain): @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 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 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 @@ -103,15 +135,9 @@ class Polyhedron(Domain): return self, def make_disjoint(self): - """ - Return a polyhedron as disjoint. - """ 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)) @@ -119,15 +145,9 @@ class Polyhedron(Domain): return universe def aspolyhedron(self): - """ - Return the polyhedral hull of a polyhedron. - """ 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: @@ -141,10 +161,6 @@ class Polyhedron(Domain): 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) @@ -158,6 +174,9 @@ class Polyhedron(Domain): 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() @@ -242,9 +261,6 @@ class Polyhedron(Domain): @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)) @@ -261,7 +277,6 @@ class Polyhedron(Domain): else: return 'And({})'.format(', '.join(strings)) - def _repr_latex_(self): strings = [] for equality in self.equalities: @@ -272,18 +287,12 @@ class Polyhedron(Domain): @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): - """ - Return a polyhedron as a sympy object. - """ import sympy constraints = [] for equality in self.equalities: @@ -294,6 +303,9 @@ class Polyhedron(Domain): class EmptyType(Polyhedron): + """ + The empty polyhedron, whose set of constraints is not satisfiable. + """ __slots__ = Polyhedron.__slots__ @@ -321,6 +333,10 @@ Empty = EmptyType() class UniverseType(Polyhedron): + """ + The universe polyhedron, whose set of constraints is always satisfiable, + i.e. is empty. + """ __slots__ = Polyhedron.__slots__ @@ -363,41 +379,42 @@ def _polymorphic(func): @_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): """ - 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): """ - 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): """ - 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): """ - 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): """ - 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]) -- 2.20.1