# Boost :

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;
}
//------------------------------------------------------------------------------

//==============================================================================
//==============================================================================
template <class IncidenceGraph, class Buffer, class BFSVisitor,
class ColorMap>
(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.