[sympycore] r1226 committed - Started implementing vertex enumeration algorithm.

[codesite...@google.com]

Revision: 1226
Author: pearu.peterson
Date: Sun Jan 8 14:39:40 2012
Log: Started implementing vertex enumeration algorithm.
http://code.google.com/p/sympycore/source/detail?r=1226

Added:
/trunk/sympycore/matrices/polyhedra.py
/trunk/sympycore/matrices/tests/test_polyhedra.py
Modified:
/trunk/sympycore/heads/pow.py
/trunk/sympycore/matrices/__init__.py
/trunk/sympycore/ring/algebra.py

=======================================
--- /dev/null
+++ /trunk/sympycore/matrices/polyhedra.py Sun Jan 8 14:39:40 2012
@@ -0,0 +1,85 @@
+
+from sympycore import Logic, SymbolicEquality, Calculus, heads
+from . import Matrix
+
+class Polyhedron(object):
+
+ def __init__(self, *exprs):
+ self.A = Matrix(0,1)
+ self.I = []
+ self.L = []
+ self.names = ['*']
+ for expr in exprs:
+ self.add(expr)
+
+ def add(self, expr):
+ """ Add extra contraint to polyhedron.
+ """
+ if isinstance(expr, str):
+ if '=' in expr or '<' in expr or '>' in expr:
+ expr = Logic(expr)
+ else:
+ expr = Logic(expr+'==0')
+ elif isinstance (expr, Calculus):
+ expr = Logic (heads.EQ, (expr, Calculus(0)))
+ if not isinstance(expr, Logic):
+ raise NotImplementedError (`expr`) # expected Logic instance
+
+ op, (lhs, rhs) = expr.pair
+ i = self.A.rows
+
+ if op==heads.EQ:
+ expr = lhs - rhs
+ self.L.append(i)
+ elif op in [heads.LT, heads.LE]:
+ op = heads.GE
+ expr = rhs - lhs
+ self.I.append(i)
+ elif op in [heads.GT, heads.GE]:
+ op = heads.GE
+ expr = lhs - rhs
+ self.I.append(i)
+ else:
+ raise NotImplementedError(`op`) # expected ==, <, <=, >, >=
+
+ expr = expr.to(heads.TERM_COEFF_DICT)
+
+ rowdict = dict()
+
+ if expr.head is heads.NUMBER:
+ self.A[i,0] = expr.data
+ elif expr.head is heads.TERM_COEFF:
+ term, coeff = expr.data
+ try:
+ j = self.names.index(term)
+ except ValueError:
+ j = len(self.names)
+ self.names.append(term)
+ self.A[i,j] = coeff
+ elif expr.head is heads.TERM_COEFF_DICT:
+ for term, coeff in expr.data.iteritems():
+ if term.head == heads.NUMBER:
+ assert term.data==1,`term.pair` # expected
Calculus('1')
+ self.A[i,0] = coeff
+ else:
+ try:
+ j = self.names.index(term)
+ except ValueError:
+ j = len(self.names)
+ self.names.append(term)
+ self.A[i,j] = coeff
+ else:
+ try:
+ j = self.names.index(expr)
+ except ValueError:
+ j = len(self.names)
+ self.names.append(expr)
+ self.A[i,j] = 1
+
+ self.A = self.A.resize(i+1, len(self.names))
+
+ def show(self):
+ print 'A:',', '.join(map(str, self.names))
+ print self.A
+ print 'L:',self.L
+ print 'I:',self.I
=======================================
--- /dev/null
+++ /trunk/sympycore/matrices/tests/test_polyhedra.py Sun Jan 8 14:39:40
2012
@@ -0,0 +1,17 @@
+
+from sympycore import Polyhedron
+
+def test_Av98a():
+ constraints = '''\
+1+x1>=0
+1+x2>=0
+1-x1>=0
+1-x2>=0
+1-x1+x3>=0
+1-x2+x3>=0
+1+x1+x3>=0
+1+x2+x3>=0'''
+ p = Polyhedron(*constraints.split('\n'))
+ p.show ()
+ vertices = [(1,1,0),(-1,1,0),(1,-1,0),(-1,-1,0),(0,0,-1)]
+ rays = [(0,0,1)]
=======================================
--- /trunk/sympycore/heads/pow.py Mon Oct 17 00:33:04 2011
+++ /trunk/sympycore/heads/pow.py Sun Jan 8 14:39:40 2012
@@ -116,6 +116,9 @@
def to_ADD(self, Algebra, (base, exp), expr):
return Algebra(ADD, [expr])

+ def to_TERM_COEFF_DICT(self, cls, data, expr):
+ return expr
+
def to_EXP_COEFF_DICT(self, cls, (base, exp), expr, variables=None):
if isinstance(exp, Expr):
if exp.head is NUMBER:
=======================================
--- /trunk/sympycore/matrices/__init__.py Tue Mar 25 11:50:00 2008
+++ /trunk/sympycore/matrices/__init__.py Sun Jan 8 14:39:40 2012
@@ -4,3 +4,4 @@

from .algebra import Matrix, MatrixBase
from .functions import eye, concatenate, jacobian
+from .polyhedra import Polyhedron
=======================================
--- /trunk/sympycore/ring/algebra.py Thu Sep 22 14:33:14 2011
+++ /trunk/sympycore/ring/algebra.py Sun Jan 8 14:39:40 2012
@@ -197,6 +197,8 @@
BASE_EXP_DICT instead of TERM_COEFF_DICT.
"""
head, data = self.pair
+ if target is head:
+ return self
if target is EXP_COEFF_DICT:
return head.to_EXP_COEFF_DICT(type(self), data, self, args or
None)
if target is TERM_COEFF_DICT: