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.
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.
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.
.. method:: widen(polyhedron)
- Compute the standard widening of two polyhedra, à la Halbwachs.
+ Compute the *standard widening* of two polyhedra, à la Halbwachs.
.. data:: Empty
.. 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
.. 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()
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.
.. 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.
.. 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.
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 ``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.
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.
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()
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
__all__ = [
'LinExpr', 'Symbol', 'Dummy', 'symbols', 'Rational',
- 'Point', 'Vector',
+ 'GeometricObject', 'Point', 'Vector',
'Polyhedron', 'Eq', 'Ne', 'Le', 'Lt', 'Ge', 'Gt', 'Empty', 'Universe',
'Domain', 'And', 'Or', 'Not',
]
# 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
@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__ = (
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:
@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))
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))
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)
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)
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)
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)
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
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)
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
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
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():
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')
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
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:
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')
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]
@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)
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))
@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
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]
def And(*domains):
+ """
+ Create the intersection domain of the domains given in arguments.
+ """
if len(domains) == 0:
from .polyhedra import Universe
return Universe
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
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__
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)
@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):
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)
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
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):
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():
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:
def isnull(self):
"""
- Returns true if a Vector is null.
+ Return True if all coordinates are 0.
"""
return not bool(self)
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
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')
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')
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()
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:
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')
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)
@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
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)
@_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():
@_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():
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)
__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())
@_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 \
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()])
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):
@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)
@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 = []
def tosympy(self):
"""
- Return an expression as a sympy object.
+ Convert the linear expression to a sympy expression.
"""
import sympy
expr = 0
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')
@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):
def asdummy(self):
"""
- Return a symbol as a Dummy Symbol.
+ Return a new Dummy symbol instance with the same name.
"""
return Dummy(self.name)
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)
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()
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):
@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):
@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)
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',
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')
@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
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))
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:
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)
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()
@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))
else:
return 'And({})'.format(', '.join(strings))
-
def _repr_latex_(self):
strings = []
for equality in self.equalities:
@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:
class EmptyType(Polyhedron):
+ """
+ The empty polyhedron, whose set of constraints is not satisfiable.
+ """
__slots__ = Polyhedron.__slots__
class UniverseType(Polyhedron):
+ """
+ The universe polyhedron, whose set of constraints is always satisfiable,
+ i.e. is empty.
+ """
__slots__ = Polyhedron.__slots__
@_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])
projects / linpy.git / commitdiff