Re: [boost] [BGL] To customize the graph traversing

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/graph/breadth_first_search.hpp>
#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/adjacency_list.hpp>
#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  my_graph::adjacency_iterator     adjacency_iterator;
        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());
}