Thursday, February 24, 2005

to throw or or not to throw

Ok, I mean 'to raise', this IS a Python post.
I have recently gotten into graph programming, and been readin' the BGL book .
Not Python, but a great book on writing software libraries in general (with many c++ gems), and has some ideas about graph algorithms that would transfer into Python quite nicely. My favorite (so far) has been the concept of 'algorithm visitor'. As I cannot explain this any better than the BGL authors, I'll just quote:
""" The visitor concepts plays the same role in BGL as functors play in the STL. Functors provide a mechanism for extending an algorithm; for customizing what is done at each step of the algorithm. Visitors allow the user to insert their own operations at various steps within a graph algorithm. Unlike the STL algorithms, graph algorithms typically have multiple event points where one may want to insert a call-back via a functor. Therefore visitors do not have a single operator() method like a functor, but instead have several methods that correspond to the various event points""" More here...
So I hacked up an initial bfs implementation using the visitor concept:

def bfs(graph, start, bfs_visitor=default_bfs_visitor()):
done = {start: True}
queue = [(start, 0)]
while queue:
node, depth = queue.pop(0)
bfs_visitor.discover_vertex(node, depth)
for v in graph.adjacent_vertices(node):
bfs_visitor.discover_edge((node, v))
if(not done.has_key(v)):
done[v] = True
queue.append((v, depth+1))

default_bfs_visitor just implements dummy methods that bfs calls, (discover_vertex and discover_edge). User-defined visitors can selectively override the methods they are interested in.
My next thought was the termination condition. While by default the bfs algorithm would traverse the entire graph there are occasions to terminate early, for example if the node of interest was found or certain depth has been reached. Pygraphlib actually uses an 'end' parameter as a termination condition, which to me seems the 'node of interest' termination condition (their rationale is not well documented). I myself was interested in limiting bfs to a certain depth. First thought was to just add a max_depth paramter to bfs(). But looking at pygraphlib and my case I realized that pygraphlib picking the end vertex as termination and me picking a certain depth is kind of arbitrary. Of course I could provide two termination condition parameters, but this would both complicate and slow down the algorithm. So then I realized that the visitor can already be used for such termination. All I need is to define a special visitor that will, for example, make the bfs function exit when discover_vertex() is calle d with a depth greater than whatever value I initialize the visitor with. But how do I 'exit' bfs? One possibility was to have every visitor funtion return a false if exit is desired at this point. This did not sit right with me, though. I am more inclined to raise an exception in the termination case, which would effectively exit the function. The only problem that I see with this is that the function will now have to be called inside a try-catch block even thoug the exception is pretty much expected in this case. So this also seems wrong. What I finally came up with is the following: a standard traversal_termination_exception should be used by all the visitors that implement a termination condition. This way bfs() can just have a single try-catch for this particular exception, which keeps the code pretty clean. If a special exception really needs to be thrown instead of my traversal_termination_exception I think a Python 2.4 decorator could be useful (I will leave this as a homework exercise due to the hour ;).


Post a Comment

<< Home