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:
- Speed.
- Flexibility.
- 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))
