Friday, March 16, 2007

Walking a Graph

I must have written at least 10 different DAG implementations, but I feel I still haven't found the perfect, Pythonic implementation.

I use these things to build and experiment with scenegraph based graphics engines, so therefore, the requirements are, in order of priority:

  1. Speed.

  2. Flexibility.

  3. Elegance.

I need speed, because I'd like to experiment with graphics techniques which require multiple traversals over the graph for each frame before it gets displayed to the screen.

I've tried, and given up previously, but now, I'm trying to approach the problem from a different angle, armed with Python2.5.

So, who wants to help build a super fast depth first traversal algorithm? :-)

This is the code for building my graph, with some extra features I'll need later for talking to OpenGL.

class Node(object):
A node in a graph.
_instances = weakref.WeakValueDictionary()
_instance_count = 0
def __new__(cls, *args, **kw):
instance = object.__new__(cls, *args, **kw)
instance._id = Node._instance_count
Node._instances[instance._id] = instance
Node._instance_count += 1
return instance

def get(cls, id):
Returns a node by its _id attribute.
return cls._instances[id]

def __repr__(self):
return "<%s #%s object>" % (self.__class__.__name__, self._id)

class Composite(Node):
A node in a graph, composed of other nodes.
def __init__(self, *children):
self.children = list(children)

def add(self, *nodes):

def remove(self, *nodes):

... and this is the code I'll use to benchmark my algorithms... with a free naive recursive walker included!

if __name__ == "__main__":
import time

def dispatch(node):

def walk(node, indent=0):
for child in getattr(node, 'children', []):
walk(child, indent+1)

def build_test(node, depth=0):
if depth > 5: return
n = Composite()
for i in xrange(5):
n.add(*(Node() for x in xrange(5)))
build_test(n, depth+1)

root = Composite()
t = time.clock()
print time.clock() - t


This is the fastest traversal function so far. It runs 1.37 times faster than the recursive walk. On my machine it walks 289261 nodes in 0.378 seconds. I think I can forget about this now, and work on something else :-)

def stack_walk(root):
stack = deque([root])
stack_pop = stack.pop
stack_extendleft = stack.extendleft
while stack:
node = stack_pop()
if hasattr(node, 'children'):


Of course, after writing a unit test to test the processing order of the traversal function, I discovered I got it wrong...

It should look like this:

def traverse(root, dispatch):
stack = deque([root])
stack_pop = stack.popleft
stack_extend = stack.extend
stack_rotate = stack.rotate
while stack:
node = stack_pop()
if hasattr(node, 'children'):


Johan Lindberg said...

So, who wants to help build a super fast depth first traversal algorithm? :-)

I would find this quite interesting. I'm currently trying various implementation techniques for the Rete algorithm (which also uses a DAG) to be used in a small (100% Python) Rule Engine.

I've not yet started to worry about speed since I'm still trying to get all of the Rete functionality in place but when I do, I'd most definitely be interested in trading tips and tricks... or possibly just copy whatever you concluded is the best :-)

fumanchu said...

That's certainly an interesting block of code. I wouldn't have expected Composite.remove to call extend.

Simon Wittber said...

Oops, yes, the perils of cut and paste. :) That method certainly won't work as expected!

Popular Posts