From 7fff25bf40e4db570565586fb49165d1675002c2 Mon Sep 17 00:00:00 2001 From: Danielle Bolan Date: Tue, 12 Aug 2014 15:10:00 +0200 Subject: [PATCH] Doc updates (not complete) --- doc/domain.rst | 62 +++++++++++++++++++++++++---- doc/linexpr.rst | 98 ++++++++++++++++++++++++++++++++++++++++++++-- doc/modules.rst | 2 +- doc/polyhedra.rst | 32 +++++++++++---- linpy/linexprs.py | 85 ++++++++++++++++++++++++++++++++++++++-- linpy/polyhedra.py | 44 +++++++++++++-------- 6 files changed, 285 insertions(+), 38 deletions(-) diff --git a/doc/domain.rst b/doc/domain.rst index b85b2d0..06eec6e 100644 --- a/doc/domain.rst +++ b/doc/domain.rst @@ -1,8 +1,21 @@ 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. @@ -14,6 +27,10 @@ Domains Module .. 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) @@ -23,9 +40,9 @@ Domains Module 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) @@ -63,7 +80,18 @@ Domains Module .. 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) @@ -106,18 +134,38 @@ Domains Module .. 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) @@ -129,4 +177,4 @@ A 2D or 3D domain can be plotted using the :meth:`plot` method. The points, vert .. 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. diff --git a/doc/linexpr.rst b/doc/linexpr.rst index b5d8069..eb2f704 100644 --- a/doc/linexpr.rst +++ b/doc/linexpr.rst @@ -4,8 +4,11 @@ Linear Expression Module 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. @@ -26,13 +29,67 @@ This class implements linear expressions. A linear expression is…. 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) @@ -43,8 +100,41 @@ This class implements linear expressions. A linear expression is…. 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 + diff --git a/doc/modules.rst b/doc/modules.rst index bf383c7..4859f2d 100644 --- a/doc/modules.rst +++ b/doc/modules.rst @@ -11,7 +11,7 @@ There are four main LinPy modules, all of them can be inherited at once with the :maxdepth: 2 linexpr.rst - polyhedra.rst domain.rst + polyhedra.rst geometry.rst diff --git a/doc/polyhedra.rst b/doc/polyhedra.rst index 1f2756b..f6f1a30 100644 --- a/doc/polyhedra.rst +++ b/doc/polyhedra.rst @@ -1,33 +1,51 @@ 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. diff --git a/linpy/linexprs.py b/linpy/linexprs.py index aedf170..bc36fda 100644 --- a/linpy/linexprs.py +++ b/linpy/linexprs.py @@ -49,6 +49,9 @@ class Expression: """ def __new__(cls, coefficients=None, constant=0): + """ + Create a new expression. + """ if isinstance(coefficients, str): if constant != 0: raise TypeError('too many arguments') @@ -82,6 +85,9 @@ class Expression: 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)) @@ -89,31 +95,52 @@ class Expression: __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) @@ -129,6 +156,9 @@ class Expression: @_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 @@ -139,6 +169,9 @@ class Expression: @_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 @@ -150,6 +183,9 @@ class Expression: 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()) @@ -169,8 +205,9 @@ class Expression: @_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 @@ -192,11 +229,18 @@ class Expression: 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() @@ -244,6 +288,9 @@ class Expression: @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') @@ -306,6 +353,9 @@ class Expression: @classmethod def fromsympy(cls, expr): + """ + Convert sympy object to an expression. + """ import sympy coefficients = [] constant = 0 @@ -321,6 +371,9 @@ class Expression: return Expression(coefficients, constant) def tosympy(self): + """ + Return an expression as a sympy object. + """ import sympy expr = 0 for symbol, coefficient in self.coefficients(): @@ -333,6 +386,9 @@ class Expression: 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) @@ -360,6 +416,9 @@ class Symbol(Expression): return self.sortkey() == other.sortkey() def asdummy(self): + """ + Return a symbol as a Dummy Symbol. + """ return Dummy(self.name) @classmethod @@ -390,10 +449,15 @@ class Symbol(Expression): 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): @@ -422,12 +486,18 @@ class Dummy(Symbol): 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) @@ -444,9 +514,15 @@ class Rational(Expression, 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): @@ -470,6 +546,9 @@ class Rational(Expression, 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 e9226f2..8eddb2d 100644 --- a/linpy/polyhedra.py +++ b/linpy/polyhedra.py @@ -35,7 +35,9 @@ __all__ = [ class Polyhedron(Domain): - + """ + Polyhedron class allows users to build and inspect polyherons. Polyhedron inherits from Domain. + """ __slots__ = ( '_equalities', '_inequalities', @@ -45,6 +47,10 @@ 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. + """ + if isinstance(equalities, str): if inequalities is not None: raise TypeError('too many arguments') @@ -74,21 +80,21 @@ class Polyhedron(Domain): @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 @@ -96,15 +102,15 @@ class Polyhedron(Domain): 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) @@ -114,11 +120,14 @@ class Polyhedron(Domain): 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: @@ -233,6 +242,9 @@ 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 +273,7 @@ class Polyhedron(Domain): @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): @@ -270,7 +282,7 @@ class Polyhedron(Domain): def tosympy(self): """ - Return an expression as a sympy object. + Return a polyhedron as a sympy object. """ import sympy constraints = [] @@ -351,41 +363,41 @@ def _polymorphic(func): @_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]) -- 2.20.1