X-Git-Url: https://scm.cri.mines-paristech.fr/git/linpy.git/blobdiff_plain/4a5b05e6a8198c51980c14101b06a3e9e0159f4c..34bcb159c06a4725f7a2baaf5ddcc6dffd5d74fe:/pypol/linear.py diff --git a/pypol/linear.py b/pypol/linear.py index 0712e1e..74b5477 100644 --- a/pypol/linear.py +++ b/pypol/linear.py @@ -5,8 +5,8 @@ import re from fractions import Fraction, gcd -from pypol import isl -from pypol.isl import libisl +from . import isl +from .isl import libisl __all__ = [ @@ -50,6 +50,13 @@ class Expression: This class implements linear expressions. """ + __slots__ = ( + '_coefficients', + '_constant', + '_symbols', + '_dimension', + ) + def __new__(cls, coefficients=None, constant=0): if isinstance(coefficients, str): if constant: @@ -90,8 +97,7 @@ class Expression: @classmethod def _fromast(cls, node): - if isinstance(node, ast.Module): - assert len(node.body) == 1 + 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) @@ -99,9 +105,8 @@ class Expression: return Symbol(node.id) elif isinstance(node, ast.Num): return Constant(node.n) - elif isinstance(node, ast.UnaryOp): - if isinstance(node.op, ast.USub): - return -cls._fromast(node.operand) + elif isinstance(node, ast.UnaryOp) and isinstance(node.op, ast.USub): + return -cls._fromast(node.operand) elif isinstance(node, ast.BinOp): left = cls._fromast(node.left) right = cls._fromast(node.right) @@ -324,6 +329,31 @@ class Expression: def __gt__(self, other): return Polyhedron(inequalities=[(self - other)._toint() - 1]) + @classmethod + def fromsympy(cls, expr): + import sympy + coefficients = {} + constant = 0 + for symbol, coefficient in expr.as_coefficients_dict().items(): + coefficient = Fraction(coefficient.p, coefficient.q) + if symbol == sympy.S.One: + constant = coefficient + elif isinstance(symbol, sympy.Symbol): + symbol = symbol.name + coefficients[symbol] = coefficient + else: + raise ValueError('non-linear expression: {!r}'.format(expr)) + return cls(coefficients, constant) + + def tosympy(self): + import sympy + expr = 0 + for symbol, coefficient in self.coefficients(): + term = coefficient * sympy.Symbol(symbol) + expr += term + expr += self.constant + return expr + class Constant(Expression): @@ -350,11 +380,29 @@ class Constant(Expression): return bool(self.constant) def __repr__(self): - return '{}({!r})'.format(self.__class__.__name__, self._constant) + if self.constant.denominator == 1: + return '{}({!r})'.format(self.__class__.__name__, self.constant) + else: + return '{}({!r}, {!r})'.format(self.__class__.__name__, + self.constant.numerator, self.constant.denominator) + + @classmethod + def fromsympy(cls, expr): + import sympy + if isinstance(expr, sympy.Rational): + return cls(expr.p, expr.q) + elif isinstance(expr, numbers.Rational): + return cls(expr) + else: + raise TypeError('expr must be a sympy.Rational instance') class Symbol(Expression): + __slots__ = Expression.__slots__ + ( + '_name', + ) + def __new__(cls, name): if isinstance(name, Symbol): name = name.name @@ -378,6 +426,15 @@ class Symbol(Expression): def __repr__(self): return '{}({!r})'.format(self.__class__.__name__, self._name) + @classmethod + def fromsympy(cls, expr): + import sympy + if isinstance(expr, sympy.Symbol): + return cls(expr.name) + else: + raise TypeError('expr must be a sympy.Symbol instance') + + def symbols(names): if isinstance(names, str): names = names.replace(',', ' ').split() @@ -410,6 +467,13 @@ class Polyhedron: This class implements polyhedrons. """ + __slots__ = ( + '_equalities', + '_inequalities', + '_constraints', + '_symbols', + ) + def __new__(cls, equalities=None, inequalities=None): if isinstance(equalities, str): if inequalities is not None: @@ -442,23 +506,20 @@ class Polyhedron: return self @classmethod - def fromstring(cls, string): - string = string.strip() - string = re.sub(r'^\{\s*|\s*\}$', '', string) - string = re.sub(r'([^<=>])=([^<=>])', r'\1==\2', string) - string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string) - equalities = [] - inequalities = [] - for cstr in re.split(r',|;|and|&&|/\\|∧', string, flags=re.I): - tree = ast.parse(cstr.strip(), 'eval') - if not isinstance(tree, ast.Module) or len(tree.body) != 1: - raise SyntaxError('invalid syntax') - node = tree.body[0] - if not isinstance(node, ast.Expr): - raise SyntaxError('invalid syntax') - node = node.value - if not isinstance(node, ast.Compare): - raise SyntaxError('invalid syntax') + def _fromast(cls, node): + 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.BinOp) and isinstance(node.op, ast.BitAnd): + equalities1, inequalities1 = cls._fromast(node.left) + equalities2, inequalities2 = cls._fromast(node.right) + equalities = equalities1 + equalities2 + inequalities = inequalities1 + inequalities2 + return equalities, inequalities + elif isinstance(node, ast.Compare): + equalities = [] + inequalities = [] left = Expression._fromast(node.left) for i in range(len(node.ops)): op = node.ops[i] @@ -474,8 +535,23 @@ class Polyhedron: elif isinstance(op, ast.Gt): inequalities.append(left - right - 1) else: - raise SyntaxError('invalid syntax') + break left = right + else: + return equalities, inequalities + raise SyntaxError('invalid syntax') + + @classmethod + def fromstring(cls, string): + string = string.strip() + string = re.sub(r'^\{\s*|\s*\}$', '', string) + string = re.sub(r'([^<=>])=([^<=>])', r'\1==\2', string) + string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string) + tokens = re.split(r',|;|and|&&|/\\|∧', string, flags=re.I) + tokens = ['({})'.format(token) for token in tokens] + string = ' & '.join(tokens) + tree = ast.parse(string, 'eval') + equalities, inequalities = cls._fromast(tree) return cls(equalities, inequalities) @property @@ -610,6 +686,48 @@ class Polyhedron: return '{}(equalities={!r}, inequalities={!r})' \ ''.format(self.__class__.__name__, equalities, inequalities) + @classmethod + def _fromsympy(cls, expr): + import sympy + equalities = [] + inequalities = [] + if expr.func == sympy.And: + for arg in expr.args: + arg_eqs, arg_ins = cls._fromsympy(arg) + equalities.extend(arg_eqs) + inequalities.extend(arg_ins) + elif expr.func == sympy.Eq: + expr = Expression.fromsympy(expr.args[0] - expr.args[1]) + equalities.append(expr) + else: + if expr.func == sympy.Lt: + expr = Expression.fromsympy(expr.args[1] - expr.args[0] - 1) + elif expr.func == sympy.Le: + expr = Expression.fromsympy(expr.args[1] - expr.args[0]) + elif expr.func == sympy.Ge: + expr = Expression.fromsympy(expr.args[0] - expr.args[1]) + elif expr.func == sympy.Gt: + expr = Expression.fromsympy(expr.args[0] - expr.args[1] - 1) + else: + raise ValueError('non-polyhedral expression: {!r}'.format(expr)) + inequalities.append(expr) + return equalities, inequalities + + @classmethod + def fromsympy(cls, expr): + import sympy + equalities, inequalities = cls._fromsympy(expr) + return cls(equalities, inequalities) + + 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) + def _symbolunion(self, *others): symbols = set(self.symbols) for other in others: @@ -663,10 +781,13 @@ class Polyhedron: { [i0, i1] : 2i1 >= -2 - i0 } ''' Empty = eq(0,1) + Universe = Polyhedron() + if __name__ == '__main__': - p1 = Polyhedron('2a + 2b + 1 == 0') # empty - print(p1._toisl()) - p2 = Polyhedron('3x + 2y + 3 == 0') # not empty - print(p2._toisl()) + #p = Polyhedron('2a + 2b + 1 == 0') # empty + p = Polyhedron('3x + 2y + 3 == 0, y == 0') # not empty + ip = p._toisl() + print(ip) + print(ip.constraints())