[SciPy-user] Python Spreadsheet with Python as Core Macro Language

[Paul Kienzle]

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()