Boost logo

Boost :

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.


#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
  graph_wrapper(const my_graph &g) : m_g(g) {}
  const my_graph& get_graph() const { return m_g; }
  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,
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());
    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)
    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());

Boost list run by bdawes at, gregod at, cpdaniel at, john at