A graph is a graph is a graph.
After hacking for about two hours the cell dependencies yesterday using dicts, I found myself saying "how can I check if the dependency graph is cyclical?"
And of course it hit me. That's the dependency graph. Use a graph library!
I looked for about 2 minutes before finding one that's probably not optimal, but is damn simple and in the public domain: graph_lib.py by Nathan Denny.
First interesting data point, the first two lines on the file (yes, I found out there is a later version):
#--Version 1.0.0 #--Nathan Denny, May 27, 1999
Yup. In two days this piece of code is turning 8 years old and untouched. But it works just fine and dandy!
Here's the piece of code that makes the engine run which has grown from a humble 10 LOC to almost a whooping 40 LOC:
class SpreadSheet(QtCore.QObject): _cells = {} tools = {} graph=Graph() def __init__(self,parent): QtCore.QObject.__init__(self,parent) for name in dir(functions): self.tools[name]=eval('functions.'+name) def __setitem__(self, key, formula): key=key.lower() c=traxcompile('%s=%s;'%(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): self.graph.add_node(key) for edge in self.graph.in_arcs(key): self.graph.delete_edge(edge) for cell in c[key][1]: self.graph.add_edge(cell,key) try: print 'GRAPH(TOPO): ',self.graph.topological_sort() self._cells[key][1]=False print 'GRAPH(BFS) : ',self.graph.bfs(key) for cell in self.graph.bfs(key)[1:]: self.emit(QtCore.SIGNAL('changed'),(cell)) except Graph_topological_error: # We made the graph cyclic # So, mark this cell as evil self._cells[key][1]=True # And remove all incoming edges to go back to # status quo for edge in self.graph.in_arcs(key): self.graph.delete_edge(edge) def getformula(self, key): key=key.lower() return self._cells[key][0] def __getitem__(self, key ): print self._cells[key] if self._cells[key][1]: return "ERROR: cyclic dependency" else: print 'evaluating [%s]: '%key,type(self._cells[key][0]),self._cells[key][0] return eval(self._cells[key][0], self.tools, self)
This engine supports:
User defined functions (just add them in formula.py)
Cell dependencies with detection of cicles, of any length
Unlimited size spreadsheets
Notification of cell changes to other modules
Automatic recalculation
A custom formula language (ok, that's not in this piece of code ;-)
The whole project is now 1167 LOC, of which 591 are generated or graph_lib, which means everything including the traxter "compiler" and the UI is less than 600 lines of code.
Not too shabby.
My goal is a functional spreadsheet with a working GUI and supporting the most common functions and pieces of the formula language in .... 2000 LOC, and I am willing to work on it for about two weeks.
Let's see how it turns out. Of course anyone with 5 free minutes can contribute his favourite spreadsheet function (I already have sum ;-)