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

    @classmethod
    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):
        self.children.extend(nodes)

    def remove(self, *nodes):
        self.children.extend(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):
        pass

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

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

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

UPDATE:

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() 
            dispatch(node)
            if hasattr(node, 'children'):
                stack_extendleft(node.children)

UPDATE UPDATE:

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() 
        dispatch(node)
        if hasattr(node, 'children'):
            stack_extend(node.children)                    
            stack_rotate(len(node.children))