[BGL] on using visitor in dijkstra_shortest_path
Hi, The example code for extending dijkstra via gives compilation errors. Attached below is the snippet code and the error messages using gcc-4.3.3 and boost_138_0. typedef boost::adjacency_list<vecS, vecS, bidirectionalS > graphImpl_t; //----taken for doc--- template <class PredecessorMap> class record_predecessors : public dijkstra_visitor<> { public: record_predecessors(PredecessorMap p) : m_predecessor(p) { } template <class Edge, class Graph> void edge_relaxed(Edge e, Graph& g) { // set the parent of the target(e) to source(e) put(m_predecessor, target(e, g), source(e, g)); } protected: PredecessorMap m_predecessor; }; template <class PredecessorMap> record_predecessors<PredecessorMap> //error: expected constructor, destructor, or type conversion before ‘<’ token make_predecessor_recorder(PredecessorMap p) { return record_predecessors<PredecessorMap>(p); } ///---end doc-------------- ..... ... vector<vertex_t> p(num_vertices(gg)); dijkstra_shortest_paths(gg, src, predecessor_map(preds).weight_map(weights).distance_map(dists).visitor(make_predecessor_recorder(&p[0]))); Thanks in advance. -sandeep
On Wed, Jul 1, 2009 at 7:22 PM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
Hi, The example code for extending dijkstra via gives compilation errors. Attached below is the snippet code and the error messages using gcc-4.3.3 and boost_138_0.
What errors? Andrew Sutton andrew.n.sutton@gmail.com
On Thu, Jul 2, 2009 at 5:02 AM, Andrew Sutton <andrew.n.sutton@gmail.com>wrote:
On Wed, Jul 1, 2009 at 7:22 PM, Sandeep Gupta <gupta.sandeep@gmail.com
wrote:
Hi, The example code for extending dijkstra via gives compilation errors. Attached below is the snippet code and the error messages using gcc-4.3.3 and boost_138_0.
What errors?
Hi Andrew, It gives following errors: In file included from main.cpp:6: debugDijkstra.hpp:30: error: expected constructor, destructor, or type conversion before ‘<’ token at the location: template <class PredecessorMap> record_predecessors<PredecessorMap> //error here make_predecessor_recorder(PredecessorMap p) { Thanks sandeep
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
It gives following errors:
In file included from main.cpp:6: debugDijkstra.hpp:30: error: expected constructor, destructor, or type conversion before ‘<’ token
at the location: template <class PredecessorMap> record_predecessors<PredecessorMap> //error here make_predecessor_recorder(PredecessorMap p) {
Sorry. I didn't sere the comments the first time. This code is basically defining a class that has the same name as a function (record_predecessors) that is already defined in the BGL. Change the name of the class (and constructor) and it should work fine. It did for me. Or you could just use the predecessor_recorder class, which is created by the record_predecessor function :) Andrew Sutton andrew.n.sutton@gmail.com
Thanks Andrew. I changed the name and that error is now gone but I am still having difficulty in defining visitor function: As I understand the visitor's argument should model "Dijkstra Visitor". Hence i created record_predecessor which is derived from dijkstra_visitor and therefore I assume would model "Dijkstra Visitor". After this I made following call vector<vertex_t> p(num_vertices(gg)); record_predecessor<vector<vertex_t> > rp(p); dijkstra_shortest_paths(gg, src, predecessor_map(preds).weight_map(weights).distance_map(dists).visitor(rp)); But this isn't legal. Please let me know what am i missing. I also tried using the record_predecessors method of visitor as following: vector<vertex_t> p(num_vertices(gg)); dijkstra_shortest_paths(gg, src, dijkstra_shortest_paths(gg, src, predecessor_map(preds).weight_map(weights).distance_map(dists).visitor(make_dijkstra_visitor(record_predecessors(p, on_edge_relaxed())))); But this doesn't seem to work as well. The full code is available at http://codepad.org/98AovhZO . Attached below are the errors. */home/sandeep/Computing/boost_sandbox/boost-trunk/boost/graph/named_function_params.hpp:112: error: field ‘boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int, std::less<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> >, std::allocator<std::pair<const boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int>
()(int), boost::edge_weight_t, boost::bgl_named_params<boost::associative_property_map<std::map<unsigned int, unsigned int, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, unsigned int> > > >, boost::vertex_predecessor_t, boost::no_property> >::m_value’ invalidly declared function type*
*/home/sandeep/Computing/boost_sandbox/boost-trunk/boost/graph/dijkstra_shortest_paths.hpp:473: error: no matching function for call to ‘get_param(const boost::bgl_named_params<boost::dijkstra_visitor<boost::predecessor_recorder<std::vector<unsigned int, std::allocator<unsigned int> >, boost::on_edge_relaxed> >, boost::graph_visitor_t, boost::bgl_named_params<boost::associative_property_map<std::map<unsigned int, int, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, int> > > >, boost::vertex_distance_t, boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int, std::less<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> >, std::allocator<std::pair<const boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int>
()(int), boost::edge_weight_t, boost::bgl_named_params<boost::associative_property_map<std::map<unsigned int, unsigned int, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, unsigned int> > > >, boost::vertex_predecessor_t, boost::no_property> > > >&, boost::edge_weight_t)’*
thanks sandeep
Hi Andrew, I think i have found the source of the problem and its working now. There was mismatch between property_map and recorder. BTW, I just googled "record_edge_predecesors" and nothing showed up. I couldn't immediately workout visitors for dijkstra even after reading the manual and examples. Even after knowing the solution (pasted below) I don't know how one could have reached here after reading the manual. Maybe its just me and other users just getting along fine. Anyways, I appreaciate the help. -sandeep the usage: std::map<vertex_t, edge_t> epred; boost::associative_property_map< std::map<vertex_t, edge_t> > epreds(epred); dijkstra_shortest_paths(gg, src, predecessor_map(preds).weight_map(weights).distance_map(dists).visitor(make_dijkstra_visitor(record_edge_predecessors(epreds, on_edge_relaxed())))); I understand that the manual describes the visitors and gives few examples. But I couldn't On Thu, Jul 2, 2009 at 9:31 AM, Sandeep Gupta <gupta.sandeep@gmail.com>wrote:
Thanks Andrew. I changed the name and that error is now gone but I am still having difficulty in defining visitor function: As I understand the visitor's argument should model "Dijkstra Visitor". Hence i created record_predecessor which is derived from dijkstra_visitor and therefore I assume would model "Dijkstra Visitor".
After this I made following call vector<vertex_t> p(num_vertices(gg)); record_predecessor<vector<vertex_t> > rp(p); dijkstra_shortest_paths(gg, src, predecessor_map(preds).weight_map(weights).distance_map(dists).visitor(rp));
But this isn't legal. Please let me know what am i missing.
I also tried using the record_predecessors method of visitor as following: vector<vertex_t> p(num_vertices(gg)); dijkstra_shortest_paths(gg, src, dijkstra_shortest_paths(gg, src, predecessor_map(preds).weight_map(weights).distance_map(dists).visitor(make_dijkstra_visitor(record_predecessors(p, on_edge_relaxed())))); But this doesn't seem to work as well. The full code is available at http://codepad.org/98AovhZO . Attached below are the errors.
*/home/sandeep/Computing/boost_sandbox/boost-trunk/boost/graph/named_function_params.hpp:112: error: field ‘boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int, std::less<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> >, std::allocator<std::pair<const boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int>
()(int), boost::edge_weight_t, boost::bgl_named_params<boost::associative_property_map<std::map<unsigned int, unsigned int, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, unsigned int> > > >, boost::vertex_predecessor_t, boost::no_property> >::m_value’ invalidly declared function type*
*/home/sandeep/Computing/boost_sandbox/boost-trunk/boost/graph/dijkstra_shortest_paths.hpp:473: error: no matching function for call to ‘get_param(const boost::bgl_named_params<boost::dijkstra_visitor<boost::predecessor_recorder<std::vector<unsigned int, std::allocator<unsigned int> >, boost::on_edge_relaxed> >, boost::graph_visitor_t, boost::bgl_named_params<boost::associative_property_map<std::map<unsigned int, int, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, int> > > >, boost::vertex_distance_t, boost::bgl_named_params<boost::associative_property_map<std::map<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int, std::less<boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> >, std::allocator<std::pair<const boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, int>
()(int), boost::edge_weight_t, boost::bgl_named_params<boost::associative_property_map<std::map<unsigned int, unsigned int, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, unsigned int> > > >, boost::vertex_predecessor_t, boost::no_property> > > >&, boost::edge_weight_t)’*
thanks sandeep
Sandeep Gupta wrote:
BTW, I just googled "record_edge_predecesors" and nothing showed up.
Add the missing "s" ("record_edge_predecessors") and I see 188 results: http://www.google.com/#q=record_edge_predecessors _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
From here to i wasn't able to pick up the usage or
Thanks for the correction. I am bit hesitant to delve into this side issue. Hopefully I there is some substance to it. But do feel free to ignore the rest as noise. If one looks carefully there are essentially two hits (rest are duplicates)... one is at visitors.hpp which is not useful to figure out the usage and the other is a question mailing list question on same topic..this is where i picked up clues for using the visitor and started doing digging around. This is quite unproductive. I couldn't find a documented usage when one's context is dijkstra_shortest_path. If your starting page is dijkstra_shortest_path then visitor ends up at dijkstra_visitor page ( http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/DijkstraVisitor.html). figure out what was wrong with my original approach. Its feasible but very cumbersome and requires multiple hit-and-trial. thanks sandeep On Thu, Jul 2, 2009 at 12:26 PM, Stewart, Robert <Robert.Stewart@sig.com>wrote:
Sandeep Gupta wrote:
BTW, I just googled "record_edge_predecesors" and nothing showed up.
Add the missing "s" ("record_edge_predecessors") and I see 188 results:
http://www.google.com/#q=record_edge_predecessors
_____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com
IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Andrew Sutton -
Sandeep Gupta -
Stewart, Robert