[boost] [BGL] To customize the graph traversing

Subject: [boost] [BGL] To customize the graph traversing
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-07-14 09:57:14

Hi to all,

I'm studying the BGL, and I've a question. I've noticed that:

- the traversing algorithms, like breadth first search, only decide how
to traverse the graph, but do not perform specific calculations;
- if I want to perform any calculation during the traverse, I can do it
passing a custom visitor to the algorithm.

But the question is: how can I customize the traverse method? The
algorithms always explore enterely the graph.

EXAMPLE: every edge (u, v) of a graph have a property
"edge_can_traverse_t" that says on which of adjacent edges starting from
v I can continue the traverse.

          _C    _F
          o|    /|
         o     /
        o     /
A---->B---->D o o o >G
        \     \
         \     \
         _\|   _\|
           E     H

-----------------------------------------
| edge  | property edge_can_traverse_t  |
|       |       (vector<edge>)          |
-----------------------------------------
| (A,B) | (B,D) , (B,E)                 |
| (B,C) | empty                         |
| (B,D) | (D,F) , (D,H)                 |
| (B,E) | empty                         |
| (D,F) | empty                         |
| (D,G) | empty                         |
| (D,H) | empty                         |
-----------------------------------------

For example, if I come from the (A,B) edge, I want that the algorithm
consider only the (B,D) and (B,E) edge, and skip the (B,C) edge.

The solution I found is to modify the breadth_first_search algorithm,
adding a predicate to the visitor and performing a control when the
algorithm examines the outer edges of the current vertex. Something like
this:

//==============================================================================
// PREDICATE (in the visitor)
//==============================================================================
template <class IncidenceGraph, class PredecessorMap>
bool can_traverse_edge( edge_descriptor e, IncidenceGraph &g,
PredecessorMap p )
{
   typedef graph_traits<IncidenceGraph>::vertex_descriptor 
VertexDescriptor;
   VertexDescriptor u = source( e, g );            // select the source
of the edge
   EdgeDescriptor eFrom = edge( p(u), u );         // select the previous
visited edge
   if ( e is contained in the edge_can_traverse_t property of eFrom )
     return true;
   else
     return false;
}
//------------------------------------------------------------------------------

//==============================================================================
// breadth_first_visit
//==============================================================================
   template <class IncidenceGraph, class Buffer, class BFSVisitor,
             class ColorMap>
   void customized_breadth_first_visit
     (const IncidenceGraph& g,
      typename graph_traits<IncidenceGraph>::vertex_descriptor s,
      Buffer& Q, BFSVisitor vis, ColorMap color)
   {

[.....]

     put(color, s, Color::gray());             vis.discover_vertex(s, g);
     Q.push(s);
     while (! Q.empty()) {
       Vertex u = Q.top(); Q.pop();            vis.examine_vertex(u, g);
       for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
       {
         if ( !vis.can_traverse_edge( *ei ) )
           continue;
[.....]

   }
//------------------------------------------------------------------------------

Does it exist a better mechanism to control the traverse with the BGL?
Or I must implement my solution?

Best Regards,
Cosimo Calabrese.