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

Subject: Re: [boost] [BGL] To customize the graph traversing
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2009-07-16 06:48:41

Cosimo Calabrese escribió:
> 
>> Yep. I see now. Sorry.
>> What if you just "unfold" you graph to explicitly create all possible 
>> paths? For example, in your example you should duplicate node D to D1 
>> and D2 and remove edge (D2->G):
>>
>>          _C       _ F
>>          o|       //|\
>>         o        / /
>>        o        / /
>> A---->B------> D1/o o o >G
>>       |         /\
>>       \        D2 \
>>        \       ^ \ \
>>         \      |  \ \
>>         _\|    |  _\||/
>>           E    |    H
>>                I
>>
> 
> 
> Yes, I've yet do it.
> 
> But the graph can increases his dimension in memory too much; moreover, 
> I must do the "vertex split" ( D in D1 and D2 ) offline, that is before 
> I use the graph in the client application; if the edge's property (that 
> explains in which edge the exploration can go) change, I must change the 
> graph on-the-fly, and my "split algorithm" is complex...
> 
> I search a strategy to understand in that direction to continue the 
> exploration maintaining the graph unchanged. If there were a way to 
> encapsulate the exploration rule, this would be a more flexible strategy.
> 

You may try to specialize out_edges() function.
See attached example.

Dmitry



#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());
 }