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