X-Git-Url: https://scm.cri.mines-paristech.fr/git/linpy.git/blobdiff_plain/2a56c56cadd9be4dd461218b1620d2617ca8a924..34bcb159c06a4725f7a2baaf5ddcc6dffd5d74fe:/pypol/linear.py?ds=inline diff --git a/pypol/linear.py b/pypol/linear.py index 524b3cb..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__ = [ @@ -54,7 +54,7 @@ class Expression: '_coefficients', '_constant', '_symbols', - '_dimension' + '_dimension', ) def __new__(cls, coefficients=None, constant=0): @@ -97,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) @@ -106,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) @@ -331,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): @@ -357,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 @@ -385,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() @@ -421,7 +471,7 @@ class Polyhedron: '_equalities', '_inequalities', '_constraints', - '_symbols' + '_symbols', ) def __new__(cls, equalities=None, inequalities=None): @@ -456,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] @@ -488,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 @@ -624,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: @@ -677,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())