Hi Elisha, On Sep 20, 2005, at 11:00 PM, Elisha Berns wrote:
Hi,
I have a Boost.Graph object that needs to model as closely as possible a DAG in order to be a dependency graph. As such it is an adjacency_list with a directedS policy. All works fine, except that it also needs to work as the inverse of a dependency graph: it needs to find the vertices for a given vertex V that are the 'dependents' (?) of V, that is to say that all the found vertices depend upon V, not that V depends upon them.
So I assume that to search for the dependents of vertex V I need to get all the in-edges of V, and the in-edges of all those in-edges recursively?
Yes.
This is apparently feasible by using a bidirectionalS policy for the graph. But my questions are the following:
1) Is there some other better way to do this, such as another graph traversal algorithm?
You can use DFS or BFS with the reverse_graph adaptor. Or, if you don't really need the out-edges, then you could just have all your edges go in the other direction and use directedS.
2) What's the computational expense, in general, of using a bidirectionalS graph over a directedS graph in terms of speed and memory?
There's no cost in speed. The memory cost is that the graph takes up approximately twice as much memory.
3) In the event that there is no better way and a bidirectionalS graph is much fatter and slower than a directedS graph does it make sense to construct the bidirectionalS graph only when needed? Since I only need this when its requested, not as a permanent feature of the application, I could copy the entire directedS graph to create some other graph for this purpose. But here the graph size can vary from a few hundred vertices to several tens of thousands of vertices, so if there is a way to avoid this its probably best.
That sounds feasible. Cheers, Jeremy