From 25ce908cffca380f930182a77c1e5a4491042a1c Mon Sep 17 00:00:00 2001 From: Danielle Bolan Date: Fri, 18 Jul 2014 17:27:24 +0200 Subject: [PATCH] Added some docs --- doc/domain.rst | 167 +++++++++++ doc/domain.rst~ | 167 +++++++++++ doc/examples.rst | 0 doc/geometry.rst | 38 +++ doc/geometry.rst~ | 39 +++ doc/index.rst | 15 +- doc/index.rst~ | 25 ++ doc/install.rst | 19 ++ doc/install.rst~ | 14 + doc/linexpr.rst | 45 +++ doc/linexpr.rst~ | 54 ++++ doc/modules.rst | 15 + doc/modules.rst~ | 15 + doc/polyhedra.rst | 61 ++++ doc/polyhedra.rst~ | 61 ++++ pypol/domains.py | 11 +- pypol/domains.py~ | 695 ++++++++++++++++++++++++++++++++++++++++++++ pypol/polyhedra.py | 43 ++- pypol/polyhedra.py~ | 358 +++++++++++++++++++++++ 19 files changed, 1820 insertions(+), 22 deletions(-) create mode 100644 doc/domain.rst create mode 100644 doc/domain.rst~ create mode 100644 doc/examples.rst create mode 100644 doc/geometry.rst create mode 100644 doc/geometry.rst~ create mode 100644 doc/index.rst~ create mode 100644 doc/install.rst create mode 100644 doc/install.rst~ create mode 100644 doc/linexpr.rst create mode 100644 doc/linexpr.rst~ create mode 100644 doc/modules.rst create mode 100644 doc/modules.rst~ create mode 100644 doc/polyhedra.rst create mode 100644 doc/polyhedra.rst~ create mode 100644 pypol/domains.py~ create mode 100644 pypol/polyhedra.py~ diff --git a/doc/domain.rst b/doc/domain.rst new file mode 100644 index 0000000..217acba --- /dev/null +++ b/doc/domain.rst @@ -0,0 +1,167 @@ +Domains Module +============== + +.. py:class :: Domain + + .. py:method:: polyhedra(self) + + Return . + +Domain Properties +----------------- + .. py:method:: symbols(self) + + Returns a list of the symbols used in a set. + + .. py:method:: dimension(self) + + Returns the number of variables in a set. + + .. py:method:: disjoint(self) + + Returns a set as disjoint. + + .. py:method:: num_parameters(self) + + Returns the total number of parameters, input, output or set dimensions. + + .. py:method:: involves_dims(self, dims) + + Returns true if set depends on given dimensions. + +Unary Properties +---------------- + .. py:method:: isempty(self) + + Return true is set is an Empty set. + + .. py:method:: isuniverse(self) + + Return true if set is the Universe set. + + .. py:method:: isbounded(self) + + Return true if set is bounded + + .. py:method:: disjoint(self) + + Returns this set as a disjoint set. + +Binary Properties +----------------- + + .. py:method:: isdisjoint(self, other) + + Return true if the intersection of two sets results in an Empty set. + + .. py:method:: issubset(self, other) + + Returns true if one set contains the other set. + + .. py:method:: __eq__(self, other) + + Return true if self == other. + + .. py:method:: __lt__(self, other) + + Return true if self < other. + + .. py:method:: __le__(self, other) + + Return true if self <= other. + + .. py:method:: __gt__(self, other) + + Return true if self > other. + + .. py:method:: __ge__(self, other) + + Return true if self >= other. + + +Unary Operations +---------------- + + .. py:method:: complement(self) + + Return the complement of a set. + + .. py:method:: simplify(self) + + Removes redundant constraints from a set. + + .. py:method:: project(self, dims) + + Return a new set with the given dimensions removed. + + .. py:method:: aspolyhedron(self) + + Return polyhedral hull of a set. + + .. py:method:: asdomain(self) + + Return + + .. py:method:: sample(self) + + Return a single sample subset of a set. + +Binary Operations +----------------- + + .. py:method:: intersection(self) + + Return the intersection of two sets as a new set. + + .. py:method:: union(self) + + Return the union of two sets as a new set. + + .. py:method:: __and__(self, other) + + Return the union of two sets as a new set. + + .. py:method:: __or__(self, other) + + Return the intersection of two sets as a new set. + + .. py:method:: __add__(self, other) + + Return the sum of two sets. + + .. py:method:: difference(self, other) + + Return the difference of two sets. + +Lexiographic Operations +----------------------- + + .. py:method:: lexmin(self) + + Return a new set containing the lexicographic minimum of the elements in the set. + + .. py:method:: lexmax(self) + + Return a new set containing the lexicographic maximum of the elements in the set. + +Plot Properties +--------------- + + .. py:method:: points(self) + + Return a list of the points contained in a set. + + .. py:method:: vertices(self) + + Return a list of the verticies of this set. + + .. py:method:: faces(self) + + Return a list of the vertices for each face of a set. + + .. py:method:: plot(self, plot=None, **kwargs) + + Return a plot of the given set. + + + diff --git a/doc/domain.rst~ b/doc/domain.rst~ new file mode 100644 index 0000000..217acba --- /dev/null +++ b/doc/domain.rst~ @@ -0,0 +1,167 @@ +Domains Module +============== + +.. py:class :: Domain + + .. py:method:: polyhedra(self) + + Return . + +Domain Properties +----------------- + .. py:method:: symbols(self) + + Returns a list of the symbols used in a set. + + .. py:method:: dimension(self) + + Returns the number of variables in a set. + + .. py:method:: disjoint(self) + + Returns a set as disjoint. + + .. py:method:: num_parameters(self) + + Returns the total number of parameters, input, output or set dimensions. + + .. py:method:: involves_dims(self, dims) + + Returns true if set depends on given dimensions. + +Unary Properties +---------------- + .. py:method:: isempty(self) + + Return true is set is an Empty set. + + .. py:method:: isuniverse(self) + + Return true if set is the Universe set. + + .. py:method:: isbounded(self) + + Return true if set is bounded + + .. py:method:: disjoint(self) + + Returns this set as a disjoint set. + +Binary Properties +----------------- + + .. py:method:: isdisjoint(self, other) + + Return true if the intersection of two sets results in an Empty set. + + .. py:method:: issubset(self, other) + + Returns true if one set contains the other set. + + .. py:method:: __eq__(self, other) + + Return true if self == other. + + .. py:method:: __lt__(self, other) + + Return true if self < other. + + .. py:method:: __le__(self, other) + + Return true if self <= other. + + .. py:method:: __gt__(self, other) + + Return true if self > other. + + .. py:method:: __ge__(self, other) + + Return true if self >= other. + + +Unary Operations +---------------- + + .. py:method:: complement(self) + + Return the complement of a set. + + .. py:method:: simplify(self) + + Removes redundant constraints from a set. + + .. py:method:: project(self, dims) + + Return a new set with the given dimensions removed. + + .. py:method:: aspolyhedron(self) + + Return polyhedral hull of a set. + + .. py:method:: asdomain(self) + + Return + + .. py:method:: sample(self) + + Return a single sample subset of a set. + +Binary Operations +----------------- + + .. py:method:: intersection(self) + + Return the intersection of two sets as a new set. + + .. py:method:: union(self) + + Return the union of two sets as a new set. + + .. py:method:: __and__(self, other) + + Return the union of two sets as a new set. + + .. py:method:: __or__(self, other) + + Return the intersection of two sets as a new set. + + .. py:method:: __add__(self, other) + + Return the sum of two sets. + + .. py:method:: difference(self, other) + + Return the difference of two sets. + +Lexiographic Operations +----------------------- + + .. py:method:: lexmin(self) + + Return a new set containing the lexicographic minimum of the elements in the set. + + .. py:method:: lexmax(self) + + Return a new set containing the lexicographic maximum of the elements in the set. + +Plot Properties +--------------- + + .. py:method:: points(self) + + Return a list of the points contained in a set. + + .. py:method:: vertices(self) + + Return a list of the verticies of this set. + + .. py:method:: faces(self) + + Return a list of the vertices for each face of a set. + + .. py:method:: plot(self, plot=None, **kwargs) + + Return a plot of the given set. + + + diff --git a/doc/examples.rst b/doc/examples.rst new file mode 100644 index 0000000..e69de29 diff --git a/doc/geometry.rst b/doc/geometry.rst new file mode 100644 index 0000000..224fb3a --- /dev/null +++ b/doc/geometry.rst @@ -0,0 +1,38 @@ +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 is given point is the origin. + + .. py:method:: + +.. py:class:: Vector + +This class represents displacements in space. + + .. 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. + + .. 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/geometry.rst~ b/doc/geometry.rst~ new file mode 100644 index 0000000..d96cd6f --- /dev/null +++ b/doc/geometry.rst~ @@ -0,0 +1,39 @@ + +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 is given point is the origin. + + .. py:method:: + +.. py:class:: Vector + +This class represents displacements in space. + + .. 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. + + .. 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 0c5738e..12f6f4e 100644 --- a/doc/index.rst +++ b/doc/index.rst @@ -6,19 +6,20 @@ Welcome to pypol's documentation! ================================= -Since Pythagoras, we know that :math:`c = \sqrt{a^2 + b^2}`. +Pypol is a Python library for symbolic mathematics. +If you are new to Pypol, start with the Tutorial. + +This is the central page for all of SymPy's documentation. + Contents: .. toctree:: :maxdepth: 2 + install.rst + examples.rst + modules.rst -Indices and tables -================== - -* :ref:`genindex` -* :ref:`modindex` -* :ref:`search` diff --git a/doc/index.rst~ b/doc/index.rst~ new file mode 100644 index 0000000..cbe9460 --- /dev/null +++ b/doc/index.rst~ @@ -0,0 +1,25 @@ +.. pypol 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 pypol's documentation! +================================= + +Pypol is a Python library for symbolic mathematics. +If you are new to Pypol, start with the Tutorial. + +This is the central page for all of SymPy's documentation. + + +Contents: + +.. toctree:: + :maxdepth: 2 + + install.rst + example.rst + modules.rst + + + diff --git a/doc/install.rst b/doc/install.rst new file mode 100644 index 0000000..35cd056 --- /dev/null +++ b/doc/install.rst @@ -0,0 +1,19 @@ +.. _installation: + +Installation +------------ + +Dependencies +============ + +Users will first need to install Integer Set Library (isl). The source files of isl are available as a tarball or a git repository. Both +are available `here`_ . + +Source +====== + +Git +=== + + +.. _here: http://freshmeat.net/projects/isl/ diff --git a/doc/install.rst~ b/doc/install.rst~ new file mode 100644 index 0000000..8e0224a --- /dev/null +++ b/doc/install.rst~ @@ -0,0 +1,14 @@ +.. _installation: + +Installation +------------ + +Dependencies +============ + +Users will first need to install Integer Set Library (isl). The source files of isl are available as a tarball or a git repository. Both +are available `here`_ . + + + +.. _here: http://freshmeat.net/projects/isl/ diff --git a/doc/linexpr.rst b/doc/linexpr.rst new file mode 100644 index 0000000..3771d5f --- /dev/null +++ b/doc/linexpr.rst @@ -0,0 +1,45 @@ +Linear Expression Module +======================== + + +This class implements linear expressions. + + .. 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 + + .. py:method:: constant(self) + + Return the constant value of an expression. + + .. py:method:: symbols(self) + + Return a list of symbols in an expression. + + .. py:method:: dimension(self) + + Return the number of vriables in an expression. + + .. py:method:: __sub__(self, other) + + Return the difference between two expressions. + + .. py:method:: subs(self, symbol, expression=None) + + Subsitute the given value into an expression and return the resulting expression. + + .. py:method:: fromsympy(self) + + Convert sympy object to an expression. + + .. py:method:: tosympy(self) + + Return an expression as a sympy object. + +.. py:class:: Dummy(Symbol) + +This class returns a dummy symbol to ensure that each no variables are repeated in an expression diff --git a/doc/linexpr.rst~ b/doc/linexpr.rst~ new file mode 100644 index 0000000..6a017bf --- /dev/null +++ b/doc/linexpr.rst~ @@ -0,0 +1,54 @@ +Linear Expression Module +======================== + + +This class implements linear expressions. + + .. 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 + + .. py:method:: constant(self) + + Return the constant value of an expression. + + .. py:method:: symbols(self) + + Return a list of symbols in an expression. + + .. py:method:: dimension(self) + + Return the number of vriables in an expression. + + .. py:method:: __sub__(self, other) + + Return the difference between two expressions. + + .. py:method:: subs(self, symbol, expression=None) + + Subsitute the given value into an expression and return the resulting expression. + + .. py:method:: fromsympy(self) + + Convert sympy object to an expression. + + .. py:method:: tosympy(self) + + Return an expression as a sympy object. + +.. py:class:: Dummy(Symbol) + +This class returns a dummy symbol to ensure that each no variables are repeated in an expression + + + + + + + + + diff --git a/doc/modules.rst b/doc/modules.rst new file mode 100644 index 0000000..2ecf371 --- /dev/null +++ b/doc/modules.rst @@ -0,0 +1,15 @@ +.. module-docs: + +Pypol Module Reference +====================== + +There are four main Pypol modules: + +.. toctree:: + :maxdepth: 2 + + polyhedra.rst + domain.rst + linexpr.rst + geometry.rst + diff --git a/doc/modules.rst~ b/doc/modules.rst~ new file mode 100644 index 0000000..2ecf371 --- /dev/null +++ b/doc/modules.rst~ @@ -0,0 +1,15 @@ +.. module-docs: + +Pypol Module Reference +====================== + +There are four main Pypol modules: + +.. toctree:: + :maxdepth: 2 + + polyhedra.rst + domain.rst + linexpr.rst + geometry.rst + diff --git a/doc/polyhedra.rst b/doc/polyhedra.rst new file mode 100644 index 0000000..fd09b90 --- /dev/null +++ b/doc/polyhedra.rst @@ -0,0 +1,61 @@ +Polyhedra Module +================ + +.. py:class:: Polyhedron + +Polyhedra Properties +-------------------- + + .. py:method:: equalities(self) + + Return a list of the equalities in a set. + + .. py:method:: inequalities(self) + + Return a list of the inequalities in a set. + + .. py:method:: constraints(self) + + Return ta list of the constraints of a set. + +Unary Operations +---------------- + .. py:method:: disjoint(self) + + Returns this set as a disjoint set. + + .. py:method:: isuniverse(self) + + Return true if this set is the Universe set. + + .. py:method:: aspolyhedron(self) + + Return polyhedral hull of this set. + + .. py:method:: subs(self, symbol, expression=None) + + Subsitute expression into given set and returns the result. + + .. py:method:: Lt(left, right) + + Assert first set is less than the second set. + + .. py:method:: Le(left, right) + + Assert first set is less than or equal to the second set. + + .. py:method:: Eq(left, right) + + Assert first set is equal to the second set. + + .. py:method:: Ne(left, right) + + Assert first set is not equal to the second set. + + .. py:method:: Gt(left, right) + + Assert first set is greater than the second set. + + .. py:method:: Ge(left, right) + + Assert first set is greater than or equal to the second set. diff --git a/doc/polyhedra.rst~ b/doc/polyhedra.rst~ new file mode 100644 index 0000000..fd09b90 --- /dev/null +++ b/doc/polyhedra.rst~ @@ -0,0 +1,61 @@ +Polyhedra Module +================ + +.. py:class:: Polyhedron + +Polyhedra Properties +-------------------- + + .. py:method:: equalities(self) + + Return a list of the equalities in a set. + + .. py:method:: inequalities(self) + + Return a list of the inequalities in a set. + + .. py:method:: constraints(self) + + Return ta list of the constraints of a set. + +Unary Operations +---------------- + .. py:method:: disjoint(self) + + Returns this set as a disjoint set. + + .. py:method:: isuniverse(self) + + Return true if this set is the Universe set. + + .. py:method:: aspolyhedron(self) + + Return polyhedral hull of this set. + + .. py:method:: subs(self, symbol, expression=None) + + Subsitute expression into given set and returns the result. + + .. py:method:: Lt(left, right) + + Assert first set is less than the second set. + + .. py:method:: Le(left, right) + + Assert first set is less than or equal to the second set. + + .. py:method:: Eq(left, right) + + Assert first set is equal to the second set. + + .. py:method:: Ne(left, right) + + Assert first set is not equal to the second set. + + .. py:method:: Gt(left, right) + + Assert first set is greater than the second set. + + .. py:method:: Ge(left, right) + + Assert first set is greater than or equal to the second set. diff --git a/pypol/domains.py b/pypol/domains.py index be9dd4b..1c400bd 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -340,6 +340,8 @@ class Domain(GeometricObject): Return a list of vertices for this Polygon. """ from .polyhedra import Polyhedron + if not self.isbounded(): + raise ValueError('domain must be bounded') islbset = self._toislbasicset(self.equalities, self.inequalities, self.symbols) vertices = libisl.isl_basic_set_compute_vertices(islbset); vertices = islhelper.isl_vertices_vertices(vertices) @@ -390,7 +392,7 @@ class Domain(GeometricObject): coordinates[symbol] = coordinate points.append(Point(coordinates)) return points - + @classmethod def _polygon_inner_point(cls, points): symbols = points[0].symbols @@ -443,6 +445,9 @@ class Domain(GeometricObject): return sorted(points, key=angles.get) def faces(self): + """ + Returns the vertices of the faces of a polyhedra. + """ faces = [] for polyhedron in self.polyhedra: vertices = polyhedron.vertices() @@ -503,6 +508,7 @@ class Domain(GeometricObject): axes.set_zlim(zmin, zmax) return axes + def plot(self, plot=None, **kwargs): """ Display plot of this set. @@ -523,6 +529,9 @@ class Domain(GeometricObject): return False def subs(self, symbol, expression=None): + """ + Subsitute the given value into an expression and return the resulting expression. + """ polyhedra = [polyhedron.subs(symbol, expression) for polyhedron in self.polyhedra] return Domain(*polyhedra) diff --git a/pypol/domains.py~ b/pypol/domains.py~ new file mode 100644 index 0000000..be9dd4b --- /dev/null +++ b/pypol/domains.py~ @@ -0,0 +1,695 @@ +import ast +import functools +import re +import math + +from fractions import Fraction + +from . import islhelper +from .islhelper import mainctx, libisl +from .linexprs import Expression, Symbol, Rational +from .geometry import GeometricObject, Point, Vector + + +__all__ = [ + 'Domain', + 'And', 'Or', 'Not', +] + + +@functools.total_ordering +class Domain(GeometricObject): + + __slots__ = ( + '_polyhedra', + '_symbols', + '_dimension', + ) + + def __new__(cls, *polyhedra): + from .polyhedra import Polyhedron + if len(polyhedra) == 1: + argument = polyhedra[0] + if isinstance(argument, str): + return cls.fromstring(argument) + elif isinstance(argument, GeometricObject): + return argument.aspolyhedron() + else: + raise TypeError('argument must be a string ' + 'or a GeometricObject instance') + else: + for polyhedron in polyhedra: + if not isinstance(polyhedron, Polyhedron): + raise TypeError('arguments must be Polyhedron instances') + symbols = cls._xsymbols(polyhedra) + islset = cls._toislset(polyhedra, symbols) + return cls._fromislset(islset, symbols) + + @classmethod + def _xsymbols(cls, iterator): + """ + Return the ordered tuple of symbols present in iterator. + """ + symbols = set() + for item in iterator: + symbols.update(item.symbols) + return tuple(sorted(symbols, key=Symbol.sortkey)) + + @property + def polyhedra(self): + return self._polyhedra + + @property + def symbols(self): + return self._symbols + + @property + def dimension(self): + return self._dimension + + def disjoint(self): + """ + Returns this set as 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): + """ + Returns true if this set is an Empty set. + """ + islset = self._toislset(self.polyhedra, self.symbols) + empty = bool(libisl.isl_set_is_empty(islset)) + libisl.isl_set_free(islset) + return empty + + def __bool__(self): + return not self.isempty() + + def isuniverse(self): + """ + Returns true if this set is the Universe set. + """ + islset = self._toislset(self.polyhedra, self.symbols) + universe = bool(libisl.isl_set_plain_is_universe(islset)) + libisl.isl_set_free(islset) + return universe + + def isbounded(self): + """ + Returns true if this set is bounded. + """ + islset = self._toislset(self.polyhedra, self.symbols) + bounded = bool(libisl.isl_set_is_bounded(islset)) + libisl.isl_set_free(islset) + return bounded + + def __eq__(self, other): + """ + Returns true if two sets are equal. + """ + symbols = self._xsymbols([self, other]) + islset1 = self._toislset(self.polyhedra, symbols) + islset2 = other._toislset(other.polyhedra, symbols) + equal = bool(libisl.isl_set_is_equal(islset1, islset2)) + libisl.isl_set_free(islset1) + libisl.isl_set_free(islset2) + return equal + + def isdisjoint(self, other): + """ + Return True if two sets have a null intersection. + """ + symbols = self._xsymbols([self, other]) + islset1 = self._toislset(self.polyhedra, symbols) + islset2 = self._toislset(other.polyhedra, symbols) + equal = bool(libisl.isl_set_is_disjoint(islset1, islset2)) + libisl.isl_set_free(islset1) + libisl.isl_set_free(islset2) + return equal + + def issubset(self, other): + """ + Report whether another set contains this set. + """ + symbols = self._xsymbols([self, other]) + islset1 = self._toislset(self.polyhedra, symbols) + islset2 = self._toislset(other.polyhedra, symbols) + equal = bool(libisl.isl_set_is_subset(islset1, islset2)) + libisl.isl_set_free(islset1) + libisl.isl_set_free(islset2) + return equal + + def __le__(self, other): + """ + Returns true if this set is less than or equal to another set. + """ + return self.issubset(other) + + def __lt__(self, other): + """ + Returns true if this set is less than another set. + """ + symbols = self._xsymbols([self, other]) + islset1 = self._toislset(self.polyhedra, symbols) + islset2 = self._toislset(other.polyhedra, symbols) + equal = bool(libisl.isl_set_is_strict_subset(islset1, islset2)) + libisl.isl_set_free(islset1) + libisl.isl_set_free(islset2) + return equal + + def complement(self): + """ + Returns the complement of this set. + """ + islset = self._toislset(self.polyhedra, self.symbols) + islset = libisl.isl_set_complement(islset) + return self._fromislset(islset, self.symbols) + + def __invert__(self): + """ + Returns the complement of this set. + """ + return self.complement() + + def simplify(self): + """ + Returns a set without redundant constraints. + """ + islset = self._toislset(self.polyhedra, self.symbols) + islset = libisl.isl_set_remove_redundancies(islset) + return self._fromislset(islset, self.symbols) + + def aspolyhedron(self): + """ + Returns polyhedral hull of set. + """ + from .polyhedra import Polyhedron + islset = self._toislset(self.polyhedra, self.symbols) + islbset = libisl.isl_set_polyhedral_hull(islset) + return Polyhedron._fromislbasicset(islbset, self.symbols) + + def asdomain(self): + return self + + def project(self, dims): + """ + Return new set with given dimensions removed. + """ + islset = self._toislset(self.polyhedra, self.symbols) + n = 0 + for index, symbol in reversed(list(enumerate(self.symbols))): + if symbol in dims: + n += 1 + elif n > 0: + islset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, index + 1, n) + n = 0 + if n > 0: + islset = libisl.isl_set_project_out(islset, libisl.isl_dim_set, 0, n) + dims = [symbol for symbol in self.symbols if symbol not in dims] + return Domain._fromislset(islset, dims) + + def sample(self): + """ + Returns a single subset of the input. + """ + islset = self._toislset(self.polyhedra, self.symbols) + islpoint = libisl.isl_set_sample_point(islset) + if bool(libisl.isl_point_is_void(islpoint)): + libisl.isl_point_free(islpoint) + raise ValueError('domain must be non-empty') + point = {} + for index, symbol in enumerate(self.symbols): + coordinate = libisl.isl_point_get_coordinate_val(islpoint, + libisl.isl_dim_set, index) + coordinate = islhelper.isl_val_to_int(coordinate) + point[symbol] = coordinate + libisl.isl_point_free(islpoint) + return point + + def intersection(self, *others): + """ + Return the intersection of two sets as a new set. + """ + if len(others) == 0: + return self + symbols = self._xsymbols((self,) + others) + islset1 = self._toislset(self.polyhedra, symbols) + for other in others: + islset2 = other._toislset(other.polyhedra, symbols) + islset1 = libisl.isl_set_intersect(islset1, islset2) + return self._fromislset(islset1, symbols) + + def __and__(self, other): + """ + Return the intersection of two sets as a new set. + """ + return self.intersection(other) + + def union(self, *others): + """ + Return the union of sets as a new set. + """ + if len(others) == 0: + return self + symbols = self._xsymbols((self,) + others) + islset1 = self._toislset(self.polyhedra, symbols) + for other in others: + islset2 = other._toislset(other.polyhedra, symbols) + islset1 = libisl.isl_set_union(islset1, islset2) + return self._fromislset(islset1, symbols) + + def __or__(self, other): + """ + Return a new set with elements from both sets. + """ + return self.union(other) + + def __add__(self, other): + """ + Return new set containing all elements in both sets. + """ + return self.union(other) + + def difference(self, other): + """ + Return the difference of two sets as a new set. + """ + symbols = self._xsymbols([self, other]) + islset1 = self._toislset(self.polyhedra, symbols) + islset2 = other._toislset(other.polyhedra, symbols) + islset = libisl.isl_set_subtract(islset1, islset2) + return self._fromislset(islset, symbols) + + def __sub__(self, other): + """ + Return the difference of two sets as a new set. + """ + return self.difference(other) + + def lexmin(self): + """ + Return a new set containing the lexicographic minimum of the elements in the set. + """ + islset = self._toislset(self.polyhedra, self.symbols) + islset = libisl.isl_set_lexmin(islset) + return self._fromislset(islset, self.symbols) + + def lexmax(self): + """ + Return a new set containing the lexicographic maximum of the elements in the set. + """ + islset = self._toislset(self.polyhedra, self.symbols) + islset = libisl.isl_set_lexmax(islset) + return self._fromislset(islset, self.symbols) + + def num_parameters(self): + """ + Return the total number of parameters, input, output or set dimensions. + """ + islbset = self._toislbasicset(self.equalities, self.inequalities, self.symbols) + num = libisl.isl_basic_set_dim(islbset, libisl.isl_dim_set) + return num + + def involves_dims(self, dims): + """ + Returns true if set depends on given dimensions. + """ + islset = self._toislset(self.polyhedra, self.symbols) + dims = sorted(dims) + symbols = sorted(list(self.symbols)) + n = 0 + if len(dims)>0: + for dim in dims: + if dim in symbols: + first = symbols.index(dims[0]) + n +=1 + else: + first = 0 + else: + return False + value = bool(libisl.isl_set_involves_dims(islset, libisl.isl_dim_set, first, n)) + libisl.isl_set_free(islset) + return value + + _RE_COORDINATE = re.compile(r'\((?P\-?\d+)\)(/(?P\d+))?') + + def vertices(self): + """ + Return a list of vertices for this Polygon. + """ + from .polyhedra import Polyhedron + islbset = self._toislbasicset(self.equalities, self.inequalities, self.symbols) + vertices = libisl.isl_basic_set_compute_vertices(islbset); + vertices = islhelper.isl_vertices_vertices(vertices) + points = [] + for vertex in vertices: + expr = libisl.isl_vertex_get_expr(vertex) + coordinates = [] + if islhelper.isl_version < '0.13': + constraints = islhelper.isl_basic_set_constraints(expr) + for constraint in constraints: + constant = libisl.isl_constraint_get_constant_val(constraint) + constant = islhelper.isl_val_to_int(constant) + for index, symbol in enumerate(self.symbols): + coefficient = libisl.isl_constraint_get_coefficient_val(constraint, + libisl.isl_dim_set, index) + coefficient = islhelper.isl_val_to_int(coefficient) + if coefficient != 0: + coordinate = -Fraction(constant, coefficient) + coordinates.append((symbol, coordinate)) + else: + string = islhelper.isl_multi_aff_to_str(expr) + matches = self._RE_COORDINATE.finditer(string) + for symbol, match in zip(self.symbols, matches): + numerator = int(match.group('num')) + denominator = match.group('den') + denominator = 1 if denominator is None else int(denominator) + coordinate = Fraction(numerator, denominator) + coordinates.append((symbol, coordinate)) + points.append(Point(coordinates)) + return points + + def points(self): + """ + Returns the points contained in the set. + """ + if not self.isbounded(): + raise ValueError('domain must be bounded') + from .polyhedra import Universe, Eq + islset = self._toislset(self.polyhedra, self.symbols) + islpoints = islhelper.isl_set_points(islset) + points = [] + for islpoint in islpoints: + coordinates = {} + for index, symbol in enumerate(self.symbols): + coordinate = libisl.isl_point_get_coordinate_val(islpoint, + libisl.isl_dim_set, index) + coordinate = islhelper.isl_val_to_int(coordinate) + coordinates[symbol] = coordinate + points.append(Point(coordinates)) + return points + + @classmethod + def _polygon_inner_point(cls, points): + symbols = points[0].symbols + coordinates = {symbol: 0 for symbol in symbols} + for point in points: + for symbol, coordinate in point.coordinates(): + coordinates[symbol] += coordinate + for symbol in symbols: + coordinates[symbol] /= len(points) + return Point(coordinates) + + @classmethod + def _sort_polygon_2d(cls, points): + if len(points) <= 3: + return points + o = cls._polygon_inner_point(points) + angles = {} + for m in points: + om = Vector(o, m) + dx, dy = (coordinate for symbol, coordinate in om.coordinates()) + angle = math.atan2(dy, dx) + angles[m] = angle + return sorted(points, key=angles.get) + + @classmethod + def _sort_polygon_3d(cls, points): + if len(points) <= 3: + return points + o = cls._polygon_inner_point(points) + a = points[0] + oa = Vector(o, a) + norm_oa = oa.norm() + for b in points[1:]: + ob = Vector(o, b) + u = oa.cross(ob) + if not u.isnull(): + u = u.asunit() + break + else: + raise ValueError('degenerate polygon') + angles = {a: 0.} + for m in points[1:]: + om = Vector(o, m) + normprod = norm_oa * om.norm() + cosinus = max(oa.dot(om) / normprod, -1.) + sinus = u.dot(oa.cross(om)) / normprod + angle = math.acos(cosinus) + angle = math.copysign(angle, sinus) + angles[m] = angle + return sorted(points, key=angles.get) + + def faces(self): + faces = [] + for polyhedron in self.polyhedra: + vertices = polyhedron.vertices() + for constraint in polyhedron.constraints: + face = [] + for vertex in vertices: + if constraint.subs(vertex.coordinates()) == 0: + face.append(vertex) + if len(face) >= 3: + faces.append(face) + return faces + + def _plot_2d(self, plot=None, **kwargs): + import matplotlib.pyplot as plt + from matplotlib.patches import Polygon + if plot is None: + fig = plt.figure() + plot = fig.add_subplot(1, 1, 1) + xmin, xmax = plot.get_xlim() + ymin, ymax = plot.get_ylim() + for polyhedron in self.polyhedra: + vertices = polyhedron._sort_polygon_2d(polyhedron.vertices()) + xys = [tuple(vertex.values()) for vertex in vertices] + xs, ys = zip(*xys) + xmin, xmax = min(xmin, float(min(xs))), max(xmax, float(max(xs))) + ymin, ymax = min(ymin, float(min(ys))), max(ymax, float(max(ys))) + plot.add_patch(Polygon(xys, closed=True, **kwargs)) + plot.set_xlim(xmin, xmax) + plot.set_ylim(ymin, ymax) + return plot + + def _plot_3d(self, plot=None, **kwargs): + import matplotlib.pyplot as plt + from mpl_toolkits.mplot3d import Axes3D + from mpl_toolkits.mplot3d.art3d import Poly3DCollection + if plot is None: + fig = plt.figure() + axes = Axes3D(fig) + else: + axes = plot + xmin, xmax = axes.get_xlim() + ymin, ymax = axes.get_ylim() + zmin, zmax = axes.get_zlim() + poly_xyzs = [] + for vertices in self.faces(): + vertices = self._sort_polygon_3d(vertices) + vertices.append(vertices[0]) + face_xyzs = [tuple(vertex.values()) for vertex in vertices] + xs, ys, zs = zip(*face_xyzs) + xmin, xmax = min(xmin, float(min(xs))), max(xmax, float(max(xs))) + ymin, ymax = min(ymin, float(min(ys))), max(ymax, float(max(ys))) + zmin, zmax = min(zmin, float(min(zs))), max(zmax, float(max(zs))) + poly_xyzs.append(face_xyzs) + collection = Poly3DCollection(poly_xyzs, **kwargs) + axes.add_collection3d(collection) + axes.set_xlim(xmin, xmax) + axes.set_ylim(ymin, ymax) + axes.set_zlim(zmin, zmax) + return axes + + def plot(self, plot=None, **kwargs): + """ + Display plot of this set. + """ + if not self.isbounded(): + raise ValueError('domain must be bounded') + elif self.dimension == 2: + return self._plot_2d(plot=plot, **kwargs) + elif self.dimension == 3: + return self._plot_3d(plot=plot, **kwargs) + else: + raise ValueError('polyhedron must be 2 or 3-dimensional') + + def __contains__(self, point): + for polyhedron in self.polyhedra: + if point in polyhedron: + return True + return False + + def subs(self, symbol, expression=None): + polyhedra = [polyhedron.subs(symbol, expression) + for polyhedron in self.polyhedra] + return Domain(*polyhedra) + + @classmethod + def _fromislset(cls, islset, symbols): + from .polyhedra import Polyhedron + islset = libisl.isl_set_remove_divs(islset) + islbsets = islhelper.isl_set_basic_sets(islset) + libisl.isl_set_free(islset) + polyhedra = [] + for islbset in islbsets: + polyhedron = Polyhedron._fromislbasicset(islbset, symbols) + polyhedra.append(polyhedron) + if len(polyhedra) == 0: + from .polyhedra import Empty + return Empty + elif len(polyhedra) == 1: + return polyhedra[0] + else: + self = object().__new__(Domain) + self._polyhedra = tuple(polyhedra) + self._symbols = cls._xsymbols(polyhedra) + self._dimension = len(self._symbols) + return self + + @classmethod + def _toislset(cls, polyhedra, symbols): + polyhedron = polyhedra[0] + islbset = polyhedron._toislbasicset(polyhedron.equalities, + polyhedron.inequalities, symbols) + islset1 = libisl.isl_set_from_basic_set(islbset) + for polyhedron in polyhedra[1:]: + islbset = polyhedron._toislbasicset(polyhedron.equalities, + polyhedron.inequalities, symbols) + islset2 = libisl.isl_set_from_basic_set(islbset) + islset1 = libisl.isl_set_union(islset1, islset2) + return islset1 + + @classmethod + def _fromast(cls, node): + from .polyhedra import Polyhedron + if isinstance(node, ast.Module) and len(node.body) == 1: + return cls._fromast(node.body[0]) + elif isinstance(node, ast.Expr): + return cls._fromast(node.value) + elif isinstance(node, ast.UnaryOp): + domain = cls._fromast(node.operand) + if isinstance(node.operand, ast.invert): + return Not(domain) + elif isinstance(node, ast.BinOp): + domain1 = cls._fromast(node.left) + domain2 = cls._fromast(node.right) + if isinstance(node.op, ast.BitAnd): + return And(domain1, domain2) + elif isinstance(node.op, ast.BitOr): + return Or(domain1, domain2) + elif isinstance(node, ast.Compare): + equalities = [] + inequalities = [] + left = Expression._fromast(node.left) + for i in range(len(node.ops)): + op = node.ops[i] + right = Expression._fromast(node.comparators[i]) + if isinstance(op, ast.Lt): + inequalities.append(right - left - 1) + elif isinstance(op, ast.LtE): + inequalities.append(right - left) + elif isinstance(op, ast.Eq): + equalities.append(left - right) + elif isinstance(op, ast.GtE): + inequalities.append(left - right) + elif isinstance(op, ast.Gt): + inequalities.append(left - right - 1) + else: + break + left = right + else: + return Polyhedron(equalities, inequalities) + raise SyntaxError('invalid syntax') + + _RE_BRACES = re.compile(r'^\{\s*|\s*\}$') + _RE_EQ = re.compile(r'([^<=>])=([^<=>])') + _RE_AND = re.compile(r'\band\b|,|&&|/\\|∧|∩') + _RE_OR = re.compile(r'\bor\b|;|\|\||\\/|∨|∪') + _RE_NOT = re.compile(r'\bnot\b|!|¬') + _RE_NUM_VAR = Expression._RE_NUM_VAR + _RE_OPERATORS = re.compile(r'(&|\||~)') + + @classmethod + def fromstring(cls, string): + # remove curly brackets + string = cls._RE_BRACES.sub(r'', string) + # replace '=' by '==' + string = cls._RE_EQ.sub(r'\1==\2', string) + # replace 'and', 'or', 'not' + string = cls._RE_AND.sub(r' & ', string) + string = cls._RE_OR.sub(r' | ', string) + string = cls._RE_NOT.sub(r' ~', string) + # add implicit multiplication operators, e.g. '5x' -> '5*x' + string = cls._RE_NUM_VAR.sub(r'\1*\2', string) + # add parentheses to force precedence + tokens = cls._RE_OPERATORS.split(string) + for i, token in enumerate(tokens): + if i % 2 == 0: + token = '({})'.format(token) + tokens[i] = token + string = ''.join(tokens) + tree = ast.parse(string, 'eval') + return cls._fromast(tree) + + def __repr__(self): + assert len(self.polyhedra) >= 2 + strings = [repr(polyhedron) for polyhedron in self.polyhedra] + return 'Or({})'.format(', '.join(strings)) + + def _repr_latex_(self): + strings = [] + for polyhedron in self.polyhedra: + strings.append('({})'.format(polyhedron._repr_latex_().strip('$'))) + return '${}$'.format(' \\vee '.join(strings)) + + @classmethod + def fromsympy(cls, expr): + import sympy + from .polyhedra import Lt, Le, Eq, Ne, Ge, Gt + funcmap = { + sympy.And: And, sympy.Or: Or, sympy.Not: Not, + sympy.Lt: Lt, sympy.Le: Le, + sympy.Eq: Eq, sympy.Ne: Ne, + sympy.Ge: Ge, sympy.Gt: Gt, + } + if expr.func in funcmap: + args = [Domain.fromsympy(arg) for arg in expr.args] + return funcmap[expr.func](*args) + elif isinstance(expr, sympy.Expr): + return Expression.fromsympy(expr) + raise ValueError('non-domain expression: {!r}'.format(expr)) + + def tosympy(self): + import sympy + polyhedra = [polyhedron.tosympy() for polyhedron in polyhedra] + return sympy.Or(*polyhedra) + + +def And(*domains): + """ + Return the intersection of two sets as a new set. + """ + if len(domains) == 0: + from .polyhedra import Universe + return Universe + else: + return domains[0].intersection(*domains[1:]) + +def Or(*domains): + """ + Return the union of sets as a new set. + """ + if len(domains) == 0: + from .polyhedra import Empty + return Empty + else: + return domains[0].union(*domains[1:]) + +def Not(domain): + """ + Returns the complement of this set. + """ + return ~domain diff --git a/pypol/polyhedra.py b/pypol/polyhedra.py index ccb1a8c..fe143d4 100644 --- a/pypol/polyhedra.py +++ b/pypol/polyhedra.py @@ -56,14 +56,23 @@ class Polyhedron(Domain): @property def equalities(self): + """ + Return a list of the equalities in a set. + """ return self._equalities @property def inequalities(self): + """ + Return a list of the inequalities in a set. + """ return self._inequalities @property def constraints(self): + """ + Return ta list of the constraints of a set. + """ return self._constraints @property @@ -72,13 +81,13 @@ class Polyhedron(Domain): def disjoint(self): """ - Return this set as disjoint. + Return a set as disjoint. """ return self def isuniverse(self): """ - Return true if this set is the Universe set. + Return true if a set is the Universe set. """ islbset = self._toislbasicset(self.equalities, self.inequalities, self.symbols) @@ -88,7 +97,7 @@ class Polyhedron(Domain): def aspolyhedron(self): """ - Return polyhedral hull of this set. + Return polyhedral hull of a set. """ return self @@ -106,6 +115,9 @@ class Polyhedron(Domain): return True def subs(self, symbol, expression=None): + """ + Subsitute the given value into an expression and return the resulting expression. + """ equalities = [equality.subs(symbol, expression) for equality in self.equalities] inequalities = [inequality.subs(symbol, expression) @@ -139,10 +151,6 @@ class Polyhedron(Domain): @classmethod def _fromislbasicset(cls, islbset, symbols): - if libisl.isl_basic_set_is_empty(islbset): - return Empty - if libisl.isl_basic_set_is_universe(islbset): - return Universe islconstraints = islhelper.isl_basic_set_constraints(islbset) equalities = [] inequalities = [] @@ -223,6 +231,7 @@ class Polyhedron(Domain): else: return 'And({})'.format(', '.join(strings)) + def _repr_latex_(self): strings = [] for equality in self.equalities: @@ -233,12 +242,18 @@ class Polyhedron(Domain): @classmethod def fromsympy(cls, expr): + """ + Convert a sympy object to an expression. + """ domain = Domain.fromsympy(expr) if not isinstance(domain, Polyhedron): raise ValueError('non-polyhedral expression: {!r}'.format(expr)) return domain def tosympy(self): + """ + Return an expression as a sympy object. + """ import sympy constraints = [] for equality in self.equalities: @@ -247,7 +262,6 @@ class Polyhedron(Domain): constraints.append(sympy.Ge(inequality.tosympy(), 0)) return sympy.And(*constraints) - class EmptyType(Polyhedron): __slots__ = Polyhedron.__slots__ @@ -318,41 +332,42 @@ def _polymorphic(func): @_polymorphic def Lt(left, right): """ - Return true if the first set is less than the second. + Assert first set is less than the second set. """ return Polyhedron([], [right - left - 1]) @_polymorphic def Le(left, right): """ - Return true the first set is less than or equal to the second. + Assert first set is less than or equal to the second set. """ return Polyhedron([], [right - left]) @_polymorphic def Eq(left, right): """ - Return true if the sets are equal. + Assert first set is equal to the second set. """ return Polyhedron([left - right], []) @_polymorphic def Ne(left, right): """ - Return true if the sets are NOT equal. + Assert first set is not equal to the second set. """ return ~Eq(left, right) @_polymorphic def Gt(left, right): """ - Return true if the first set is greater than the second set. + Assert first set is greater than the second set. """ return Polyhedron([], [left - right - 1]) @_polymorphic def Ge(left, right): """ - Return true if the first set is greater than or equal the second set. + Assert first set is greater than or equal to the second set. """ return Polyhedron([], [left - right]) + diff --git a/pypol/polyhedra.py~ b/pypol/polyhedra.py~ new file mode 100644 index 0000000..ccb1a8c --- /dev/null +++ b/pypol/polyhedra.py~ @@ -0,0 +1,358 @@ +import functools +import math +import numbers + +from . import islhelper + +from .islhelper import mainctx, libisl +from .geometry import GeometricObject, Point +from .linexprs import Expression, Rational +from .domains import Domain + + +__all__ = [ + 'Polyhedron', + 'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt', + 'Empty', 'Universe', +] + + +class Polyhedron(Domain): + + __slots__ = ( + '_equalities', + '_inequalities', + '_constraints', + '_symbols', + '_dimension', + ) + + def __new__(cls, equalities=None, inequalities=None): + if isinstance(equalities, str): + if inequalities is not None: + raise TypeError('too many arguments') + return cls.fromstring(equalities) + elif isinstance(equalities, GeometricObject): + if inequalities is not None: + raise TypeError('too many arguments') + return equalities.aspolyhedron() + if equalities is None: + equalities = [] + else: + for i, equality in enumerate(equalities): + if not isinstance(equality, Expression): + raise TypeError('equalities must be linear expressions') + equalities[i] = equality.scaleint() + if inequalities is None: + inequalities = [] + else: + for i, inequality in enumerate(inequalities): + if not isinstance(inequality, Expression): + raise TypeError('inequalities must be linear expressions') + inequalities[i] = inequality.scaleint() + symbols = cls._xsymbols(equalities + inequalities) + islbset = cls._toislbasicset(equalities, inequalities, symbols) + return cls._fromislbasicset(islbset, symbols) + + @property + def equalities(self): + return self._equalities + + @property + def inequalities(self): + return self._inequalities + + @property + def constraints(self): + return self._constraints + + @property + def polyhedra(self): + return self, + + def disjoint(self): + """ + Return this set as disjoint. + """ + return self + + def isuniverse(self): + """ + Return true if this set is the Universe set. + """ + islbset = self._toislbasicset(self.equalities, self.inequalities, + self.symbols) + universe = bool(libisl.isl_basic_set_is_universe(islbset)) + libisl.isl_basic_set_free(islbset) + return universe + + def aspolyhedron(self): + """ + Return polyhedral hull of this set. + """ + return self + + def __contains__(self, point): + if not isinstance(point, Point): + raise TypeError('point must be a Point instance') + if self.symbols != point.symbols: + raise ValueError('arguments must belong to the same space') + for equality in self.equalities: + if equality.subs(point.coordinates()) != 0: + return False + for inequality in self.inequalities: + if inequality.subs(point.coordinates()) < 0: + return False + return True + + def subs(self, symbol, expression=None): + equalities = [equality.subs(symbol, expression) + for equality in self.equalities] + inequalities = [inequality.subs(symbol, expression) + for inequality in self.inequalities] + return Polyhedron(equalities, inequalities) + + def _asinequalities(self): + inequalities = list(self.equalities) + inequalities.extend([-expression for expression in self.equalities]) + inequalities.extend(self.inequalities) + return inequalities + + def widen(self, other): + if not isinstance(other, Polyhedron): + raise ValueError('argument must be a Polyhedron instance') + inequalities1 = self._asinequalities() + inequalities2 = other._asinequalities() + inequalities = [] + for inequality1 in inequalities1: + if other <= Polyhedron(inequalities=[inequality1]): + inequalities.append(inequality1) + for inequality2 in inequalities2: + for i in range(len(inequalities1)): + inequalities3 = inequalities1[:i] + inequalities[i + 1:] + inequalities3.append(inequality2) + polyhedron3 = Polyhedron(inequalities=inequalities3) + if self == polyhedron3: + inequalities.append(inequality2) + break + return Polyhedron(inequalities=inequalities) + + @classmethod + def _fromislbasicset(cls, islbset, symbols): + if libisl.isl_basic_set_is_empty(islbset): + return Empty + if libisl.isl_basic_set_is_universe(islbset): + return Universe + islconstraints = islhelper.isl_basic_set_constraints(islbset) + equalities = [] + inequalities = [] + for islconstraint in islconstraints: + constant = libisl.isl_constraint_get_constant_val(islconstraint) + constant = islhelper.isl_val_to_int(constant) + coefficients = {} + for index, symbol in enumerate(symbols): + coefficient = libisl.isl_constraint_get_coefficient_val(islconstraint, + libisl.isl_dim_set, index) + coefficient = islhelper.isl_val_to_int(coefficient) + if coefficient != 0: + coefficients[symbol] = coefficient + expression = Expression(coefficients, constant) + if libisl.isl_constraint_is_equality(islconstraint): + equalities.append(expression) + else: + inequalities.append(expression) + libisl.isl_basic_set_free(islbset) + self = object().__new__(Polyhedron) + self._equalities = tuple(equalities) + self._inequalities = tuple(inequalities) + self._constraints = tuple(equalities + inequalities) + self._symbols = cls._xsymbols(self._constraints) + self._dimension = len(self._symbols) + return self + + @classmethod + def _toislbasicset(cls, equalities, inequalities, symbols): + dimension = len(symbols) + indices = {symbol: index for index, symbol in enumerate(symbols)} + islsp = libisl.isl_space_set_alloc(mainctx, 0, dimension) + islbset = libisl.isl_basic_set_universe(libisl.isl_space_copy(islsp)) + islls = libisl.isl_local_space_from_space(islsp) + for equality in equalities: + isleq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(islls)) + for symbol, coefficient in equality.coefficients(): + islval = str(coefficient).encode() + islval = libisl.isl_val_read_from_str(mainctx, islval) + index = indices[symbol] + isleq = libisl.isl_constraint_set_coefficient_val(isleq, + libisl.isl_dim_set, index, islval) + if equality.constant != 0: + islval = str(equality.constant).encode() + islval = libisl.isl_val_read_from_str(mainctx, islval) + isleq = libisl.isl_constraint_set_constant_val(isleq, islval) + islbset = libisl.isl_basic_set_add_constraint(islbset, isleq) + for inequality in inequalities: + islin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(islls)) + for symbol, coefficient in inequality.coefficients(): + islval = str(coefficient).encode() + islval = libisl.isl_val_read_from_str(mainctx, islval) + index = indices[symbol] + islin = libisl.isl_constraint_set_coefficient_val(islin, + libisl.isl_dim_set, index, islval) + if inequality.constant != 0: + islval = str(inequality.constant).encode() + islval = libisl.isl_val_read_from_str(mainctx, islval) + islin = libisl.isl_constraint_set_constant_val(islin, islval) + islbset = libisl.isl_basic_set_add_constraint(islbset, islin) + return islbset + + @classmethod + def fromstring(cls, string): + domain = Domain.fromstring(string) + if not isinstance(domain, Polyhedron): + raise ValueError('non-polyhedral expression: {!r}'.format(string)) + return domain + + def __repr__(self): + strings = [] + for equality in self.equalities: + strings.append('Eq({}, 0)'.format(equality)) + for inequality in self.inequalities: + strings.append('Ge({}, 0)'.format(inequality)) + if len(strings) == 1: + return strings[0] + else: + return 'And({})'.format(', '.join(strings)) + + def _repr_latex_(self): + strings = [] + for equality in self.equalities: + strings.append('{} = 0'.format(equality._repr_latex_().strip('$'))) + for inequality in self.inequalities: + strings.append('{} \\ge 0'.format(inequality._repr_latex_().strip('$'))) + return '$${}$$'.format(' \\wedge '.join(strings)) + + @classmethod + def fromsympy(cls, expr): + domain = Domain.fromsympy(expr) + if not isinstance(domain, Polyhedron): + raise ValueError('non-polyhedral expression: {!r}'.format(expr)) + return domain + + def tosympy(self): + import sympy + constraints = [] + for equality in self.equalities: + constraints.append(sympy.Eq(equality.tosympy(), 0)) + for inequality in self.inequalities: + constraints.append(sympy.Ge(inequality.tosympy(), 0)) + return sympy.And(*constraints) + + +class EmptyType(Polyhedron): + + __slots__ = Polyhedron.__slots__ + + def __new__(cls): + self = object().__new__(cls) + self._equalities = (Rational(1),) + self._inequalities = () + self._constraints = self._equalities + self._symbols = () + self._dimension = 0 + return self + + def widen(self, other): + if not isinstance(other, Polyhedron): + raise ValueError('argument must be a Polyhedron instance') + return other + + def __repr__(self): + return 'Empty' + + def _repr_latex_(self): + return '$$\\emptyset$$' + +Empty = EmptyType() + + +class UniverseType(Polyhedron): + + __slots__ = Polyhedron.__slots__ + + def __new__(cls): + self = object().__new__(cls) + self._equalities = () + self._inequalities = () + self._constraints = () + self._symbols = () + self._dimension = () + return self + + def __repr__(self): + return 'Universe' + + def _repr_latex_(self): + return '$$\\Omega$$' + +Universe = UniverseType() + + +def _polymorphic(func): + @functools.wraps(func) + def wrapper(left, right): + if not isinstance(left, Expression): + if isinstance(left, numbers.Rational): + left = Rational(left) + else: + raise TypeError('left must be a a rational number ' + 'or a linear expression') + if not isinstance(right, Expression): + if isinstance(right, numbers.Rational): + right = Rational(right) + else: + raise TypeError('right must be a a rational number ' + 'or a linear expression') + return func(left, right) + return wrapper + +@_polymorphic +def Lt(left, right): + """ + Return true if the first set is less than the second. + """ + return Polyhedron([], [right - left - 1]) + +@_polymorphic +def Le(left, right): + """ + Return true the first set is less than or equal to the second. + """ + return Polyhedron([], [right - left]) + +@_polymorphic +def Eq(left, right): + """ + Return true if the sets are equal. + """ + return Polyhedron([left - right], []) + +@_polymorphic +def Ne(left, right): + """ + Return true if the sets are NOT equal. + """ + return ~Eq(left, right) + +@_polymorphic +def Gt(left, right): + """ + Return true if the first set is greater than the second set. + """ + return Polyhedron([], [left - right - 1]) + +@_polymorphic +def Ge(left, right): + """ + Return true if the first set is greater than or equal the second set. + """ + return Polyhedron([], [left - right]) -- 2.20.1