Domains Module
==============
+This module provides classes and functions to deal with polyhedral
+domains, i.e. unions of polyhedra.
+
.. py:class :: Domain
+ This class represents polyhedral domains, i.e. unions of polyhedra.
+
+ .. py:method:: __new__(cls, *polyhedra)
+
+ Create and return a new domain from a string or a list of polyhedra.
+
+ .. attribute:: polyhedra
+
+ The tuple of polyhedra which constitute the domain.
+
.. attribute:: symbols
Returns a tuple of the symbols that exsist in a domain.
.. py:method:: isempty(self)
Return ``True`` is a domain is empty.
+
+ .. py:method:: __bool__(self)
+
+ Return ``True`` if the domain is non-empty.
.. py:method:: isuniverse(self)
Return ``True`` if a domain is bounded.
- .. py:method:: disjoint(self)
+ .. py:method:: make_disjoint(self)
- It is not guarenteed that a domain is disjoint. If it is necessary, this method will return a domain as disjoint.
+ It is not guarenteed that a domain is disjoint. If it is necessary, this method will return an equivalent domain, whose polyhedra are disjoint.
.. py:method:: isdisjoint(self, other)
.. py:method:: complement(self)
~self
- Return the complement of a domain.
+ Return the complementary domain of a domain.
+
+ .. py:method:: coalesce(self)
+
+ Simplify the representation of the domain by trying to combine pairs of
+ polyhedra into a single polyhedron.
+
+
+ .. py:method:: detect_equalities(self)
+
+ Simplify the representation of the domain by detecting implicit
+ equalities.
.. py:method:: simplify(self)
.. py:method:: lexmin(self)
- Return a new set containing the lexicographic minimum of the elements in the set.
+ Return a new domain containing the lexicographic minimum of the elements in the domain.
.. py:method:: lexmax(self)
- Return a new set containing the lexicographic maximum of the elements in the set.
+ Return a new domain containing the lexicographic maximum of the elements in the domain.
+
+ .. py:method:: subs(self, symbol, expression=None):
+
+ Subsitute symbol by expression in equations and return the resulting
+ domain.
+ .. py:method:: fromstring(cls, string)
+
+ Convert a string into a domain.
+
+ .. py:method:: fromsympy(cls, expr)
+
+ Convert a SymPy expression into a domain.
+
+ .. py:method:: tosympy(self)
+
+ Convert a domain into a SymPy expression.
A 2D or 3D domain can be plotted using the :meth:`plot` method. The points, vertices, and faces of a domain can be inspected using the following functions.
.. py:method:: points(self)
- Return a list of the points contained in a domain as :class:`Points` objects.
+ Return a list of the points with integer coordinates contained in a domain as :class:`Points` objects.
+
+ .. py:method:: __contains__(self, point)
+
+ Return ``True`` if point if contained within the domain.
.. py:method:: vertices(self)
.. py:method:: plot(self, plot=None, **kwargs)
- Return a plot of the given domain or add a plot to a plot instance.
+ Return a plot of the given domain or add a plot to a plot instance, using matplotlib.
This class implements linear expressions. A linear expression is….
.. py:class:: Expression
-
-
+
+ .. py:method:: __new__(cls, coefficients=None, constant=0)
+
+ Create and return a new linear expression from a string or a list of coefficients and a constant.
+
.. py:method:: coefficient(self, symbol)
Return the coefficient value of the given symbol.
Return the number of variables in an expression.
+ .. py:method:: isconstant(self)
+
+ Return ``True`` if an expression is a constant.
+
+ .. py:method:: issymbol(self)
+
+ Return ``True`` if an expression is a symbol.
+
+
+ .. py:method:: values(self)
+
+ Return the coefficient and constant values of an expression.
+
+ .. py:method:: __add__(self, other)
+
+ Return the sum of *self* and *other*.
+
.. py:method:: __sub__(self, other)
Return the difference between *self* and *other*.
-
+
+ .. py:method:: __mul__(self, other)
+
+ Return the product of *self* and *other* if *other* is a rational number.
+
+ .. py:method:: __eq__(self, other)
+
+ Test whether two expressions are equal.
+
+ .. py:method:: __le__(self, other)
+ self <= other
+
+ Create a new polyhedra from an expression with a single constraint as *self* less than or equal to *other*.
+
+ .. py:method:: __lt__(self, other)
+ self < other
+
+ Create a new polyhedra from an expression with a single constraint as *self* less than *other*.
+
+ .. py:method:: __ge__(self, other)
+ self >= other
+
+ Create a new polyhedra from an expression with a single constraint as *self* greater than or equal to *other*.
+
+ .. py:method:: __gt__(self, other)
+ self > other
+
+ Create a new polyhedra from an expression with a single constraint as *self* greater than *other*.
+
+ .. py:method:: scaleint(self)
+
+ Multiply an expression by a scalar to make all coefficients integer values.
+
.. py:method:: subs(self, symbol, expression=None)
Subsitute the given value into an expression and return the resulting expression.
+
+
+ .. py:method:: fromstring(self)
+
+ Create an expression from a string.
.. py:method:: fromsympy(self)
Return an expression as a sympy object.
.. py:class:: Symbol(Expression)
+
+ .. py:method:: __new__(cls, name)
+
+ Create and return a symbol from a string.
+
+ .. py:method:: symbols(names)
+
+ This function returns a sequence of symbols with names taken from names argument, which can be a comma or whitespace delimited string, or a sequence of strings.
+ .. py:method:: asdummy(self)
+
+ Return a symbol as a :class:`Dummy` Symbol.
.. py:class:: Dummy(Symbol)
-This class returns a dummy symbol to ensure that each no variables are repeated in an expression
+ This class returns a dummy symbol to ensure that no variables are repeated in an expression. This is useful when the user needs to have a unique symbol, for example as a temporary one in some calculation, which is going to be substituted for something else at the end anyway.
+
+ .. py:method:: __new__(cls, name=None)
+
+ Create and return a new dummy symbol.
+
+
+.. py:class:: Rational(Expression, Fraction)
+
+ This class represents integers and rational numbers of any size.
+
+ .. attribute:: constant
+
+ Return rational as a constant.
+
+ .. py:method:: isconstant(self)
+
+ Test whether a value is a constant.
+
+ .. py:method:: fromsympy(cls, expr)
+
+ Create a rational object from a sympy expression
+
:maxdepth: 2
linexpr.rst
- polyhedra.rst
domain.rst
+ polyhedra.rst
geometry.rst
Polyhedra Module
================
-Polyhedron class allows users to build and inspect polyherons.
+Polyhedron class allows users to build and inspect polyherons. Polyhedron inherits all methods from the :class:`Domain` class.
-.. py:class:: Polyhedron
+.. py:class:: Polyhedron(Domain)
- .. py:property:: equalities
+ .. py:method:: __new__(cls, equalities=None, inequalities=None)
+
+ Create and return a new Polyhedron from a string or list of equalities and inequalities.
+
+ .. attribute:: equalities
Returns a list of the equalities in a polyhedron.
- .. py:property:: inequalities
+ .. attribute:: inequalities
Returns a list of the inequalities in a polyhedron.
- .. py:property:: constraints
+ .. attribute:: constraints
Returns a list of the constraints of a polyhedron.
- .. py:method:: disjoint(self)
+ .. py:method:: make_disjoint(self)
Returns a polyhedron as a disjoint.
.. py:method:: isuniverse(self)
Return ``True`` if a polyhedron is the Universe set.
+
+ .. py:method:: aspolyhedron(self)
+
+ Return the polyhedral hull of a polyhedron.
+
+ .. py:method:: __contains__(self, point)
+
+ Report whether a polyhedron constains an integer point
.. py:method:: subs(self, symbol, expression=None)
- Substitutes an expression into a polyhedron and returns the result.
+ Subsitute the given value into an expression and return the resulting
+ expression.
+
+ .. py:method:: fromstring(cls, string)
+
+ Create and return a Polyhedron from a string.
+
To create a polyhedron, the user can use the following functions to define equalities and inequalities as the constraints.
"""
def __new__(cls, coefficients=None, constant=0):
+ """
+ Create a new expression.
+ """
if isinstance(coefficients, str):
if constant != 0:
raise TypeError('too many arguments')
return self
def coefficient(self, symbol):
+ """
+ Return the coefficient value of the given symbol.
+ """
if not isinstance(symbol, Symbol):
raise TypeError('symbol must be a Symbol instance')
return Rational(self._coefficients.get(symbol, 0))
__getitem__ = coefficient
def coefficients(self):
+ """
+ Return a list of the coefficients of an expression
+ """
for symbol, coefficient in self._coefficients.items():
yield symbol, Rational(coefficient)
@property
def constant(self):
+ """
+ Return the constant value of an expression.
+ """
return Rational(self._constant)
@property
def symbols(self):
+ """
+ Return a list of symbols in an expression.
+ """
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.
+ """
return self._dimension
def __hash__(self):
return hash((tuple(self._coefficients.items()), self._constant))
def isconstant(self):
+ """
+ Return true if an expression is a constant.
+ """
return False
def issymbol(self):
+ """
+ Return true if an expression is a symbol.
+ """
return False
def values(self):
+ """
+ Return the coefficient and constant values of an expression.
+ """
for coefficient in self._coefficients.values():
yield Rational(coefficient)
yield Rational(self._constant)
@_polymorphic
def __add__(self, other):
+ """
+ Return the sum of two expressions.
+ """
coefficients = defaultdict(Fraction, self._coefficients)
for symbol, coefficient in other._coefficients.items():
coefficients[symbol] += coefficient
@_polymorphic
def __sub__(self, other):
+ """
+ Return the difference between two expressions.
+ """
coefficients = defaultdict(Fraction, self._coefficients)
for symbol, coefficient in other._coefficients.items():
coefficients[symbol] -= coefficient
return other - self
def __mul__(self, other):
+ """
+ Return the product of two expressions if other is a rational number.
+ """
if isinstance(other, numbers.Rational):
coefficients = ((symbol, coefficient * other)
for symbol, coefficient in self._coefficients.items())
@_polymorphic
def __eq__(self, other):
- # returns a boolean, not a constraint
- # see http://docs.sympy.org/dev/tutorial/gotchas.html#equals-signs
+ """
+ Test whether two expressions are equal
+ """
return isinstance(other, Expression) and \
self._coefficients == other._coefficients and \
self._constant == other._constant
return Gt(self, other)
def scaleint(self):
+ """
+ Multiply an expression by a scalar to make all coefficients integer values.
+ """
lcm = functools.reduce(lambda a, b: a*b // gcd(a, b),
[value.denominator for value in self.values()])
return self * lcm
def subs(self, symbol, expression=None):
+ """
+ Subsitute symbol by expression in equations and return the resulting
+ expression.
+ """
if expression is None:
if isinstance(symbol, Mapping):
symbol = symbol.items()
@classmethod
def fromstring(cls, string):
+ """
+ Create an expression from a string.
+ """
# add implicit multiplication operators, e.g. '5x' -> '5*x'
string = Expression._RE_NUM_VAR.sub(r'\1*\2', string)
tree = ast.parse(string, 'eval')
@classmethod
def fromsympy(cls, expr):
+ """
+ Convert sympy object to an expression.
+ """
import sympy
coefficients = []
constant = 0
return Expression(coefficients, constant)
def tosympy(self):
+ """
+ Return an expression as a sympy object.
+ """
import sympy
expr = 0
for symbol, coefficient in self.coefficients():
class Symbol(Expression):
def __new__(cls, name):
+ """
+ Create and return a symbol from a string.
+ """
if not isinstance(name, str):
raise TypeError('name must be a string')
self = object().__new__(cls)
return self.sortkey() == other.sortkey()
def asdummy(self):
+ """
+ Return a symbol as a Dummy Symbol.
+ """
return Dummy(self.name)
@classmethod
class Dummy(Symbol):
-
+ """
+ This class returns a dummy symbol to ensure that no variables are repeated in an expression
+ """
_count = 0
def __new__(cls, name=None):
+ """
+ Create and return a new dummy symbol.
+ """
if name is None:
name = 'Dummy_{}'.format(Dummy._count)
elif not isinstance(name, str):
def symbols(names):
+ """
+ Transform strings into instances of the Symbol class
+ """
if isinstance(names, str):
names = names.replace(',', ' ').split()
return tuple(Symbol(name) for name in names)
class Rational(Expression, Fraction):
+ """
+ This class represents integers and rational numbers of any size.
+ """
def __new__(cls, numerator=0, denominator=None):
self = object().__new__(cls)
@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.
+ """
__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.
+ """
+
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 set.
+ Return a list of the equalities in a polyhedron.
"""
return self._equalities
@property
def inequalities(self):
"""
- Return a list of the inequalities in a set.
+ Return a list of the inequalities in a polyhedron.
"""
return self._inequalities
@property
def constraints(self):
"""
- Return ta list of the constraints of a set.
+ Return the list of the constraints of a polyhedron.
"""
return self._constraints
def polyhedra(self):
return self,
- def disjoint(self):
+ def make_disjoint(self):
"""
- Return a set as disjoint.
+ Return a polyhedron as disjoint.
"""
return self
def isuniverse(self):
"""
- Return true if a set is the Universe set.
+ Return true if a polyhedron is the Universe set.
"""
islbset = self._toislbasicset(self.equalities, self.inequalities,
self.symbols)
def aspolyhedron(self):
"""
- Return polyhedral hull of a set.
+ 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:
@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))
@classmethod
def fromsympy(cls, expr):
"""
- Convert a sympy object to an expression.
+ Convert a sympy object to a polyhedron.
"""
domain = Domain.fromsympy(expr)
if not isinstance(domain, Polyhedron):
def tosympy(self):
"""
- Return an expression as a sympy object.
+ Return a polyhedron as a sympy object.
"""
import sympy
constraints = []
@_polymorphic
def Lt(left, right):
"""
- Assert first set is less than the second set.
+ Returns a Polyhedron instance with a single constraint as left less than right.
"""
return Polyhedron([], [right - left - 1])
@_polymorphic
def Le(left, right):
"""
- Assert first set is less than or equal to the second set.
+ Returns a Polyhedron instance with a single constraint as left less than or equal to right.
"""
return Polyhedron([], [right - left])
@_polymorphic
def Eq(left, right):
"""
- Assert first set is equal to the second set.
+ Returns a Polyhedron instance with a single constraint as left equal to right.
"""
return Polyhedron([left - right], [])
@_polymorphic
def Ne(left, right):
"""
- Assert first set is not equal to the second set.
+ Returns a Polyhedron instance with a single constraint as left not equal to right.
"""
return ~Eq(left, right)
@_polymorphic
def Gt(left, right):
"""
- Assert first set is greater than the second set.
+ Returns a Polyhedron instance with a single constraint as left greater than right.
"""
return Polyhedron([], [left - right - 1])
@_polymorphic
def Ge(left, right):
"""
- Assert first set is greater than or equal to the second set.
+ Returns a Polyhedron instance with a single constraint as left greater than or equal to right.
"""
return Polyhedron([], [left - right])
projects / linpy.git / commitdiff