Is there a name to the "things to handle" design pattern?

Question

There's a design pattern I use once in a while, and I don't know what's it called. Perhaps it has a name and someone here knows it?

It's something I use when I want to traverse a tree-like structure and do some action on all of its nodes. It goes something like this:

nodes_to_handle = [root_node]
while nodes_to_handle:
    node = nodes_to_handle.pop()
    # handle node
    nodes_to_handle += node.get_neighbors()

Note that the structure doesn't have to be a tree; for example, this pattern can be used to do a flood-fill in an array.

So, is there an accepted name to this design pattern?

Answer 1

I think what you're getting at is a more general pattern than depth-first traversal: the frontier list. A frontier list is a (sorted or unsorted) list of elements that still require processing; the algorithm continues removing elements and processing them until the list is empty or some other termination criteria is met.

My favorite example of this pattern is dijkstra's algorithm. In Dijkstra's, the frontier list is a priority queue or heap, and the smallest-valued element is popped off the heap each iteration.

Answer 2

This looks like the depth-first traversal algorithm. (since you pop the list from the end)

It can be implemented generically in a few different ways:

• Using an iterator which traverses the tree (the preferred way)
• Using a traversal function (like yours) with a callback (for the #handle node code).
  • Outside the node class
  • Inside the node class
• ...

Edit: Didn't look at the code properly. :)

Answer 3

This is a depth-first graph traversal. It is an algorithm, not a design pattern. (From Jochen Ritzel's comment.)