# Boost :

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

Dmitry Bufistov ha scritto:
> Cosimo Calabrese wrote:
>>
>>>
>>> You may try to specialize out_edges() function.
>>> See attached example.
>>>
>>
>> Dmitry,
>>
>> thank you very much for the code. If I correctly understand it:
>>
>> - "pv" vertex property is the predecessor vertex;
>> - "outel" edge property is the list of the edges in which I can
>> continue the exploration;
> Yep.
>> - the redefined out_edges returns all the outer edges if I've
>> discovered the vertex for the first time, and only the "authorized"
>> edges (outel) if the vertex has already been discovered.
>>
>> Right?
>
> No. All the outer edges are return only for the START vertex of the BFS,
> because it does not have any predecessor info.

You're right.

>>
>> To focalize the problem, take a look at the attached image ( no more
>> ascii sketch... ). Suppose that A is the start vertex, and I want
>> reach the N vertex; suppose that I can't go in LM if I'm in CL. So the
>> path should be:
>>
>> A-B-C-D-E-F-G-H-L-M-N
>>
>> But the BFD algorithm, when it condiders the C vertex, discovers the L
>> vertex; so the outer edge of L is only LH, because LM is forbidden
>> from CL. So L becames a explored vertex, in other words a black
>> vertex. So the BFS doesn't consider the L vertex never more. So I
>> can't obtain the attended path.
>>
>> In your example, when I reach the L vertex for the first time, the
>> out_edges function returns ALL the outer edges, included the forbidden
>> LM, because the original boost::out_edges is called.
>
> Should work fine for this example.

Unfortunately this doesn't resolve the problem.

I've modified your code to implement the example's picture (you can find
it with numbered vertexes in attach, like the code implements). All the
edges can follow all their outer edges, except the 2-9 edge that can't
follow the 9-10 edge.

The result is that, for example, the "11" is not reachable. From 2-9, I
examine the 9 vertex; then I follow to the 9-7 (that is authorized), but
I consider the 9-10 edge never more, because the 9 vertex is explored
(black). So the 10, 11 and 12 vertexes are not reachable.

But it isn't true, because the path to reach the 11 vertex exists:

0-1-2-3-4-5-6-7-9-10-11

I also attach the modified code.

Best regards,
Cosimo Calabrese

#include <iostream>
#include <algorithm>
#include <boost/vector_property_map.hpp>
#include "t.hpp"

namespace std
{
std::ostream& operator<<(std::ostream &os, const outel_t &o)
{
std::copy(o.begin(), o.end(), std::ostream_iterator<Edge>(os," "));
return os << std::endl;
}
}

//-----------------------------------------------------------------------------
struct my_visitor : boost::default_bfs_visitor
{
template <typename G, typename Edge>
void examine_edge(Edge e, const G &g)
{
std::cout << "Examine edge: " << e << std::endl;
my_graph &g_ = const_cast<my_graph&>(g.get_graph());
Vertex s = boost::source(e, g_);
Vertex t = boost::target(e, g_);
boost::put(&vp_t::pred, g_, t, e);
boost::put(&vp_t::pv, g_, t, s);
}
};

//-----------------------------------------------------------------------------
typedef boost::property_map<my_graph, boost::vertex_index_t>::type vim_t;
outel_t goutel;

//-----------------------------------------------------------------------------
int main()
{
const size_t N_V = 13;
const size_t N_E = 13;

my_graph g( N_V );
using namespace boost;

// init vertexes predecessor
for ( size_t i = 0; i < N_V; ++i )
put( &vp_t::pv, g, i, i );

// edges definitions
typedef std::pair< int, int > edgeDef;
edgeDef edl[ N_E ] = { edgeDef( 0,1 ),
edgeDef( 1,2 ),
edgeDef( 2,3 ),
edgeDef( 3,4 ),
edgeDef( 4,5 ),
edgeDef( 5,6 ),
edgeDef( 6,7 ),
edgeDef( 7,8 ),
edgeDef( 7,9 ),
edgeDef( 2,9 ),
edgeDef( 9,10 ),
edgeDef( 10,11 ),
edgeDef( 10,12 ) };

for ( size_t ii = 0; ii < N_E; ++ii )
{
add_edge( edl[ ii ].first, edl[ ii ].second, g ); // add directed
add_edge( edl[ ii ].second, edl[ ii ].first, g ); // add inverse
}

graph_wrapper gw( g );
print_graph( gw, get( vertex_index, g ) );

// set the constrains; all the edges can follow all the outer edges,
// except the 2-9 edge that can't follow the 9-10 edge, like the
// attached graph
graph_traits< my_graph >::edge_iterator ei, ei_end;
for ( tie( ei, ei_end ) = edges( g ); ei != ei_end; ++ei )
{
Vertex s = boost::source( *ei, g );
Vertex t = boost::target( *ei, g );

outel_t el;
graph_traits< my_graph >::out_edge_iterator oei, oei_end;
for ( tie( oei, oei_end ) = out_edges( t, g ); oei != oei_end; ++oei )
{
if ( ( s != 2 ) || ( t != 9 ) || ( boost::target( *oei, g ) != 10 ) )
{
el.push_back(*oei);
}
}
put(&ep_t::outel, g, *ei, el);
}

boost::queue<Vertex> Q;
boost::vector_property_map<int, vim_t> col(get(vertex_index, g));
boost::breadth_first_visit( gw, *boost::vertices(gw).first, Q,
my_visitor(), col );
// boost::breadth_first_visit(g, *boost::vertices(g).first, Q,
// my_visitor(), col);
return 0;
}

#include <list>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/properties.hpp>

struct ep_t;
struct vp_t;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
vp_t, ep_t> my_graph;

typedef boost::graph_traits<my_graph>::edge_descriptor Edge;
typedef boost::graph_traits<my_graph>::vertex_descriptor Vertex;
typedef std::list<Edge> outel_t;
extern outel_t goutel;

//-----------------------------------------------------------------------------
namespace std
{
std::ostream& operator<<(std::ostream &os, const outel_t &o);
}

//-----------------------------------------------------------------------------
struct vp_t
{
Edge pred; //Edge from which the vertex has been discovered
Vertex pv;
};

//-----------------------------------------------------------------------------
struct ep_t
{
outel_t outel;
friend std::ostream& operator<<(std::ostream &os, const ep_t &o)
{
std::copy(o.outel.begin(), o.outel.end(), std::ostream_iterator<Edge>(os," "));
return os << std::endl;
}
};

//-----------------------------------------------------------------------------
class graph_wrapper
{
public:
graph_wrapper(const my_graph &g) : m_g(g) {}
const my_graph& get_graph() const { return m_g; }
private:
const my_graph &m_g;
};

namespace boost
{
//-----------------------------------------------------------------------------
template <>
struct graph_traits<graph_wrapper>
{
typedef my_graph::vertex_descriptor vertex_descriptor;
typedef my_graph::edge_descriptor edge_descriptor;
typedef outel_t::const_iterator out_edge_iterator;
typedef my_graph::in_edge_iterator in_edge_iterator;
typedef my_graph::vertex_iterator vertex_iterator;
typedef my_graph::edge_iterator edge_iterator;

typedef my_graph::directed_category directed_category;
typedef my_graph::edge_parallel_category edge_parallel_category;
typedef my_graph::traversal_category traversal_category;

typedef my_graph::vertices_size_type vertices_size_type;
typedef my_graph::edges_size_type edges_size_type;
typedef my_graph::degree_size_type degree_size_type;

static inline vertex_descriptor null_vertex();
};
//-----------------------------------------------------------------------------
inline std::pair<
boost::graph_traits< graph_wrapper >::vertex_iterator,
boost::graph_traits< graph_wrapper >::vertex_iterator
>
vertices(const graph_wrapper &g)
{
return boost::vertices(g.get_graph());
}

//-----------------------------------------------------------------------------
inline graph_traits<graph_wrapper>::degree_size_type
out_degree( graph_traits<graph_wrapper>::vertex_descriptor v,
const graph_wrapper &g )
{
return boost::out_degree(v, g.get_graph());
}

//-----------------------------------------------------------------------------
inline std::pair<
graph_traits<graph_wrapper>::out_edge_iterator,
graph_traits<graph_wrapper>::out_edge_iterator
>
out_edges( graph_traits<graph_wrapper>::vertex_descriptor v,
const graph_wrapper &g )
{
property_map<my_graph, outel_t ep_t::*>::const_type
epm(get(&ep_t::outel, g.get_graph()));
if (get(&vp_t::pv, g.get_graph(), v) != v)
{
return std::make_pair( get( epm, get( &vp_t::pred, g.get_graph(), v ) ).begin(),
get( epm, get( &vp_t::pred, g.get_graph(), v ) ).end() );
}
else
{
goutel.clear();
boost::graph_traits<my_graph>::out_edge_iterator oei, oei_end;
for (boost::tie(oei, oei_end) = boost::out_edges(v, g.get_graph());
oei != oei_end; ++oei)
{
goutel.push_back(*oei);
}
return std::make_pair(goutel.begin(), goutel.end());
}
}
}

//-----------------------------------------------------------------------------
inline boost::graph_traits<graph_wrapper>::vertex_descriptor
source( boost::graph_traits<graph_wrapper>::edge_descriptor e,
const graph_wrapper &g )
{
boost::graph_traits<my_graph>::edge_descriptor e_ = e;
return boost::source(e_, g.get_graph());
}

//-----------------------------------------------------------------------------
inline boost::graph_traits<graph_wrapper>::vertex_descriptor
target( boost::graph_traits<graph_wrapper>::edge_descriptor e,
const graph_wrapper &g )
{
return boost::target(e, g.get_graph());
}