Boost.Graph can a graph that is a directedS be safely converted to a bidirectionalS?
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? 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? 2) What's the computational expense, in general, of using a bidirectionalS graph over a directedS graph in terms of speed and 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. Thanks for any insight here, Elisha Berns e.berns@computer.org tel. (310) 556 - 8332 fax (310) 556 - 2839
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
Thanks for the reply, What you mention below about the reverse_graph_adaptor:
You can use DFS or BFS with the reverse_graph adaptor <
So if I take that route, will I get some benefit in terms of saving memory, or some other optimization? I hate to sound thick-headed here, but what is DFS or BFS going to do find in this case? Elisha
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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Elisha, On Sep 21, 2005, at 6:46 PM, Elisha Berns wrote:
You can use DFS or BFS with the reverse_graph adaptor <
So if I take that route, will I get some benefit in terms of saving memory, or some other optimization? I hate to sound thick-headed here, but what is DFS or BFS going to do find in this case?
It's just a quick way to implement the approach you described of finding all the vertices that depend on a particular vertex. There's no special savings in memory or execution time.
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?
Cheers, Jeremy
participants (2)
-
Elisha Berns -
Jeremy Siek