From a08ebc700e22f6aee8147cb5b5323a6c040b12db Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Sun, 17 Aug 2014 22:25:22 +0200 Subject: [PATCH 1/1] Reformat documentation. --- doc/conf.py | 10 +- doc/domain.rst | 180 ------------ doc/examples.rst | 198 ++++++------- doc/geometry.rst | 79 ------ doc/index.rst | 29 +- doc/install.rst | 53 ++-- doc/linexpr.rst | 140 ---------- doc/modules.rst | 17 -- doc/polyhedra.rst | 74 ----- doc/reference.rst | 695 ++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 849 insertions(+), 626 deletions(-) delete mode 100644 doc/domain.rst delete mode 100644 doc/geometry.rst delete mode 100644 doc/linexpr.rst delete mode 100644 doc/modules.rst delete mode 100644 doc/polyhedra.rst create mode 100644 doc/reference.rst diff --git a/doc/conf.py b/doc/conf.py index 23a1b91..ed93095 100644 --- a/doc/conf.py +++ b/doc/conf.py @@ -29,9 +29,7 @@ import os # Add any Sphinx extension module names here, as strings. They can be # extensions coming with Sphinx (named 'sphinx.ext.*') or your custom # ones. -extensions = [ - 'sphinx.ext.mathjax', -] +extensions = [] # Add any paths that contain templates here, relative to this directory. templates_path = ['_templates'] @@ -54,9 +52,9 @@ copyright = '2014, MINES ParisTech' # built documents. # # The short X.Y version. -version = '' +version = '1.0' # The full version, including alpha/beta/rc tags. -release = '' +release = '1.0a' # The language for content autogenerated by Sphinx. Refer to documentation # for a list of supported languages. @@ -244,7 +242,7 @@ man_pages = [ # dir menu entry, description, category) texinfo_documents = [ ('index', 'LinPy', 'LinPy Documentation', - 'MINES ParisTech', 'LinPy', 'One line description of project.', + 'MINES ParisTech', 'LinPy', 'A polyheral library based on ISL.', 'Miscellaneous'), ] diff --git a/doc/domain.rst b/doc/domain.rst deleted file mode 100644 index 06eec6e..0000000 --- a/doc/domain.rst +++ /dev/null @@ -1,180 +0,0 @@ -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. - - .. attribute:: dimension - - Returns the number of variables that exist 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 the Universe set. - - .. py:method:: isbounded(self) - - Return ``True`` if a domain is bounded. - - .. py:method:: make_disjoint(self) - - 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) - - Return ``True`` if the intersection of *self* and *other* results in an empty set. - - .. py:method:: issubset(self, other) - - Test whether every element in a domain is in *other*. - - .. py:method:: __eq__(self, other) - self == other - - Test whether a domain is equal to *other*. - - .. py:method:: __lt__(self, other) - self < other - - Test whether a domain is a strict subset of *other*. - - .. py:method:: __le__(self, other) - self <= other - - Test whether every element in a domain is in *other*. - - .. py:method:: __gt__(self, other) - self > other - - Test whether a domain is a strict superset of *other*. - - .. py:method:: __ge__(self, other) - self >= other - - Test whether every element in *other* is in a domain. - - .. py:method:: complement(self) - ~self - - 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) - - Return a new domain without any redundant constraints. - - .. py:method:: project(self, variables) - - Return a new domain with the given variables removed. - - .. py:method:: aspolyhedron(self) - - Return polyhedral hull of a domain. - - .. py:method:: sample(self) - - Return a single sample subset of a domain. - - .. py:method:: intersection(self, other) - __or__ - self | other - - Return a new domain with the elements that are common between *self* and *other*. - - .. py:method:: union(self, other) - __and__ - self & other - - Return a new domain with all the elements from *self* and *other*. - - .. py:method:: difference(self, other) - __sub__ - self - other - - Return a new domain with the elements in a domain that are not in *other* . - - .. py:method:: __add__(self, other) - self + other - - Return the sum of two domains. - - .. py:method:: lexmin(self) - - Return a new domain containing the lexicographic minimum of the elements in the domain. - - .. py:method:: lexmax(self) - - 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 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) - - Return a list of the verticies of a domain. - - .. py:method:: faces(self) - - Return a list of the vertices for each face of a domain. - - .. py:method:: plot(self, plot=None, **kwargs) - - Return a plot of the given domain or add a plot to a plot instance, using matplotlib. diff --git a/doc/examples.rst b/doc/examples.rst index 3d2626d..b552b7f 100644 --- a/doc/examples.rst +++ b/doc/examples.rst @@ -1,112 +1,118 @@ -LinPy Examples -============== + +.. _examples: + +Examples +======== Basic Examples -------------- - To create any polyhedron, first define the symbols used. Then use the polyhedron functions to define the constraints. The following is a simple running example illustrating some different operations and properties that can be performed by LinPy with two squares. - - >>> from linpy import * - >>> x, y = symbols('x y') - >>> # define the constraints of the polyhedron - >>> square1 = Le(0, x) & Le(x, 2) & Le(0, y) & Le(y, 2) - >>> square1 - And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)) - - Binary operations and properties examples: - - >>> # create a polyhedron from a string - >>> square2 = Polyhedron('1 <= x') & Polyhedron('x <= 3') & \ - Polyhedron('1 <= y') & Polyhedron('y <= 3') - >>> #test equality - >>> square1 == square2 - False - >>> # compute the union of two polyhedrons - >>> square1 | square2 - Or(And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)), \ +To create any polyhedron, first define the symbols used. +Then use the polyhedron functions to define the constraints. +The following is a simple running example illustrating some different operations and properties that can be performed by LinPy with two squares. + +>>> from linpy import * +>>> x, y = symbols('x y') +>>> # define the constraints of the polyhedron +>>> square1 = Le(0, x) & Le(x, 2) & Le(0, y) & Le(y, 2) +>>> square1 +And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)) + +Binary operations and properties examples: + +>>> # create a polyhedron from a string +>>> square2 = Polyhedron('1 <= x') & Polyhedron('x <= 3') & \ + Polyhedron('1 <= y') & Polyhedron('y <= 3') +>>> #test equality +>>> square1 == square2 +False +>>> # compute the union of two polyhedra +>>> square1 | square2 +Or(And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0)), \ And(Ge(x - 1, 0), Ge(-x + 3, 0), Ge(y - 1, 0), Ge(-y + 3, 0))) - >>> # check if square1 and square2 are disjoint - >>> square1.disjoint(square2) - False - >>> # compute the intersection of two polyhedrons - >>> square1 & square2 - And(Ge(x - 1, 0), Ge(-x + 2, 0), Ge(y - 1, 0), Ge(-y + 2, 0)) - >>> # compute the convex union of two polyhedrons - >>> Polyhedron(square1 | sqaure2) - And(Ge(x, 0), Ge(y, 0), Ge(-y + 3, 0), Ge(-x + 3, 0), \ +>>> # check if square1 and square2 are disjoint +>>> square1.disjoint(square2) +False +>>> # compute the intersection of two polyhedra +>>> square1 & square2 +And(Ge(x - 1, 0), Ge(-x + 2, 0), Ge(y - 1, 0), Ge(-y + 2, 0)) +>>> # compute the convex union of two polyhedra +>>> Polyhedron(square1 | sqaure2) +And(Ge(x, 0), Ge(y, 0), Ge(-y + 3, 0), Ge(-x + 3, 0), \ Ge(x - y + 2, 0), Ge(-x + y + 2, 0)) - Unary operation and properties examples: +Unary operation and properties examples: - >>> square1.isempty() - False - >>> # compute the complement of square1 - >>> ~square1 - Or(Ge(-x - 1, 0), Ge(x - 3, 0), And(Ge(x, 0), Ge(-x + 2, 0), \ +>>> square1.isempty() +False +>>> # compute the complement of square1 +>>> ~square1 +Or(Ge(-x - 1, 0), Ge(x - 3, 0), And(Ge(x, 0), Ge(-x + 2, 0), \ Ge(-y - 1, 0)), And(Ge(x, 0), Ge(-x + 2, 0), Ge(y - 3, 0))) - >>> square1.symbols() - (x, y) - >>> square1.inequalities - (x, -x + 2, y, -y + 2) - >>> # project out the variable x - >>> square1.project([x]) - And(Ge(-y + 2, 0), Ge(y, 0)) +>>> square1.symbols() +(x, y) +>>> square1.inequalities +(x, -x + 2, y, -y + 2) +>>> # project out the variable x +>>> square1.project([x]) +And(Ge(-y + 2, 0), Ge(y, 0)) Plot Examples ------------- - LinPy uses matplotlib plotting library to plot 2D and 3D polygons. The user has the option to pass subplots to the :meth:`plot` method. This can be a useful tool to compare polygons. Also, key word arguments can be passed such as color and the degree of transparency of a polygon. - - >>> import matplotlib.pyplot as plt - >>> from matplotlib import pylab - >>> from mpl_toolkits.mplot3d import Axes3D - >>> from linpy import * - >>> # define the symbols - >>> x, y, z = symbols('x y z') - >>> fig = plt.figure() - >>> cham_plot = fig.add_subplot(1, 1, 1, projection='3d', aspect='equal') - >>> cham_plot.set_title('Chamfered cube') - >>> cham = Le(0, x) & Le(x, 3) & Le(0, y) & Le(y, 3) & Le(0, z) & \ - Le(z, 3) & Le(z - 2, x) & Le(x, z + 2) & Le(1 - z, x) & \ - Le(x, 5 - z) & Le(z - 2, y) & Le(y, z + 2) & Le(1 - z, y) & \ - Le(y, 5 - z) & Le(y - 2, x) & Le(x, y + 2) & Le(1 - y, x) & Le(x, 5 - y) - >>> cham.plot(cham_plot, facecolor='red', alpha=0.75) - >>> pylab.show() - - .. figure:: images/cham_cube.jpg - :align: center +LinPy can use the matplotlib plotting library to plot 2D and 3D polygons. +This can be a useful tool to visualize and compare polygons. +The user has the option to pass plot objects to the :meth:`Domain.plot` method, which provides great flexibility. +Also, keyword arguments can be passed such as color and the degree of transparency of a polygon. + +>>> import matplotlib.pyplot as plt +>>> from matplotlib import pylab +>>> from mpl_toolkits.mplot3d import Axes3D +>>> from linpy import * +>>> # define the symbols +>>> x, y, z = symbols('x y z') +>>> fig = plt.figure() +>>> cham_plot = fig.add_subplot(1, 1, 1, projection='3d', aspect='equal') +>>> cham_plot.set_title('Chamfered cube') +>>> cham = Le(0, x) & Le(x, 3) & Le(0, y) & Le(y, 3) & Le(0, z) & \ + Le(z, 3) & Le(z - 2, x) & Le(x, z + 2) & Le(1 - z, x) & \ + Le(x, 5 - z) & Le(z - 2, y) & Le(y, z + 2) & Le(1 - z, y) & \ + Le(y, 5 - z) & Le(y - 2, x) & Le(x, y + 2) & Le(1 - y, x) & Le(x, 5 - y) +>>> cham.plot(cham_plot, facecolor='red', alpha=0.75) +>>> pylab.show() + +.. figure:: images/cham_cube.jpg + :align: center LinPy can also inspect a polygon's vertices and the integer points included in the polygon. - >>> diamond = Ge(y, x - 1) & Le(y, x + 1) & Ge(y, -x - 1) & Le(y, -x + 1) - >>> diamond.vertices() - [Point({x: Fraction(0, 1), y: Fraction(1, 1)}), \ - Point({x: Fraction(-1, 1), y: Fraction(0, 1)}), \ - Point({x: Fraction(1, 1), y: Fraction(0, 1)}), \ - Point({x: Fraction(0, 1), y: Fraction(-1, 1)})] - >>> diamond.points() - [Point({x: -1, y: 0}), Point({x: 0, y: -1}), Point({x: 0, y: 0}), \ - Point({x: 0, y: 1}), Point({x: 1, y: 0})] - -The user also can pass another plot to the :meth:`plot` method. This can be useful to compare two polyhedrons on the same axis. This example illustrates the union of two squares. - - >>> from linpy import * - >>> import matplotlib.pyplot as plt - >>> from matplotlib import pylab - >>> x, y = symbols('x y') - >>> square1 = Le(0, x) & Le(x, 2) & Le(0, y) & Le(y, 2) - >>> square2 = Le(1, x) & Le(x, 3) & Le(1, y) & Le(y, 3) - >>> fig = plt.figure() - >>> plot = fig.add_subplot(1, 1, 1, aspect='equal') - >>> square1.plot(plot, facecolor='red', alpha=0.3) - >>> square2.plot(plot, facecolor='blue', alpha=0.3) - >>> squares = Polyhedron(square1 + square2) - >>> squares.plot(plot, facecolor='blue', alpha=0.3) - >>> pylab.show() - - .. figure:: images/union.jpg - :align: center - - - - +>>> diamond = Ge(y, x - 1) & Le(y, x + 1) & Ge(y, -x - 1) & Le(y, -x + 1) +>>> diamond.vertices() +[Point({x: Fraction(0, 1), y: Fraction(1, 1)}), \ + Point({x: Fraction(-1, 1), y: Fraction(0, 1)}), \ + Point({x: Fraction(1, 1), y: Fraction(0, 1)}), \ + Point({x: Fraction(0, 1), y: Fraction(-1, 1)})] +>>> diamond.points() +[Point({x: -1, y: 0}), Point({x: 0, y: -1}), Point({x: 0, y: 0}), \ + Point({x: 0, y: 1}), Point({x: 1, y: 0})] + +The user also can pass another plot to the :meth:`Domain.plot` method. +This can be useful to compare two polyhedra on the same axis. +This example illustrates the union of two squares. + +>>> from linpy import * +>>> import matplotlib.pyplot as plt +>>> from matplotlib import pylab +>>> x, y = symbols('x y') +>>> square1 = Le(0, x) & Le(x, 2) & Le(0, y) & Le(y, 2) +>>> square2 = Le(1, x) & Le(x, 3) & Le(1, y) & Le(y, 3) +>>> fig = plt.figure() +>>> plot = fig.add_subplot(1, 1, 1, aspect='equal') +>>> square1.plot(plot, facecolor='red', alpha=0.3) +>>> square2.plot(plot, facecolor='blue', alpha=0.3) +>>> squares = Polyhedron(square1 + square2) +>>> squares.plot(plot, facecolor='blue', alpha=0.3) +>>> pylab.show() + +.. figure:: images/union.jpg + :align: center diff --git a/doc/geometry.rst b/doc/geometry.rst deleted file mode 100644 index 838ec6e..0000000 --- a/doc/geometry.rst +++ /dev/null @@ -1,79 +0,0 @@ -Geometry Module -=============== - -The geometry module is used to obtain information about the points and vertices of a ployhedra. - -.. py:class:: Points - -This class represents points in space. - - .. py:method:: isorigin(self) - - Return ``True`` if a point is the origin. - - .. py:method:: __eq__(self, other) - - Compare two Points for equality. - - .. py:method:: __add__(self, other) - - Add a Point to a Vector and return the result as a Point. - - .. py:method:: __sub__(self, other) - - Return the difference between two Points as a Vector. - - .. py:method:: aspolyhedon(self) - - Return a Point as a polyhedron corresponding to the Point, assuming the Point has integer coordinates. - - -.. py:class:: Vector - -This class represents displacements in space. - - .. py:method:: __eq__(self, other) - - Compare two Vectors for equality. - - .. py:method:: __add__(self, other) - - Add either a Point or Vector to a Vector. The resulting sum is returned as the same structure *other* is. - - .. py:method:: __sub__(self, other) - - Subtract a Point or Vector from a Vector. The resulting difference is returned in the same form as *other*. - - .. py:method:: __mul__(self, other) - - Multiply a Vector by a scalar value and returns the result as a Vector. - - .. py:method:: __neg__(self) - - Negate a Vector. - - .. py:method:: norm(self) - - Normalizes a Vector. - - .. py:method:: isnull(self) - - Tests whether a Vector is null. - - .. py:method:: angle(self, other) - - Retrieve the angle required to rotate the vector into the vector passed in argument. The result is an angle in radians, ranging between -pi and - pi. - - .. py:method:: cross(self, other) - - Calculate the cross product of two Vector3D structures. If the vectors are not tridimensional, a _____ error is raised. - - .. py:method:: dot(self, other) - - Calculate the dot product of two vectors. - - .. py:method:: __trudiv__(self, other) - - Divide the vector by the specified scalar and returns the result as a vector. - diff --git a/doc/index.rst b/doc/index.rst index b3a9271..ad985bf 100644 --- a/doc/index.rst +++ b/doc/index.rst @@ -1,25 +1,30 @@ -.. LinPy documentation master file, created by - sphinx-quickstart on Wed Jun 25 20:34:21 2014. - You can adapt this file completely to your liking, but it should at least - contain the root `toctree` directive. Welcome to LinPy’s documentation! ================================= -LinPy is a Python wrapper for the Integer Set Library (isl) by Sven Verdoolaege. Isl ia a C library for manipulating sets and relations of integer points bounded by linear constraints. +LinPy is a polyhedral library for Python based on `isl `_. +isl (Integer Set Library) is a C library for manipulating sets and relations of integer points bounded by linear constraints. -If you are new to LinPy, start with the Examples. +LinPy is a free software, licensed under the `GPLv3 license `_. +Its source code is available `here `_. -This is the central page for all of LinPy’s documentation. +To have an overview of LinPy's functionalities, you may wish to consult the :ref:`examples` section. -Contents: +.. only:: html + + Contents: .. toctree:: - :maxdepth: 2 + :maxdepth: 2 - install.rst - examples.rst - modules.rst + install.rst + examples.rst + reference.rst +.. only:: html + Indices and tables + ================== + * :ref:`genindex` + * :ref:`search` diff --git a/doc/install.rst b/doc/install.rst index d1b9f1f..040029d 100644 --- a/doc/install.rst +++ b/doc/install.rst @@ -1,38 +1,36 @@ -.. _installation: Installation ------------- -Source -====== +============ -Users can install LinPy by cloning the git repository:: +Dependencies +------------ - git clone https://scm.cri.ensmp.fr/git/linpy.git +LinPy requires Python version 3.4 or above to work. -Then, execute the following to complete installation:: - - python3 setup.py install +LinPy's one mandatory dependency is isl version 0.12 or 0.13 (it may work with other versions of isl, but this has not been tested). +isl can be downloaded `here `_ or preferably, using your favorite distribution's package manager. +For Ubuntu, the command to run is:: -PyPi -==== + sudo apt-get install libisl-dev - sudo pip install linpy +For Arch Linux, run:: -Dependencies -============ + sudo pacman -S isl -LinPy's one mandatory dependency is isl, which can be downloaded from `here`_ or using package manager, e.g for ubuntu:: +Apart from isl, there are two optional dependencies that will maximize the use of LinPy's functions: `SymPy `_ and `matplotlib `_. +Please consult the `SymPy download page `_ and `matplotlib installation instructions `_ to install these libraries. - sudo apt-get install libisl­-dev +pip +--- -There are two optional dependencies that will maximize the use of LinPy's -functions; SymPy and matplotlib. SymPy installation instructions can be found on the SymPy `download page`_. Matplotlib install information can be found at this `link`_. +.. warning:: -License -======= + The project has not been published in PyPI yet, so this section is not relevant. + Instead, see the :ref:`source` section to install LinPy. -LinPy is a free software, licensed under the `GPLv3 license`_ . +LinPy can be installed using pip with the command:: + sudo pip install linpy .. _here: http://freshmeat.net/projects/isl/ @@ -40,5 +38,16 @@ LinPy is a free software, licensed under the `GPLv3 license`_ . .. _link: http://matplotlib.org/faq/installing_faq.html -.. _GPLv3 license: https://www.gnu.org/licenses/gpl-3.0.txt +.. _source: + +Source +------ + +Alternatively, LinPy can be installed from source. +First, clone the public git repository:: + + git clone https://scm.cri.ensmp.fr/git/linpy.git + +and build and install as usual with:: + sudo python3 setup.py install diff --git a/doc/linexpr.rst b/doc/linexpr.rst deleted file mode 100644 index eb2f704..0000000 --- a/doc/linexpr.rst +++ /dev/null @@ -1,140 +0,0 @@ -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. - - .. py:method:: coefficients(self) - - Return a list of the coefficients of an expression - - .. attribute:: constant - - Return the constant value of an expression. - - .. attribute:: symbols - - Return a list of symbols in an expression. - - .. attribute:: dimension - - 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) - - Convert sympy object to an expression. - - .. py:method:: tosympy(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 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 deleted file mode 100644 index 4859f2d..0000000 --- a/doc/modules.rst +++ /dev/null @@ -1,17 +0,0 @@ -.. module-docs: - -LinPy Module Reference -====================== - -There are four main LinPy modules, all of them can be inherited at once with the LinPy package: - - >>> from linpy import * - -.. toctree:: - :maxdepth: 2 - - linexpr.rst - domain.rst - polyhedra.rst - geometry.rst - diff --git a/doc/polyhedra.rst b/doc/polyhedra.rst deleted file mode 100644 index f6f1a30..0000000 --- a/doc/polyhedra.rst +++ /dev/null @@ -1,74 +0,0 @@ -Polyhedra Module -================ - -Polyhedron class allows users to build and inspect polyherons. Polyhedron inherits all methods from the :class:`Domain` class. - -.. py:class:: Polyhedron(Domain) - - .. 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. - - .. attribute:: inequalities - - Returns a list of the inequalities in a polyhedron. - - .. attribute:: constraints - - Returns a list of the constraints of a polyhedron. - - .. 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) - - 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. - -.. py:function:: Eq(left, right) - - Returns a Polyhedron instance with a single constraint as *left* equal to *right*. - -.. py:function:: Ne(left, right) - - Returns a Polyhedron instance with a single constraint as *left* not equal to *right*. - -.. py:function:: Lt(left, right) - - Returns a Polyhedron instance with a single constraint as *left* less than *right*. - -.. py:function:: Le(left, right) - - Returns a Polyhedron instance with a single constraint as *left* less than or equal to *right*. - -.. py:function:: Gt(left, right) - - Returns a Polyhedron instance with a single constraint as *left* greater than *right*. - -.. py:function:: Ge(left, right) - - Returns a Polyhedron instance with a single constraint as *left* greater than or equal to *right*. diff --git a/doc/reference.rst b/doc/reference.rst new file mode 100644 index 0000000..8184c43 --- /dev/null +++ b/doc/reference.rst @@ -0,0 +1,695 @@ + +Module Reference +================ + +Symbols +------- + +*Symbols* are the basic components to build expressions and constraints. +They correspond to mathematical variables. + +.. class:: Symbol(name) + + Return a symbol with the name string given in argument. + Alternatively, the function :func:`symbols` allows to create several symbols at once. + Symbols are instances of class :class:`LinExpr` and, as such, inherit its functionalities. + + >>> x = Symbol('x') + >>> x + x + + Two instances of :class:`Symbol` are equal if they have the same name. + + .. attribute:: name + + The name of the symbol. + + .. method:: asdummy() + + Return a new :class:`Dummy` symbol instance with the same name. + + .. method:: sortkey() + + 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 :class:`LinExpr`). + + >>> sort(symbols, key=Symbol.sortkey) + + +.. function:: symbols(names) + + 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']) + + +Sometimes, you need 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. +This is achieved using ``Dummy('x')``. + +.. class:: Dummy(name=None) + + A variation of :class:`Symbol` which are all unique, 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 :class:`Symbol`, :class:`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 + + +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 :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`. + +.. class:: LinExpr(coefficients=None, constant=0) + LinExpr(string) + + 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 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) + + although 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') + + :class:`LinExpr` instances are hashable, and should be treated as immutable. + + A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance. + A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance. + + .. method:: coefficient(symbol) + __getitem__(symbol) + + Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression. + + .. method:: coefficients() + + Iterate over the pairs ``(symbol, value)`` of linear terms in the expression. + The constant term is ignored. + + .. attribute:: constant + + The constant term of the expression. + + .. attribute:: symbols + + The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`. + + .. attribute:: dimension + + The dimension of the expression, i.e. the number of symbols present in it. + + .. method:: isconstant() + + Return ``True`` if the expression only consists of a constant term. + In this case, it is a :class:`Rational` instance. + + .. method:: issymbol() + + Return ``True`` if an expression only consists of a symbol with coefficient ``1``. + In this case, it is a :class:`Symbol` instance. + + .. method:: values() + + Iterate over the coefficient values in the expression, and the constant term. + + .. method:: __add__(expr) + + Return the sum of two linear expressions. + + .. method:: __sub__(expr) + + Return the difference between two linear expressions. + + .. method:: __mul__(value) + + Return the product of the linear expression by a rational. + + .. method:: __truediv__(value) + + Return the quotient of the linear expression by a rational. + + .. method:: __eq__(expr) + + Test whether two linear expressions are equal. + + As explained below, it is possible to create polyhedra from linear expressions using comparison methods. + + .. method:: __lt__(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. + + >>> x, y = symbols('x y') + >>> x < y + Le(x - y + 1, 0) + + + .. method:: scaleint() + + Return the expression multiplied by its lowest common denominator to make all values integer. + + .. method:: subs(symbol, expression) + subs(pairs) + + Substitute the given symbol by an expression and return the resulting expression. + Raise :exc:`TypeError` is 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 + + .. classmethod:: fromstring(string) + + Create an expression from a string. + Raise :exc:`SyntaxError` if the string is not properly formatted. + + There are also methods to convert linear expressions to and from `SymPy `_ expressions: + + .. classmethod:: fromsympy(expr) + + Create a linear expression from a :mod:`sympy` expression. + Raise :exc:`ValueError` is the :mod:`sympy` expression is not linear. + + .. method:: tosympy() + + Convert the linear expression to a sympy expression. + + +Apart from :mod:`Symbol`, 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 :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes. + +.. class:: Rational(numerator, denominator=1) + Rational(string) + + The first version requires that *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with value ``numerator/denominator``. + If denominator is ``0``, it raises a :exc:`ZeroDivisionError`. + The other version of the constructor expects a string. + The usual form for this instance is:: + + [sign] numerator ['/' denominator] + + where the optional ``sign`` may be either '+' or '-' and ``numerator`` and ``denominator`` (if present) are strings of decimal digits. + + See the documentation of :class:`fractions.Fraction` for more information and examples. + +Polyhedra +--------- + +A *convex polyhedron* (or simply polyhedron) is the space defined by a system of linear equalities and inequalities. +This space can be unbounded. + +.. class:: Polyhedron(equalities, inequalities) + Polyhedron(string) + Polyhedron(geometric object) + + 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 :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, or functions :func:`Lt`, :func:`Le`, :func:`Eq`, :func:`Ge` and :func:`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 :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method. + This way, it is possible to compute the polyhedral hull of a :class:`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) + + A polyhedron is a :class:`Domain` instance, and, as such, inherits the functionalities of this class. + It is also a :class:`GeometricObject` instance. + + .. attribute:: equalities + + The tuple of equalities. + This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron. + + .. attribute:: inequalities + + The tuple of inequalities. + This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron. + + .. attribute:: constraints + + The tuple of constraints, i.e., equalities and inequalities. + This is semantically equivalent to: ``equalities + inequalities``. + + .. method:: widen(polyhedron) + + Compute the standard widening of two polyhedra, à la Halbwachs. + + +.. data:: Empty + + The empty polyhedron, whose set of constraints is not satisfiable. + +.. data:: Universe + + The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty. + +Domains +------- + +A *domain* is a union of polyhedra. +Unlike polyhedra, domains allow exact computation of union and complementary operations. + +.. class:: Domain(*polyhedra) + Domain(string) + Domain(geometric object) + + 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 :meth:`Domain.__and__`, :meth:`Domain.__or__` or functions :func:`And` and :func:`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 :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method. + + A domain is also a :class:`GeometricObject` instance. + A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance. + + .. attribute:: polyhedra + + The tuple of polyhedra present in the domain. + + .. attribute:: symbols + + The tuple of symbols present in the domain expression, sorted according to :meth:`Symbol.sortkey`. + + .. attribute:: dimension + + The dimension of the domain, i.e. the number of symbols present in it. + + .. method:: isempty() + + Return ``True`` if the domain is empty, that is, equal to :data:`Empty`. + + .. method:: __bool__() + + Return ``True`` if the domain is non-empty. + + .. method:: isuniverse() + + Return ``True`` if the domain is universal, that is, equal to :data:`Universe`. + + .. method:: isbounded() + + Return ``True`` is the domain is bounded. + + .. method:: __eq__(domain) + + Return ``True`` if two domains are equal. + + .. method:: isdisjoint(domain) + + Return ``True`` if two domains have a null intersection. + + .. method:: issubset(domain) + __le__(domain) + + Report whether another domain contains the domain. + + .. method:: __lt__(domain) + + Report whether another domain is contained within the domain. + + .. method:: complement() + __invert__() + + Return the complementary domain of the domain. + + .. method:: make_disjoint() + + Return an equivalent domain, whose polyhedra are disjoint. + + .. method:: coalesce() + + Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain. + + .. method:: detect_equalities() + + Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain. + + .. method:: remove_redundancies() + + Remove redundant constraints in the domain, and return the resulting domain. + + .. method:: project(symbols) + + Project out the sequence of symbols given in arguments, and return the resulting domain. + + .. method:: sample() + + Return a sample of the domain, as an integer instance of :class:`Point`. + If the domain is empty, a :exc:`ValueError` exception is raised. + + .. method:: intersection(domain[, ...]) + __and__(domain) + + Return the intersection of two or more domains as a new domain. + As an alternative, function :func:`And` can be used. + + .. method:: union(domain[, ...]) + __or__(domain) + __add__(domain) + + Return the union of two or more domains as a new domain. + As an alternative, function :func:`Or` can be used. + + .. method:: difference(domain) + __sub__(domain) + + Return the difference between two domains as a new domain. + + .. method:: lexmin() + + Return the lexicographic minimum of the elements in the domain. + + .. method:: lexmax() + + Return the lexicographic maximum of the elements in the domain. + + .. method:: vertices() + + Return the vertices of the domain, as a list of rational instances of :class:`Point`. + + .. method:: points() + + Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`. + If the domain is not bounded, a :exc:`ValueError` exception is raised. + + .. method:: __contains__(point) + + Return ``True`` if the :class:`Point` is contained within the domain. + + .. method:: faces() + + 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 :class:`Point`. + If the domain is not bounded, a :exc:`ValueError` exception is raised. + + .. method:: plot(plot=None, **options) + + 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 :exc:`ValueError` is the domain is not 2D or 3D. + + .. method:: subs(symbol, expression) + subs(pairs) + + 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 :func:`LinExpr.subs`. + + .. classmethod:: fromstring(string) + + Create a domain from a string. + Raise :exc:`SyntaxError` if the string is not properly formatted. + + There are also methods to convert a domain to and from `SymPy `_ expressions: + + .. classmethod:: fromsympy(expr) + + Create a domain from a sympy expression. + + .. method:: tosympy() + + Convert the domain to a sympy expression. + + +Comparison and Logic Operators +------------------------------ + +The following functions allow to create :class:`Polyhedron` or :class:`Domain` instances by comparison of :class:`LinExpr` instances: + +.. function:: Lt(expr1, expr2[, expr3, ...]) + + Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``. + +.. function:: Le(expr1, expr2[, expr3, ...]) + + Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``. + +.. function:: Eq(expr1, expr2[, expr3, ...]) + + Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``. + +.. function:: Ne(expr1, expr2[, expr3, ...]) + + Create the domain such that ``expr1 != expr2 != expr3 ...``. + The result is a :class:`Domain`, not a :class:`Polyhedron`. + +.. function:: Ge(expr1, expr2[, expr3, ...]) + + Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``. + +.. function:: Gt(expr1, expr2[, expr3, ...]) + + Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``. + +The following functions allow to combine :class:`Polyhedron` or :class:`Domain` instances using logic operators: + +.. function:: Or(domain1, domain2[, ...]) + + Create the union domain of domains given in arguments. + +.. function:: And(domain1, domain2[, ...]) + + Create the intersection domain of domains given in arguments. + +.. function:: Not(domain) + + Create the complementary domain of the domain given in argument. + + +Geometric Objects +----------------- + +.. class:: GeometricObject + + :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space. + Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`. + The following elements must be provided: + + .. attribute:: symbols + + The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`. + + .. attribute:: dimension + + The dimension of the object, i.e. the number of symbols present in it. + + .. method:: aspolyedron() + + Return a :class:`Polyhedron` object that approximates the geometric object. + + .. method:: asdomain() + + Return a :class:`Domain` object that approximates the geometric object. + +.. class:: Point(coordinates) + + Create a point from a dictionnary or a sequence that maps symbols to their coordinates. + Coordinates must be rational numbers. + + For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions: + + >>> x, y = symbols('x y') + >>> p = Point({x: 1, y: 2}) + >>> p = Point([(x, 1), (y, 2)]) + + :class:`Point` instances are hashable, and should be treated as immutable. + + A point is a :class:`GeometricObject` instance. + + .. attribute:: symbols + + The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`. + + .. attribute:: dimension + + The dimension of the point, i.e. the number of symbols present in it. + + .. method:: coordinate(symbol) + __getitem__(symbol) + + Return the coordinate value of the given symbol. + Raise :exc:`KeyError` if the symbol is not involved in the point. + + .. method:: coordinates() + + Iterate over the pairs ``(symbol, value)`` of coordinates in the point. + + .. method:: values() + + Iterate over the coordinate values in the point. + + .. method:: isorigin() + + Return ``True`` if all coordinates are ``0``. + + .. method:: __bool__() + + Return ``True`` if not all coordinates are ``0``. + + .. method:: __add__(vector) + + Translate the point by a :class:`Vector` instance and return the resulting point. + + .. method:: __sub__(point) + __sub__(vector) + + The first version substract a point from another and return the resulting vector. + The second version translates the point by the opposite vector of *vector* and returns the resulting point. + + .. method:: __eq__(point) + + Test whether two points are equal. + + +.. class:: Vector(coordinates) + + Create a point from a dictionnary or a sequence that maps symbols to their coordinates, similarly to :meth:`Point`. + Coordinates must be rational numbers. + + :class:`Vector` instances are hashable, and should be treated as immutable. + + .. attribute:: symbols + + The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`. + + .. attribute:: dimension + + The dimension of the point, i.e. the number of symbols present in it. + + .. method:: coordinate(symbol) + __getitem__(symbol) + + Return the coordinate value of the given symbol. + Raise :exc:`KeyError` if the symbol is not involved in the point. + + .. method:: coordinates() + + Iterate over the pairs ``(symbol, value)`` of coordinates in the point. + + .. method:: values() + + Iterate over the coordinate values in the point. + + .. method:: isnull() + + Return ``True`` if all coordinates are ``0``. + + .. method:: __bool__() + + Return ``True`` if not all coordinates are ``0``. + + .. method:: __add__(point) + __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) + + The first version substracts a point from a vector and returns the resulting point. + The second version returns the difference vector between two vectors. + + .. method:: __neg__() + + Return the opposite vector. + + .. method:: angle(vector) + + Retrieve the angle required to rotate the vector into the vector passed in argument. + The result is an angle in radians, ranging between ``-pi`` and ``pi``. + + .. method:: cross(vector) + + Compute the cross product of two 3D vectors. + If either one of the vectors is not tridimensional, a :exc:`ValueError` exception is raised. + + .. method:: dot(vector) + + 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. + + .. method:: asunit() + + Return the normalized vector, i.e. the vector of same direction but with norm 1. -- 2.20.1