[SciPy-user] Python Spreadsheet with Python as Core Macro Language
Paul Kienzle
pkienzle@nist....
Wed Mar 12 16:59:32 CDT 2008
On Wed, Mar 12, 2008 at 09:40:09PM +0100, Sebastian Haase wrote:
> Since the GUI part is practically given with some simple wxPython
> code, one could instead ask for a "spreadsheed engine" !! This would
> be a (small) set of functions which can analysis the dependencies a
> given spreadsheet and evaluate the cells in a (non-circular) sequence
> taking the found dependencies into account. Might already exist ...
Indeed. See attached. Not the highest performance code, but it should be
enough to get one started. All you need is to parse the expressions
to identify cell references for building the dependency graph.
- Paul
-------------- next part --------------
# This program is public domain
# Author: Paul Kienzle
"""
Helper classes for implementing constraint dependency ordering.
Constraints must be evaluated in the correct order. If parameter A
depends on parameter B, then parameter B must be evaluated first.
This ConstraintsDAG class allows you to specify the links between
the constraints, and from there calculate the extract an order in
which to evaluate them.
"""
# TODO: the current algorithm is recursive, and is subject to max recursion
# depth errors if too many constraints are used. Need to construct a
# non-recursive algorithm for ordering constraints.
class Error(Exception):
"""Exception raised for errors in the constraint module."""
pass
class CyclicError(Exception):
"""
The constraint expressions have a cycle.
"""
pass
class ParsingError(Exception):
"""
A constraint expression is invalid.
"""
pass
def _order_children(depends_on, target, visited, stack):
"""
Recursion for dependency ordering algorithm.
"""
#print target,visited,stack
if target in stack:
raise CyclicError, "Cyclic constraint containing parameter %s"%(target)
if target not in depends_on or target in visited: return []
stack += [target]
visited.add(target)
order = []
for child in depends_on[target]:
#print "checking",target,"->",child
order += _order_children(depends_on, child, visited, stack)
return order+[target]
class ConstraintDAG(object):
"""
Structure to store constraint dependencies.
"""
def __init__(self, pairs=[]):
self.depends_on = {}
for a,b in pairs: self.link(a,b)
def link(self,a,b):
"""
Make a depend on b.
"""
if a not in self.depends_on: self.depends_on[a] = []
self.depends_on[a].append(b)
def links(self,a,b):
"""
Set all dependencies of a.
"""
if b == []:
if a in self.depends_on: del self.depends_on[a]
else:
self.depends_on[a] = b
def order(self):
"""
Return the set of nodes A in the order they need to be
evaluated, raising CyclicError if their are circular
dependencies.
"""
visited = set()
order = []
for target in self.depends_on.iterkeys():
#print "checking tree",target
order += _order_children(self.depends_on, target, visited, [])
return order
# ========= Test code ========
def check(msg,n,items,partialorder):
"""
Verify that the list n contains the given items, and that the list
satisfies the partial ordering given by the pairs in partial order.
"""
success = True # optimism
if set(n) != set(items) or len(n) != len(items):
success = False
print msg,"expect",n,"to contain only",items
for lo,hi in partialorder:
if lo in n and hi in n and n.index(hi) <= n.index(lo):
print msg,"expect",lo,"before",hi
success = False
if success: print msg,"passes"
def test():
import numpy
DAG = ConstraintDAG([(7,2),(5,1),(4,1),(1,2),(1,3),(6,5)])
n = DAG.order()
check("test1",n,[1,4,5,6,7],[(1,3),(1,4),(1,5),(5,6)])
DAG = ConstraintDAG([(1,6),(3,7),(4,7),(7,6),(7,5),(2,3)])
n = DAG.order()
check("test1-renumbered",n,[1,2,3,4,7],[(7,5),(7,4),(7,3),(3,2)])
DAG = ConstraintDAG(numpy.array([(7,2),(5,1),(4,1),(1,2),(1,3),(6,5)]))
n = DAG.order()
check("test1-numpy",n,[1,4,5,6,7],[(1,3),(1,4),(1,5),(5,6)])
DAG = ConstraintDAG([(1,4),(2,3),(8,4)])
n = DAG.order()
check("test2",n,[1,2,8],[])
DAG = ConstraintDAG([(1,4),(4,3),(4,5),(5,1)])
try:
n = DAG.order()
print "test3 expected CyclicError but got",n
except CyclicError,msg:
print "test3 correctly fails - error message:",msg
# large test for gross speed check
A = numpy.random.randint(4000,size=(10000,2))
A[:,1] += 4000 # Avoid cycles
DAG = ConstraintDAG(A)
n = DAG.order()
# depth test
k = 100
A = numpy.array([range(0,k),range(1,k+1)]).T
DAG = ConstraintDAG(A)
n = DAG.order()
A = numpy.array([range(1,k+1),range(0,k)]).T
DAG = ConstraintDAG(A)
n = DAG.order()
if __name__ == "__main__":
test()
More information about the SciPy-user
mailing list