[BGL] To customize the graph traversing
Hi to all, I'm studying the BGL, and I've a question. I've noticed that: - the traversing algorithms, like breadth first search, only decide how to traverse the graph, but do not perform specific calculations; - if I want to perform any calculation during the traverse, I can do it passing a custom visitor to the algorithm. But the question is: how can I customize the traverse method? The algorithms always explore enterely the graph. EXAMPLE: every edge (u, v) of a graph have a property "edge_can_traverse_t" that says on which of adjacent edges starting from v I can continue the traverse. _C _F o| /| o / o / A---->B---->D o o o >G \ \ \ \ _\| _\| E H ----------------------------------------- | edge | property edge_can_traverse_t | | | (vector<edge>) | ----------------------------------------- | (A,B) | (B,D) , (B,E) | | (B,C) | empty | | (B,D) | (D,F) , (D,H) | | (B,E) | empty | | (D,F) | empty | | (D,G) | empty | | (D,H) | empty | ----------------------------------------- For example, if I come from the (A,B) edge, I want that the algorithm consider only the (B,D) and (B,E) edge, and skip the (B,C) edge. The solution I found is to modify the breadth_first_search algorithm, adding a predicate to the visitor and performing a control when the algorithm examines the outer edges of the current vertex. Something like this: //============================================================================== // PREDICATE (in the visitor) //============================================================================== template <class IncidenceGraph, class PredecessorMap> bool can_traverse_edge( edge_descriptor e, IncidenceGraph &g, PredecessorMap p ) { typedef graph_traits<IncidenceGraph>::vertex_descriptor VertexDescriptor; VertexDescriptor u = source( e, g ); // select the source of the edge EdgeDescriptor eFrom = edge( p(u), u ); // select the previous visited edge if ( e is contained in the edge_can_traverse_t property of eFrom ) return true; else return false; } //------------------------------------------------------------------------------ //============================================================================== // breadth_first_visit //============================================================================== template <class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap> void customized_breadth_first_visit (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor s, Buffer& Q, BFSVisitor vis, ColorMap color) { [.....] put(color, s, Color::gray()); vis.discover_vertex(s, g); Q.push(s); while (! Q.empty()) { Vertex u = Q.top(); Q.pop(); vis.examine_vertex(u, g); for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { if ( !vis.can_traverse_edge( *ei ) ) continue; [.....] } //------------------------------------------------------------------------------ Does it exist a better mechanism to control the traverse with the BGL? Or I must implement my solution? Best Regards, Cosimo Calabrese.
Hi Cosimo, Cosimo Calabrese wrote:
Hi to all,
I'm studying the BGL, and I've a question. I've noticed that:
- the traversing algorithms, like breadth first search, only decide how to traverse the graph, but do not perform specific calculations; - if I want to perform any calculation during the traverse, I can do it passing a custom visitor to the algorithm.
But the question is: how can I customize the traverse method? The algorithms always explore enterely the graph.
[example]
The solution I found is to modify the breadth_first_search algorithm, adding a predicate to the visitor and performing a control when the algorithm examines the outer edges of the current vertex. Something like this:
[A possible solution]
Does it exist a better mechanism to control the traverse with the BGL? Or I must implement my solution?
Best Regards, Cosimo Calabrese.
You also may try to use filtered graph adaptor http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/filtered_graph.html Regards, Dmitry
You also may try to use filtered graph adaptor http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/filtered_graph.html
Thank you Dmitry, but I can't use the filtered graph, because it completely hides edges; instead I would to hide an edge if I "come" from a particulary adjacent edge, and to show an edge if I come from another adjacent edge. In this other graph (I hope it's comprehensible...): _C _F o| /| o / o / A---->B------> D o o o >G \ ^ \ \ | \ _\| | _\| E | H I if the exploration goes through AB, and then BD, I can't go in DG, but only in DF and DH; instead if I come from ID, so I can go in DG. It is an exploration problem. I think that a Dijkstra/BFS foundation is that the graph must be immutable during the exploration. Instead I would to hide the DG edge in some cases, and to show it in other cases. Best regards, Cosimo Calabrese.
Cosimo Calabrese wrote:
You also may try to use filtered graph adaptor http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/filtered_graph.html
Thank you Dmitry,
but I can't use the filtered graph, because it completely hides edges; instead I would to hide an edge if I "come" from a particulary adjacent edge, and to show an edge if I come from another adjacent edge. In this other graph (I hope it's comprehensible...):
You graph drawing is very nice :-)
_C _F o| /| o / o / A---->B------> D o o o >G \ ^ \ \ | \ _\| | _\| E | H I
if the exploration goes through AB, and then BD, I can't go in DG, but only in DF and DH; instead if I come from ID, so I can go in DG.
It is an exploration problem. I think that a Dijkstra/BFS foundation is that the graph must be immutable during the exploration. Instead I would to hide the DG edge in some cases, and to show it in other cases.
Best regards, Cosimo Calabrese.
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 Regards, Dmitry
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. Best regards, Cosimo Calabrese.
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()); }
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; - 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? 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. Best, Cosimo Calabrese.
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.
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.
Dmitry
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()); }
Cosimo Calabrese wrote:
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.
Ok. Does the attached patch work? We add a property "degree of exploration" for each vertex (m_vo in the code).
Best regards, Cosimo Calabrese
Best, Dmitry
Hi Cosimo, I am not sure i understand what's preventing you from using a filtered_graph. It uses a property which can be dynamically modified thus making it possible to hide an edge at some point, and show it later on. You just need a trigger to inform the filter property of the last edge that has been explored. How have you stored the constraints on allowed paths ? Benoît Casoetto On Mon, Jul 20, 2009 at 3:00 PM, Cosimo Calabrese<cosimo.calabrese@tellus.it> 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; - 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?
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.
Best, Cosimo Calabrese.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi Benoît,
Hi Cosimo,
I am not sure i understand what's preventing you from using a filtered_graph. It uses a property which can be dynamically modified thus making it possible to hide an edge at some point, and show it later on. You just need a trigger to inform the filter property of the last edge that has been explored.
How have you stored the constraints on allowed paths ?
the constraints are stored in a edge property, that is a list of "authorized" edgeDescriptors. If I understand that you propose, I should apply a parametrized predicate to a filtered graph. During the exploration, when I explore a vertex, I can take the predecessor vertex, and get the edge predecessor of the examined vertex. So I can reconfigure the predicate with that edge, including the "authorized" edges and excluding the other outer edges from the graph view. So the exploration can continue only on the locally authorized edges. If I correctly understand, I think that it doesn't work. The situation returned to the Dmitry's proposal. Referring to the same attached graph (look to the Dmitry mail), when the exploration reachs the "9" vertex from "2" vertex, so the predecessor edge is 2-9. If I pass the 2-9 edge to the predicate, it excludes the 9-10 from the view, and the exploration continue to the 9-7 edge. But now the 9 vertex is "explored", so it is black, and so I consider the 9 vertex never more. So the 10, 11 and 12 vertexes aren't reachable. The problem is that the "9" vertex becomes black "prematurely", and it dipends only from the traversing algorithm (BFS in this case). So even if I apply a filter to the graph, or select the right outer edges like Dmitry's proposal, this doesn't change this fact. When the "9" vertex becomes black, it becomes inexplorable, like BFS wants. IMO, a BFS hypothesis is that the graph is immutable during all the traversing. I'm searching a method to customize the traversing algorithm, but I'm pessimist. The coloration method is cabled in the algorithm. So I think I must modify BFS so that it colors vertexes in different way. Or to find another exploration algorithm. Best regards, Cosimo Calabrese.
The problem is that the "9" vertex becomes black "prematurely", and it depends only from the traversing algorithm (BFS in this case). I'm searching a method to customize the traversing algorithm, but I'm pessimist. The coloration method is cabled in the algorithm.
I am still not sure i understand your problem correctly but i still want to help a bit. You're clearly right, the coloration method is cabled in the algorithm. BUT the color property isn't. You may decide to create a color property that does what you want (possibly returning "white" after being set to "black"?) . This is entirely up to you. Hope this helps !
Benoit . ha scritto:
The problem is that the "9" vertex becomes black "prematurely", and it depends only from the traversing algorithm (BFS in this case). I'm searching a method to customize the traversing algorithm, but I'm pessimist. The coloration method is cabled in the algorithm.
I am still not sure i understand your problem correctly but i still want to help a bit. You're clearly right, the coloration method is cabled in the algorithm. BUT the color property isn't. You may decide to create a color property that does what you want (possibly returning "white" after being set to "black"?) . This is entirely up to you.
Hope this helps !
Thanks Benoit, yes, it's what I will make. Now the question is: which is the right moment in which to turn a vertex color from black to white, without to risk to distort the sense of the Dijkstra's algorithm? I've tried a pair of strategies, but I must think a little on the question... I would want to be sure to avoid unexplored paths or to create situations of inconsistent vertex states. I hope to post a solution soon... Regards, Cosimo Calabrese
participants (3)
-
Benoit . -
Cosimo Calabrese -
Dmitry Bufistov