Thank you for the tips, Andrew. What about the case where we have a child waiting on multiple parents? That seems like a bit more difficult case...?
It should never happen if you're responding to the on_tree_edge. The nice thing is that the discovery of edges in a BFS (and DFS and the MST algorithms) is that id builds a tree, meaning that every node has only one parent. If you do have multiple parents (aka polytree)... I'm not sure. You could invert the process and have each child start waiting on a semaphore initialized with its number of parents (I forget the exact terminology). Each parent signals the semaphore when its done, and the child thread will be woken up when the semaphore reaches 0. I think you can do this with condition variables also. Andrew Sutton andrew.n.sutton@gmail.com