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

From: Jeremy Siek (jeremy.siek_at_[hidden])
Date: 2005-09-21 07:57:53

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