#!/usr/bin/env python3
-# This example is inspired from a math question in the French baccalauréat 2014,
+# This example is inspired from a math question in the French baccalauréat 2014
# consisting in computing the intersection of a plane with a line.
-from linpy import *
+from linpy import Eq, symbols
x, y, z = symbols('x y z')
plane = Eq(x, y) & Eq(z, 6 - 2*x)
from math import ceil
from matplotlib import pylab
-from mpl_toolkits.mplot3d import Axes3D
-from linpy import *
+from linpy import Le, Polyhedron, symbols
x, y, z = symbols('x y z')
_x, _y, _z = x.asdummy(), y.asdummy(), z.asdummy()
+
def translate(domain, *, dx=0, dy=0, dz=0):
domain &= Polyhedron([x - _x + dx, y - _y + dy, z - _z + dz])
domain = domain.project([x, y, z])
domain = domain.subs({_x: x, _y: y, _z: z})
return domain
+
def _menger(domain, size):
result = domain
result |= translate(domain, dx=0, dy=size, dz=0)
result |= translate(domain, dx=2*size, dy=2*size, dz=2*size)
return result
+
def menger(domain, count=1, cut=False):
size = 1
for i in range(count):
if __name__ == '__main__':
parser = argparse.ArgumentParser(
description='Compute a Menger sponge.')
- parser.add_argument('-n', '--iterations', type=int, default=2,
+ parser.add_argument(
+ '-n', '--iterations', type=int, default=2,
help='number of iterations (default: 2)')
- parser.add_argument('-c', '--cut', action='store_true', default=False,
+ parser.add_argument(
+ '-c', '--cut', action='store_true', default=False,
help='cut the sponge')
args = parser.parse_args()
cube = Le(0, x) & Le(x, 1) & Le(0, y) & Le(y, 1) & Le(0, z) & Le(z, 1)
# to compute the transitive closure of an affine transformer. A refined version
# of this algorithm is implemented in PIPS.
-from linpy import *
+from linpy import Dummy, Eq, Ge, Polyhedron, symbols
class Transformer:
delta_symbols = [symbol.asdummy() for symbol in self.range_symbols]
k = Dummy('k')
polyhedron = self.polyhedron
- for x, xprime, dx in zip(self.range_symbols, self.domain_symbols, delta_symbols):
+ for x, xprime, dx in zip(
+ self.range_symbols, self.domain_symbols, delta_symbols):
polyhedron &= Eq(dx, xprime - x)
polyhedron = polyhedron.project(self.symbols)
equalities, inequalities = [], []
inequalities.append(inequality)
polyhedron = Polyhedron(equalities, inequalities) & Ge(k, 0)
polyhedron = polyhedron.project([k])
- for x, xprime, dx in zip(self.range_symbols, self.domain_symbols, delta_symbols):
+ for x, xprime, dx in zip(
+ self.range_symbols, self.domain_symbols, delta_symbols):
polyhedron &= Eq(dx, xprime - x)
polyhedron = polyhedron.project(delta_symbols)
return Transformer(polyhedron, self.range_symbols, self.domain_symbols)
if __name__ == '__main__':
i0, i, j0, j = symbols('i0 i j0 j')
transformer = Transformer(Eq(i, i0 + 2) & Eq(j, j0 + 1),
- [i0, j0], [i, j])
+ [i0, j0], [i, j])
print('T =', transformer.polyhedron)
print('T* =', transformer.star().polyhedron)
import matplotlib.pyplot as plt
from matplotlib import pylab
-from mpl_toolkits.mplot3d import Axes3D
-from linpy import *
+from linpy import Ge, Le, symbols
x, y, z = symbols('x y z')
diam = Ge(y, x - 1) & Le(y, x + 1) & Ge(y, -x - 1) & Le(y, -x + 1)
-cham = Le(0, x, 3) & Le(0, y, 3) & Le(0, z, 3) & \
- Le(z - 2, x, z + 2) & Le(1 - z, x, 5 - z) & \
- Le(z - 2, y, z + 2) & Le(1 - z, y, 5 - z) & \
- Le(y - 2, x, y + 2) & Le(1 - y, x, 5 - y)
-
-rhom = cham & \
- Le(x + y + z, 7) & Ge(-2, -x - y - z) & \
- Le(-1, x + y - z, 4) & Le(-1, x - y + z, 4) & Le(-1, -x + y + z, 4)
-
-cubo = Le(0, x, 5) & Le(0, y, 5) & Le(0, z, 5) & \
- Le(x -4, y, x + 4) & Le(-x + 1, y, -x + 9) & \
- Le(y -4, z, y + 4) & Le(-y + 1, z, -y + 9) & \
- Le(z -4, x, z + 4) & Le(-z + 1, x, -z + 9) & \
- Le(3, x + y + z, 12) & Le(-2, x - y + z, 7) & \
- Le(-2, -x + y + z, 7) & Le(-2, x + y - z, 7)
+cham = (
+ Le(0, x, 3) & Le(0, y, 3) & Le(0, z, 3) &
+ Le(z - 2, x, z + 2) & Le(1 - z, x, 5 - z) &
+ Le(z - 2, y, z + 2) & Le(1 - z, y, 5 - z) &
+ Le(y - 2, x, y + 2) & Le(1 - y, x, 5 - y))
+
+rhom = cham & (
+ Le(x + y + z, 7) & Ge(-2, -x - y - z) &
+ Le(-1, x + y - z, 4) & Le(-1, x - y + z, 4) & Le(-1, -x + y + z, 4))
+
+cubo = (
+ Le(0, x, 5) & Le(0, y, 5) & Le(0, z, 5) &
+ Le(x - 4, y, x + 4) & Le(-x + 1, y, -x + 9) &
+ Le(y - 4, z, y + 4) & Le(-y + 1, z, -y + 9) &
+ Le(z - 4, x, z + 4) & Le(-z + 1, x, -z + 9) &
+ Le(3, x + y + z, 12) & Le(-2, x - y + z, 7) &
+ Le(-2, -x + y + z, 7) & Le(-2, x + y - z, 7))
if __name__ == '__main__':
# the cube consists of 6 square faces, the hypersurface of the tesseract
# consists of 8 cubical cells.
-from linpy import *
+from linpy import Le, symbols
x, y, z, t = symbols('x y z t')
tesseract = Le(0, x, 1) & Le(0, y, 1) & Le(0, z, 1) & Le(0, t, 1)
+
def faces(polyhedron):
for points in polyhedron.faces():
face = points[0].aspolyhedron()
- face = face.convex_union(*[point.aspolyhedron() for point in points[1:]])
+ face = face.convex_union(*[point.aspolyhedron()
+ for point in points[1:]])
yield face
+
if __name__ == '__main__':
print('Faces of tesseract\n\n {}\n\nare:\n'.format(tesseract))
for face in faces(tesseract):
A polyhedral library based on isl
"""
-from .geometry import GeometricObject, Point, Vector
-from .linexprs import LinExpr, Symbol, symbols, Dummy, Rational
-from .polyhedra import Polyhedron, Lt, Le, Eq, Ne, Ge, Gt, Ne, Empty, Universe
-from .domains import Domain, And, Or, Not
from ._version import __version__
+from .domains import And, Domain, Not, Or
+from .geometry import GeometricObject, Point, Vector
+from .linexprs import Dummy, LinExpr, Rational, Symbol, symbols
+from .polyhedra import Empty, Eq, Ge, Gt, Le, Lt, Ne, Polyhedron, Universe
__all__ = [
- 'LinExpr', 'Symbol', 'symbols', 'Dummy', 'Rational',
- 'GeometricObject', 'Point', 'Vector',
- 'Polyhedron', 'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt', 'Empty', 'Universe',
- 'Domain', 'And', 'Or', 'Not',
'__version__',
+ 'And',
+ 'Domain',
+ 'Dummy',
+ 'Empty',
+ 'Eq',
+ 'Ge',
+ 'GeometricObject',
+ 'Gt',
+ 'Le',
+ 'LinExpr',
+ 'Lt',
+ 'Ne',
+ 'Not',
+ 'Or',
+ 'Point',
+ 'Polyhedron',
+ 'Rational',
+ 'Symbol',
+ 'symbols',
+ 'Universe',
+ 'Vector',
]
from fractions import Fraction
from . import islhelper
-from .islhelper import mainctx, libisl
-from .linexprs import LinExpr, Symbol
from .geometry import GeometricObject, Point, Vector
+from .islhelper import libisl
+from .linexprs import LinExpr, Symbol
__all__ = [
+ 'And',
'Domain',
- 'And', 'Or', 'Not',
+ 'Not',
+ 'Or',
]
return argument.aspolyhedron()
else:
raise TypeError('argument must be a string '
- 'or a GeometricObject instance')
+ 'or a GeometricObject instance')
else:
for polyhedron in polyhedra:
if not isinstance(polyhedron, Polyhedron):
if symbol in symbols:
n += 1
elif n > 0:
- islset = libisl.isl_set_project_out(islset,
- libisl.isl_dim_set, index + 1, n)
+ 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)
+ islset = libisl.isl_set_project_out(
+ islset, libisl.isl_dim_set, 0, n)
symbols = [symbol for symbol in self.symbols if symbol not in symbols]
return Domain._fromislset(islset, symbols)
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 = 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 the vertices of the domain, as a list of rational instances of
Point.
"""
- 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);
+ self.symbols)
+ vertices = libisl.isl_basic_set_compute_vertices(islbset)
vertices = islhelper.isl_vertices_vertices(vertices)
points = []
for vertex in vertices:
if self._RE_COORDINATE is None:
constraints = islhelper.isl_basic_set_constraints(expression)
for constraint in constraints:
- constant = libisl.isl_constraint_get_constant_val(constraint)
+ 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 = \
+ 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)
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)
+ denominator = \
+ 1 if denominator is None else int(denominator)
coordinate = Fraction(numerator, denominator)
coordinates.append((symbol, coordinate))
points.append(Point(coordinates))
def points(self):
"""
Return the integer points of a bounded domain, as a list of integer
- instances of Point. If the domain is not bounded, a ValueError exception
- is raised.
+ instances of Point. If the domain is not bounded, a ValueError
+ exception is raised.
"""
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 = 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))
similar to LinExpr.subs().
"""
polyhedra = [polyhedron.subs(symbol, expression)
- for polyhedron in self.polyhedra]
+ for polyhedron in self.polyhedra]
return Domain(*polyhedra)
@classmethod
@classmethod
def _toislset(cls, polyhedra, symbols):
polyhedron = polyhedra[0]
- islbset = polyhedron._toislbasicset(polyhedron.equalities,
- polyhedron.inequalities, symbols)
+ 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)
+ 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
Convert the domain to a SymPy expression.
"""
import sympy
- polyhedra = [polyhedron.tosympy() for polyhedron in polyhedra]
+ polyhedra = [polyhedron.tosympy() for polyhedron in self.polyhedra]
return sympy.Or(*polyhedra)
else:
return domains[0].intersection(*domains[1:])
+
def Or(*domains):
"""
Create the union domain of the domains given in arguments.
else:
return domains[0].union(*domains[1:])
+
def Not(domain):
"""
Create the complementary domain of the domain given in argument.
import numbers
import operator
-from abc import ABC, abstractproperty, abstractmethod
-from collections import OrderedDict, Mapping
+from abc import ABC, abstractmethod, abstractproperty
+from collections import Mapping, OrderedDict
from .linexprs import Symbol
def __new__(cls, coordinates):
"""
- Create a coordinate system from a dictionary or a sequence that maps the
- symbols to their coordinates. Coordinates must be rational numbers.
+ Create a coordinate system from a dictionary or a sequence that maps
+ the symbols to their coordinates. Coordinates must be rational numbers.
"""
if isinstance(coordinates, Mapping):
coordinates = coordinates.items()
def __repr__(self):
string = ', '.join(['{!r}: {!r}'.format(symbol, coordinate)
- for symbol, coordinate in self.coordinates()])
+ for symbol, coordinate in self.coordinates()])
return '{}({{{}}})'.format(self.__class__.__name__, string)
def _map(self, func):
def __sub__(self, other):
"""
If other is a point, substract it from self and return the resulting
- vector. If other is a vector, translate the point by the opposite vector
- and returns the resulting point.
+ vector. If other is a vector, translate the point by the opposite
+ vector and returns the resulting point.
"""
coordinates = []
if isinstance(other, Point):
def __new__(cls, initial, terminal=None):
"""
- Create a vector from a dictionary or a sequence that maps the symbols to
- their coordinates, or as the displacement between two points.
+ Create a vector from a dictionary or a sequence that maps the symbols
+ to their coordinates, or as the displacement between two points.
"""
if not isinstance(initial, Point):
initial = Point(initial)
result += coordinate1 * coordinate2
return result
- def __hash__(self):
- return super().__hash__()
-
def norm(self):
"""
Return the norm of the vector.
def asunit(self):
"""
- Return the normalized vector, i.e. the vector of same direction but with
- norm 1.
+ Return the normalized vector, i.e. the vector of same direction but
+ with norm 1.
"""
return self / self.norm()
# You should have received a copy of the GNU General Public License
# along with LinPy. If not, see <http://www.gnu.org/licenses/>.
-import ctypes, ctypes.util
+import ctypes
+import ctypes.util
import re
from . import _islhelper
-from ._islhelper import *
+from ._islhelper import (isl_basic_set_constraints, isl_set_basic_sets,
+ isl_set_points, isl_vertices_vertices)
__all__ = [
- 'libisl',
- 'isl_version',
- 'mainctx',
- 'isl_val_to_int',
- 'isl_basic_set_to_str', 'isl_basic_set_constraints',
- 'isl_set_to_str', 'isl_set_basic_sets',
+ 'isl_basic_set_constraints',
+ 'isl_basic_set_to_str',
+ 'isl_multi_aff_to_str',
+ 'isl_set_basic_sets',
'isl_set_points',
+ 'isl_set_to_str',
+ 'isl_val_to_int',
+ 'isl_version',
'isl_vertices_vertices',
- 'isl_multi_aff_to_str',
+ 'libisl',
+ 'mainctx',
]
libisl.isl_printer_get_str.restype = ctypes.c_char_p
+
def isl_val_to_int(islval):
islpr = libisl.isl_printer_to_str(mainctx)
islpr = libisl.isl_printer_print_val(islpr, islval)
string = libisl.isl_printer_get_str(islpr).decode()
return int(string)
+
def isl_basic_set_to_str(islbset):
islpr = libisl.isl_printer_to_str(mainctx)
islpr = libisl.isl_printer_print_basic_set(islpr, islbset)
string = libisl.isl_printer_get_str(islpr).decode()
return string
+
def isl_set_to_str(islset):
islpr = libisl.isl_printer_to_str(mainctx)
islpr = libisl.isl_printer_print_set(islpr, islset)
string = libisl.isl_printer_get_str(islpr).decode()
return string
+
def isl_multi_aff_to_str(islmaff):
islpr = libisl.isl_printer_to_str(mainctx)
islpr = libisl.isl_printer_print_multi_aff(islpr, islmaff)
import numbers
import re
-from collections import OrderedDict, defaultdict, Mapping
+from collections import defaultdict, Mapping, OrderedDict
from fractions import Fraction, gcd
__all__ = [
+ 'Dummy',
'LinExpr',
- 'Symbol', 'Dummy', 'symbols',
'Rational',
+ 'Symbol',
+ 'symbols',
]
def __new__(cls, coefficients=None, constant=0):
"""
Return a linear expression from a dictionary or a sequence, that maps
- symbols to their coefficients, and a constant term. The coefficients and
- the constant term must be rational numbers.
+ symbols to their coefficients, and a constant term. The coefficients
+ and the constant term must be rational numbers.
For example, the linear expression x + 2*y + 1 can be constructed using
one of the following instructions:
>>> LinExpr('x + 2y + 1')
A linear expression with a single symbol of coefficient 1 and no
- constant term is automatically subclassed as a Symbol instance. A linear
- expression with no symbol, only a constant term, is automatically
- subclassed as a Rational instance.
+ constant term is automatically subclassed as a Symbol instance. A
+ linear expression with no symbol, only a constant term, is
+ automatically subclassed as a Rational instance.
"""
if isinstance(coefficients, str):
if constant != 0:
symbol, coefficient = coefficients[0]
if coefficient == 1:
return symbol
- coefficients = [(symbol, Fraction(coefficient))
- for symbol, coefficient in coefficients if coefficient != 0]
+ coefficients = [(symbol_, Fraction(coefficient_))
+ for symbol_, coefficient_ in coefficients
+ if coefficient_ != 0]
coefficients.sort(key=lambda item: item[0].sortkey())
self = object().__new__(cls)
self._coefficients = OrderedDict(coefficients)
Return the product of the linear expression by a rational.
"""
if isinstance(other, numbers.Rational):
- coefficients = ((symbol, coefficient * other)
+ coefficients = (
+ (symbol, coefficient * other)
for symbol, coefficient in self._coefficients.items())
constant = self._constant * other
return LinExpr(coefficients, constant)
Return the quotient of the linear expression by a rational.
"""
if isinstance(other, numbers.Rational):
- coefficients = ((symbol, coefficient / other)
+ coefficients = (
+ (symbol, coefficient / other)
for symbol, coefficient in self._coefficients.items())
constant = self._constant / other
return LinExpr(coefficients, constant)
make all values integer.
"""
lcd = functools.reduce(lambda a, b: a*b // gcd(a, b),
- [value.denominator for value in self.values()])
+ [value.denominator for value in self.values()])
return self * lcd
def subs(self, symbol, expression=None):
symbol = Symbol(symbol.name)
coefficients.append((symbol, coefficient))
else:
- raise TypeError('non-linear expression: {!r}'.format(expression))
+ raise TypeError('non-linear expression: {!r}'.format(
+ expression))
expression = LinExpr(coefficients, constant)
if not isinstance(expression, cls):
- raise TypeError('cannot convert to a {} instance'.format(cls.__name__))
+ raise TypeError('cannot convert to a {} instance'.format(
+ cls.__name__))
return expression
def tosympy(self):
# along with LinPy. If not, see <http://www.gnu.org/licenses/>.
import functools
-import math
import numbers
from . import islhelper
-from .islhelper import mainctx, libisl
+from .domains import Domain
from .geometry import GeometricObject, Point
+from .islhelper import libisl, mainctx
from .linexprs import LinExpr, Rational
-from .domains import Domain
__all__ = [
+ 'Empty',
+ 'Eq',
+ 'Ge',
+ 'Gt',
+ 'Le',
+ 'Lt',
+ 'Ne',
'Polyhedron',
- 'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt',
- 'Empty', 'Universe',
+ 'Universe',
]
class Polyhedron(Domain):
"""
A convex polyhedron (or simply "polyhedron") is the space defined by a
- system of linear equalities and inequalities. This space can be unbounded. A
- Z-polyhedron (simply called "polyhedron" in LinPy) is the set of integer
+ system of linear equalities and inequalities. This space can be unbounded.
+ A Z-polyhedron (simply called "polyhedron" in LinPy) is the set of integer
points in a convex polyhedron.
"""
def __new__(cls, equalities=None, inequalities=None):
"""
- 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
+ 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')
And(0 <= x, x <= 2, 0 <= y, y <= 2)
It may be easier to use comparison operators LinExpr.__lt__(),
- LinExpr.__le__(), LinExpr.__ge__(), LinExpr.__gt__(), or functions Lt(),
- Le(), Eq(), Ge() and Gt(), using one of the following instructions:
+ LinExpr.__le__(), LinExpr.__ge__(), LinExpr.__gt__(), or
+ functions Lt(), Le(), Eq(), Ge() and Gt(), using one of the following
+ instructions:
>>> x, y = symbols('x y')
>>> square1 = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
>>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
Finally, a polyhedron can be constructed from a GeometricObject
- instance, calling the GeometricObject.aspolyedron() method. This way, it
- is possible to compute the polyhedral hull of a Domain instance, i.e.,
- the convex hull of two polyhedra:
+ instance, calling the GeometricObject.aspolyedron() method. This way,
+ it is possible to compute the polyhedral hull of a Domain instance,
+ i.e., the convex hull of two polyhedra:
>>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
>>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
sc_equalities.append(Rational(equality).scaleint())
else:
raise TypeError('equalities must be linear expressions '
- 'or rational numbers')
+ 'or rational numbers')
sc_inequalities = []
if inequalities is not None:
for inequality in inequalities:
sc_inequalities.append(Rational(inequality).scaleint())
else:
raise TypeError('inequalities must be linear expressions '
- 'or rational numbers')
+ 'or rational numbers')
symbols = cls._xsymbols(sc_equalities + sc_inequalities)
islbset = cls._toislbasicset(sc_equalities, sc_inequalities, symbols)
return cls._fromislbasicset(islbset, symbols)
def isuniverse(self):
islbset = self._toislbasicset(self.equalities, self.inequalities,
- self.symbols)
+ self.symbols)
universe = bool(libisl.isl_basic_set_is_universe(islbset))
libisl.isl_basic_set_free(islbset)
return universe
def subs(self, symbol, expression=None):
equalities = [equality.subs(symbol, expression)
- for equality in self.equalities]
+ for equality in self.equalities]
inequalities = [inequality.subs(symbol, expression)
- for inequality in self.inequalities]
+ for inequality in self.inequalities]
return Polyhedron(equalities, inequalities)
def asinequalities(self):
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 = 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
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))
+ 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)
+ 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))
+ 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)
+ 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)
def fromsympy(cls, expression):
domain = Domain.fromsympy(expression)
if not isinstance(domain, Polyhedron):
- raise ValueError('non-polyhedral expression: {!r}'.format(expression))
+ raise ValueError('non-polyhedral expression: {!r}'.format(
+ expression))
return domain
def tosympy(self):
expression = Rational(expression)
else:
raise TypeError('arguments must be rational numbers '
- 'or linear expressions')
+ 'or linear expressions')
return func(*expressions)
return wrapper
+
@_pseudoconstructor
def Lt(*expressions):
"""
inequalities.append(right - left - 1)
return Polyhedron([], inequalities)
+
@_pseudoconstructor
def Le(*expressions):
"""
inequalities.append(right - left)
return Polyhedron([], inequalities)
+
@_pseudoconstructor
def Eq(*expressions):
"""
equalities.append(left - right)
return Polyhedron(equalities, [])
+
@_pseudoconstructor
def Ne(*expressions):
"""
domain &= ~Eq(left, right)
return domain
+
@_pseudoconstructor
def Ge(*expressions):
"""
inequalities.append(left - right)
return Polyhedron([], inequalities)
+
@_pseudoconstructor
def Gt(*expressions):
"""
# along with LinPy. If not, see <http://www.gnu.org/licenses/>.
import functools
+import importlib
import unittest
try:
- import sympy
+ importlib.import_module('sympy')
def requires_sympy(func):
@functools.wraps(func)
import unittest
-from ..domains import *
+from ..domains import And, Or
from ..linexprs import Symbol, symbols
-from ..polyhedra import *
+from ..polyhedra import Empty, Eq, Ge, Polyhedron
class TestDomain(unittest.TestCase):
def setUp(self):
x, y = symbols('x y')
self.square1 = Polyhedron(inequalities=[x, 2 - x, y, 2 - y])
- self.square2 = Polyhedron(inequalities=[x - 1, 3 - x , y - 1, 3 - y]) #correct representation
+ self.square2 = Polyhedron(inequalities=[x - 1, 3 - x, y - 1, 3 - y])
self.square3 = Polyhedron(inequalities=[x, 3 - x, y, 3 - y])
self.square4 = Polyhedron(inequalities=[x - 1, 2 - x, y - 1, 2 - y])
- self.square5 = Polyhedron(inequalities=[x - 3, 6 - x, y - 3, 6 -y])
- self.square6 = Polyhedron(equalities=[3 - y], inequalities=[x - 1, 3 - x, y - 1])
+ self.square5 = Polyhedron(inequalities=[x - 3, 6 - x, y - 3, 6 - y])
+ self.square6 = Polyhedron(equalities=[3 - y],
+ inequalities=[x - 1, 3 - x, y - 1])
self.unbound_poly = Polyhedron(inequalities=[x, 3 - x, y])
self.universe = Polyhedron([])
self.empty = Empty
self.disjoint = And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0))
- self.complement = 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)))
+ self.complement = 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)))
self.hull = And(Ge(x, 0), Ge(-x + 2, 0), Ge(y, 0), Ge(-y + 2, 0))
self.dropped = And(Ge(y, 0), Ge(-y + 2, 0))
- self.intersection = And(Ge(x - 1, 0), Ge(-x + 2, 0), Ge(y - 1, 0), Ge(-y + 2, 0))
- self.union = 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)))
- self.sum1 = 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)))
- self.sum2 =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))
- self.difference1 = Or(And(Eq(x - 3, 0), Ge(y - 1, 0), Ge(-y + 3, 0)), And(Eq(y - 3, 0), Ge(x - 1, 0), Ge(-x + 2, 0)))
+ self.intersection = And(Ge(x - 1, 0), Ge(-x + 2, 0), Ge(y - 1, 0),
+ Ge(-y + 2, 0))
+ self.union = 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)))
+ self.sum1 = 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)))
+ self.sum2 = 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))
+ self.difference1 = Or(And(Eq(x - 3, 0), Ge(y - 1, 0), Ge(-y + 3, 0)),
+ And(Eq(y - 3, 0), Ge(x - 1, 0), Ge(-x + 2, 0)))
self.difference2 = And(Ge(x + y - 4, 0), Ge(-x + 3, 0), Ge(-y + 3, 0))
self.lexmin = And(Eq(y, 0), Eq(x, 0))
self.lexmax = And(Eq(y - 2, 0), Eq(x - 2, 0))
self.assertEqual(self.empty.project([]), Empty)
def test_sample(self):
- self.assertEqual(self.square6.sample(), {Symbol('x'): 1, Symbol('y'): 3})
+ self.assertEqual(self.square6.sample(),
+ {Symbol('x'): 1, Symbol('y'): 3})
with self.assertRaises(ValueError):
self.empty.sample()
self.assertEqual(self.universe.sample(), {})
def test_intersection(self):
- self.assertEqual(self.square1.intersection(self.square2), self.intersection)
+ self.assertEqual(self.square1.intersection(self.square2),
+ self.intersection)
def test_and(self):
self.assertEqual(self.square2 & self.square1, self.intersection)
def test_difference(self):
self.assertEqual(self.square2 - self.square1, self.difference1)
- self.assertEqual(Polyhedron(self.square2 - self.square1), self.difference2)
+ self.assertEqual(Polyhedron(self.square2 - self.square1),
+ self.difference2)
self.assertEqual(self.square2 - self.square2, Empty)
self.assertEqual(self.universe - self.universe, Empty)
import math
import unittest
-from ..geometry import *
+from ..geometry import Point, Vector
from ..linexprs import Symbol
from ..polyhedra import Eq
def test_new(self):
self.assertEqual(Point({self.x: 10, self.y: 5, self.z: 1}), self.pt1)
self.assertEqual(Point([(self.x, 10), (self.y, 5), (self.z, 1)]),
- self.pt1)
+ self.pt1)
def test_symbols(self):
self.assertTupleEqual(self.pt1.symbols, (self.x, self.y, self.z))
def test_coordinates(self):
self.assertListEqual(list(self.pt1.coordinates()),
- [(self.x, 10), (self.y, 5), (self.z, 1)])
+ [(self.x, 10), (self.y, 5), (self.z, 1)])
def test_values(self):
- self.assertListEqual(list(self.pt1.values()),
- [10, 5, 1])
+ self.assertListEqual(list(self.pt1.values()), [10, 5, 1])
def test_isorigin(self):
self.assertFalse(self.pt1.isorigin())
def test_add(self):
self.assertEqual(self.pt1 + self.vec1,
- Point({self.x: 30, self.y: 35, self.z: 41}))
+ Point({self.x: 30, self.y: 35, self.z: 41}))
with self.assertRaises(TypeError):
self.pt1 + self.pt2
def test_sub(self):
self.assertEqual(self.pt1 - self.pt2,
- Vector({self.x: -5, self.y: -35, self.z: -59}))
+ Vector({self.x: -5, self.y: -35, self.z: -59}))
self.assertEqual(self.pt1 - self.vec1,
- Point({self.x: -10, self.y: -25, self.z: -39}))
+ Point({self.x: -10, self.y: -25, self.z: -39}))
def test_eq(self):
self.assertEqual(self.pt1, self.pt1)
def test_aspolyhedron(self):
self.assertEqual(self.pt1.aspolyhedron(),
- Eq(self.x, 10) & Eq(self.y, 5) & Eq(self.z, 1))
+ Eq(self.x, 10) & Eq(self.y, 5) & Eq(self.z, 1))
def test_repr(self):
self.assertEqual(repr(self.pt1), 'Point({x: 10, y: 5, z: 1})')
self.vec2 = Vector({self.x: 45, self.y: 70, self.z: 80})
def test_add(self):
- self.assertEqual(self.vec1 + self.pt1, Point({self.x: 30, self.y: 35, self.z: 41}))
- self.assertEqual(self.vec1 + self.vec2, Vector({self.x: 65, self.y: 100, self.z: 120}))
+ self.assertEqual(self.vec1 + self.pt1,
+ Point({self.x: 30, self.y: 35, self.z: 41}))
+ self.assertEqual(self.vec1 + self.vec2,
+ Vector({self.x: 65, self.y: 100, self.z: 120}))
def test_angle(self):
self.assertEqual(math.degrees(self.vec1.angle(self.vec1)), 0)
- self.assertAlmostEqual(math.degrees(self.vec1.angle(self.vec2)), 4.15129, places=5)
- self.assertAlmostEqual(math.degrees(self.vec2.angle(self.vec1)), 4.15129, places=5)
+ self.assertAlmostEqual(math.degrees(self.vec1.angle(self.vec2)),
+ 4.15129, places=5)
+ self.assertAlmostEqual(math.degrees(self.vec2.angle(self.vec1)),
+ 4.15129, places=5)
def test_cross(self):
- self.assertEqual(self.vec1.cross(self.vec2), Vector({self.x: -400, self.y: 200, self.z: 50}))
+ self.assertEqual(self.vec1.cross(self.vec2),
+ Vector({self.x: -400, self.y: 200, self.z: 50}))
def test_div(self):
- self.assertEqual(self.vec1 / 10, Vector({self.x: 2, self.y: 3, self.z: 4}))
+ self.assertEqual(self.vec1 / 10,
+ Vector({self.x: 2, self.y: 3, self.z: 4}))
def test_dot(self):
self.assertEqual(self.vec1.dot(self.vec2), 6200)
self.assertNotEqual(self.vec1, self.vec2)
def test_mul(self):
- self.assertEqual(75 * self.vec1, Vector({self.x: 1500, self.y: 2250, self.z: 3000}))
- self.assertEqual(self.vec1 * 75, Vector({self.x: 1500, self.y: 2250, self.z: 3000}))
+ self.assertEqual(75 * self.vec1,
+ Vector({self.x: 1500, self.y: 2250, self.z: 3000}))
+ self.assertEqual(self.vec1 * 75,
+ Vector({self.x: 1500, self.y: 2250, self.z: 3000}))
def test_neg(self):
- self.assertEqual(-self.vec1, Vector({self.x: -20, self.y: -30, self.z: -40}))
+ self.assertEqual(-self.vec1,
+ Vector({self.x: -20, self.y: -30, self.z: -40}))
def test_norm(self):
self.assertAlmostEqual(self.vec1.norm(), 53.85165, places=5)
self.assertAlmostEqual(unit[self.z], 0.74278, 5)
def test_sub(self):
- self.assertEqual(self.vec1 - self.pt1, Point({self.x: 10, self.y: 25, self.z: 39}))
- self.assertEqual(self.vec1 - self.vec2, Vector({self.x: -25, self.y: -40, self.z: -40}))
+ self.assertEqual(self.vec1 - self.pt1,
+ Point({self.x: 10, self.y: 25, self.z: 39}))
+ self.assertEqual(self.vec1 - self.vec2,
+ Vector({self.x: -25, self.y: -40, self.z: -40}))
# You should have received a copy of the GNU General Public License
# along with LinPy. If not, see <http://www.gnu.org/licenses/>.
-import functools
import unittest
from fractions import Fraction
-from ..linexprs import *
+from ..linexprs import Dummy, LinExpr, Rational, Symbol, symbols
from .libhelper import requires_sympy
self.expr[self.expr]
def test_coefficients(self):
- self.assertListEqual(list(self.expr.coefficients()), [(self.x, 1), (self.y, -2)])
+ self.assertListEqual(list(self.expr.coefficients()),
+ [(self.x, 1), (self.y, -2)])
def test_constant(self):
self.assertEqual(self.x.constant, 0)
def test_scaleint(self):
self.assertEqual((self.x + self.y/2 + self.z/3).scaleint(),
- 6*self.x + 3*self.y + 2*self.z)
+ 6*self.x + 3*self.y + 2*self.z)
def test_subs(self):
self.assertEqual(self.x.subs(self.x, 3), 3)
self.assertEqual(self.x.subs(self.y, 3), self.x)
self.assertEqual(self.pi.subs(self.x, 3), self.pi)
self.assertEqual(self.expr.subs(self.x, -3), -2 * self.y)
- self.assertEqual(self.expr.subs([(self.x, self.y), (self.y, self.x)]), -2*self.x + self.y + 3)
- self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}), 3 - self.z)
- self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}), 3 - self.z)
+ self.assertEqual(self.expr.subs([(self.x, self.y), (self.y, self.x)]),
+ -2*self.x + self.y + 3)
+ self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}),
+ 3 - self.z)
+ self.assertEqual(self.expr.subs({self.x: self.z, self.y: self.z}),
+ 3 - self.z)
with self.assertRaises(TypeError):
self.x.subs('x', 3)
with self.assertRaises(TypeError):
# You should have received a copy of the GNU General Public License
# along with LinPy. If not, see <http://www.gnu.org/licenses/>.
-import functools
import unittest
from ..linexprs import symbols
-from ..polyhedra import *
+from ..polyhedra import Empty, Polyhedron, Universe
from .libhelper import requires_sympy
def test_repr(self):
self.assertEqual(repr(self.square),
- "And(0 <= x, x <= 1, 0 <= y, y <= 1)")
+ 'And(0 <= x, x <= 1, 0 <= y, y <= 1)')
def test_fromstring(self):
- self.assertEqual(Polyhedron.fromstring('{x >= 0, -x + 1 >= 0, '
- 'y >= 0, -y + 1 >= 0}'), self.square)
+ self.assertEqual(
+ Polyhedron.fromstring(
+ '{x >= 0, -x + 1 >= 0, y >= 0, -y + 1 >= 0}'),
+ self.square)
def test_isempty(self):
self.assertFalse(self.square.isempty())
def test_fromsympy(self):
import sympy
sp_x, sp_y = sympy.symbols('x y')
- self.assertEqual(Polyhedron.fromsympy((sp_x >= 0) & (sp_x <= 1) &
- (sp_y >= 0) & (sp_y <= 1)), self.square)
+ self.assertEqual(
+ Polyhedron.fromsympy(
+ (sp_x >= 0) & (sp_x <= 1) & (sp_y >= 0) & (sp_y <= 1)),
+ self.square)
@requires_sympy
def test_tosympy(self):
import sympy
sp_x, sp_y = sympy.symbols('x y')
- self.assertEqual(self.square.tosympy(),
+ self.assertEqual(
+ self.square.tosympy(),
sympy.And(-sp_x + 1 >= 0, -sp_y + 1 >= 0, sp_x >= 0, sp_y >= 0))
# You should have received a copy of the GNU General Public License
# along with LinPy. If not, see <http://www.gnu.org/licenses/>.
-from distutils.core import setup, Extension
+from distutils.core import Extension, setup
with open('linpy/_version.py') as file:
+ __version__ = None
exec(file.read())
with open('README.rst') as file:
- long_description=file.read()
+ long_description = file.read()
setup(
name='LinPy',
packages=['linpy'],
ext_modules=[
Extension('linpy._islhelper',
- sources=['linpy/_islhelper.c'],
- libraries=['isl'])
+ sources=['linpy/_islhelper.c'],
+ libraries=['isl'])
]
)
projects / linpy.git / commitdiff