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

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-09-21 18:46:16

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users