Re: [Boost-users] Computing a path while traversing a graph with a search algorithm

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-12-15 10:54:25

Hello Roger,

On Sun, 2006-12-10 at 17:50 +0000, Roger Leigh wrote:
> Hi folks,
> 
> I've written a program which makes use of the Boost Graph library to
> construct a graph.  I've then attached properties to both the vertices
> and edges, giving a result like this:
> 
> http://www-users.york.ac.uk/~rl522/test.pdf
> 
> However, I want to now search the graph in order to do this:
> 
> 1. When the edge is the last, i.e. the outdegree of the target is 0:
> 2. Total the edge values for all the edges followed to get here all
>    the way back to the root, and add 19.
> 3. If this total is the same value as the root node value, set a
>    particular property on each vertex those edges are connected to.
> 
> I've tried a depth_first_search using a Visitor.  I wanted to push
> each edge onto a temporary vector as I found it, and then pop it when
> the algorithm backtracked, but this doesn't work. 

How do you want to deal with multiple paths in the graph? That could
determine what kind of search this is. For example, one could have paths
A -> B -> D and A -> C -> D, where the edges along the paths have
different values. Do you want the shortest path from A to D? The longest
path? Do you want to check both paths separately? The other issue is
cycles... how would you want to treat a cycle like A -> B -> D -> A? 

>  The aim here was to
> know the path taken to get to a particular edge when that edge was
> found.  I'm completely new to using graphs (I'm actually a Biologist),
> and I think I'm missing how I should really be using the
> depth_first_search or breadth_first_search visitors to do what I need.

Looking at your depth-first search visitor, I think the BGL terminology
might be a little misleading. The "back_edge" event refers to edges that
go from the currently active vertex back to a vertex that is already on
a the current path. 

It's easy to keep a stack of *vertices* with path information, because
one can push the vertex on the stack in discover_vertex and pop the
vertex off the stack in finish_vertex. If there are no parallel edges in
the graph (e.g., two edges from A to B), one can reconstruct the path
from this information. When you traverse an edge (e.g., in the tree_edge
event), the stack will contain all of the vertices in the path up to
(but not including) the path of the edge.

For edges, we don't have an equivalent "finish_edge" event, which would
really help here. We could probably fake it: for instance, if your
visitor is only interested in "tree" edges (not back, forward, or cross
edges), you could push the edge onto the stack of edges in the tree_edge
event, then remove it in finish_vertex, because a tree_edge call always
preceeds a discover_vertex call.

Still, it depends on how you want to handle cycles and alternate paths.
This depth-first search formulation will basically ignore cycles and
alternate paths.

> It also doesn't appear to like me using the visitor to alter the
> properties on the vertices or edges during the search.  Is this
> allowed?  I'm not altering the graph, just wanting to set a few
> property values (internally stored, in this case).

Ah, right. The depth_first_search takes in a "const Graph&", and passes
that "const" through to your visitor. To modify the graph, you need to
"const_cast" to the reference type, like this:

  template < typename Edge, typename Graph >
  void back_edge(Edge e, const Graph & in_g)
  {
    Graph& g = const_cast<const Graph&>(in_g);
    // This is *never* called.
    std::cout << "BACK" << std::endl;
    s.pop_back();
  }

  Cheers,
  Doug