[Boost-users] Boost.Graph can a graph that is a directedS be safely converted to a bidirectionalS?

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-09-20 23:00:45

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_at_[hidden]
tel. (310) 556 - 8332
fax (310) 556 - 2839