Re: [Boost-users] Graph-Based Threaded Algorithms

Subject: Re: [Boost-users] Graph-Based Threaded Algorithms
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-12-23 16:07:31

> 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_at_[hidden]