Skip to main content

Ralsina.Me — Roberto Alsina's website

A graph is a graph is a graph.

Af­ter hack­ing for about two hours the cell de­pen­den­cies yes­ter­day us­ing dict­s, I found my­self say­ing "how can I check if the de­pen­den­cy graph is cycli­cal?"

And of course it hit me. That's the de­pen­den­cy graph. Use a graph li­brary!

I looked for about 2 min­utes be­fore find­ing one that's prob­a­bly not op­ti­mal, but is damn sim­ple and in the pub­lic do­main: by Nathan Den­ny.

First in­ter­est­ing da­ta point, the first two lines on the file (yes, I found out there is a lat­er ver­sion):

#--Version 1.0.0
#--Nathan Denny, May 27, 1999

Yup. In two days this piece of code is turn­ing 8 years old and un­touched. But it works just fine and dandy!

Here's the piece of code that makes the en­gine run which has grown from a hum­ble 10 LOC to al­most a whoop­ing 40 LOC:

class SpreadSheet(QtCore.QObject):
    _cells = {}
    tools = {}

    def __init__(self,parent):
        for name in dir(functions):

    def __setitem__(self, key, formula):
        self._cells[key] = [c[key][0],False,compile(c[key][0],"Formula for %s"%key,'eval')]

        # Dependency graph
        if not self.graph.has_node(key):
        for edge in self.graph.in_arcs(key):
        for cell in c[key][1]:
                print 'GRAPH(TOPO): ',self.graph.topological_sort()
                print 'GRAPH(BFS) : ',self.graph.bfs(key)
                for cell in self.graph.bfs(key)[1:]:
        except Graph_topological_error:
                # We made the graph cyclic
                # So, mark this cell as evil
                # And remove all incoming edges to go back to
                # status quo
                for edge in self.graph.in_arcs(key):

    def getformula(self, key):
        return self._cells[key][0]
    def __getitem__(self, key ):
        print self._cells[key]
        if self._cells[key][1]:
                return "ERROR: cyclic dependency"
                print 'evaluating [%s]: '%key,type(self._cells[key][0]),self._cells[key][0]
              return eval(self._cells[key][0],, self)

This en­gine sup­port­s:

  • Us­er de­fined func­­tions (just add them in for­­mu­

  • Cell de­pen­­den­­cies with de­tec­­tion of ci­­cles, of any length

  • Un­lim­it­ed size spread­­sheets

  • No­ti­­fi­­ca­­tion of cell changes to oth­­er mod­­ules

  • Au­­to­­mat­ic re­­cal­cu­la­­tion

  • A cus­­tom for­­mu­la lan­guage (ok, that's not in this piece of code ;-)

The whole project is now 1167 LOC, of which 591 are gen­er­at­ed or graph_lib, which means ev­ery­thing in­clud­ing the trax­ter "com­pil­er" and the UI is less than 600 lines of code.

Not too shab­by.

My goal is a func­tion­al spread­sheet with a work­ing GUI and sup­port­ing the most com­mon func­tions and pieces of the for­mu­la lan­guage in .... 2000 LOC, and I am will­ing to work on it for about two week­s.

Let's see how it turns out. Of course any­one with 5 free min­utes can con­trib­ute his favourite spread­sheet func­tion (I al­ready have sum ;-)


Comments powered by Disqus