Unitary tests for Polyhedron, very incomplete

[linpy.git] / pypol / linear.py

diff --git a/pypol/linear.py b/pypol/linear.py
index 8a61744..74b5477 100644 (file)
--- a/pypol/linear.py
+++ b/pypol/linear.py
@@ -5,8 +5,8 @@ import re
 
 from fractions import Fraction, gcd
 
 
 from fractions import Fraction, gcd
 

-from pypol import isl
-from pypol.isl import libisl
+from . import isl
+from .isl import libisl

 
 
 __all__ = [
 
 
 __all__ = [


@@ -50,6 +50,13 @@ class Expression:
     This class implements linear expressions.
     """
 
     This class implements linear expressions.
     """
 

+    __slots__ = (
+        '_coefficients',
+        '_constant',
+        '_symbols',
+        '_dimension',
+    )
+

     def __new__(cls, coefficients=None, constant=0):
         if isinstance(coefficients, str):
             if constant:
     def __new__(cls, coefficients=None, constant=0):
         if isinstance(coefficients, str):
             if constant:


@@ -90,8 +97,7 @@ class Expression:
 
     @classmethod
     def _fromast(cls, node):
 
     @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)
             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)
             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)
         elif isinstance(node, ast.BinOp):
             left = cls._fromast(node.left)
             right = cls._fromast(node.right)


@@ -117,9 +122,7 @@ class Expression:
 
     @classmethod
     def fromstring(cls, string):
 
     @classmethod
     def fromstring(cls, string):

-        string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()',
-                lambda m: '{}*{}'.format(m.group(1), m.group(2)),
-                string)
+        string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string)

         tree = ast.parse(string, 'eval')
         return cls._fromast(tree)
 
         tree = ast.parse(string, 'eval')
         return cls._fromast(tree)
 


@@ -326,6 +329,31 @@ class Expression:
     def __gt__(self, other):
         return Polyhedron(inequalities=[(self - other)._toint() - 1])
 
     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):
 
 
 class Constant(Expression):
 


@@ -352,11 +380,29 @@ class Constant(Expression):
         return bool(self.constant)
 
     def __repr__(self):
         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):
 
 
 
 class Symbol(Expression):
 

+    __slots__ = Expression.__slots__ + (
+        '_name',
+    )
+

     def __new__(cls, name):
         if isinstance(name, Symbol):
             name = name.name
     def __new__(cls, name):
         if isinstance(name, Symbol):
             name = name.name


@@ -380,6 +426,15 @@ class Symbol(Expression):
     def __repr__(self):
         return '{}({!r})'.format(self.__class__.__name__, self._name)
 
     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()
 def symbols(names):
     if isinstance(names, str):
         names = names.replace(',', ' ').split()


@@ -412,6 +467,13 @@ class Polyhedron:
     This class implements polyhedrons.
     """
 
     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:
     def __new__(cls, equalities=None, inequalities=None):
         if isinstance(equalities, str):
             if inequalities is not None:


@@ -443,9 +505,54 @@ class Polyhedron:
         self._symbols = tuple(sorted(self._symbols))
         return self
 
         self._symbols = tuple(sorted(self._symbols))
         return self
 

+    @classmethod
+    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]
+                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 equalities, inequalities
+        raise SyntaxError('invalid syntax')
+

     @classmethod
     def fromstring(cls, string):
     @classmethod
     def fromstring(cls, string):

-        raise NotImplementedError
+        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
     def equalities(self):
 
     @property
     def equalities(self):


@@ -579,6 +686,48 @@ class Polyhedron:
             return '{}(equalities={!r}, inequalities={!r})' \
                     ''.format(self.__class__.__name__, equalities, inequalities)
 
             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:
     def _symbolunion(self, *others):
         symbols = set(self.symbols)
         for other in others:


@@ -612,7 +761,7 @@ class Polyhedron:
                 dim = symbols.index(symbol)
                 cin = libisl.isl_constraint_set_coefficient_val(cin, libisl.isl_dim_set, dim, val)
             if inequality.constant != 0:
                 dim = symbols.index(symbol)
                 cin = libisl.isl_constraint_set_coefficient_val(cin, libisl.isl_dim_set, dim, val)
             if inequality.constant != 0:

-                val = str(ineq.constant).encode()
+                val = str(inequality.constant).encode()

                 val = libisl.isl_val_read_from_str(_main_ctx, val)
                 cin = libisl.isl_constraint_set_constant_val(cin, val)
             bset = libisl.isl_basic_set_add_constraint(bset, cin)
                 val = libisl.isl_val_read_from_str(_main_ctx, val)
                 cin = libisl.isl_constraint_set_constant_val(cin, val)
             bset = libisl.isl_basic_set_add_constraint(bset, cin)


@@ -632,12 +781,13 @@ class Polyhedron:
             { [i0, i1] : 2i1 >= -2 - i0 } '''
 
 Empty = eq(0,1)
             { [i0, i1] : 2i1 >= -2 - i0 } '''
 
 Empty = eq(0,1)

+

 Universe = Polyhedron()
 
 Universe = Polyhedron()
 

+

 if __name__ == '__main__':
 if __name__ == '__main__':

-    e1 = Expression('2a + 2b + 1')
-    p1 = Polyhedron(equalities=[e1]) # empty
-    e2 = Expression('3x + 2y + 3')
-    p2 = Polyhedron(equalities=[e2]) # not empty
-    print(p1._toisl())
-    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())