Dijkstra Shortest path problem
Hi all, I'm trying to get Dijkstra's shortest path algorithm to work with my graph which has some bundled edge properties with weight as an attribute in the bundle struct edge_properties { int capacity ; double weight ; }; typedef boost::adjacency_list<listS, vecS, bidirectionalS, //directedS, property<vertex_name_t, std::string>, edge_properties> Graph; I read in the graph using the graph viz library and that works fine. (tested by printing the graph info) dynamic_properties dp; dp.property("weight", get(&edge_properties::weight, g)); dp.property("capacity", get(&edge_properties::capacity, g)); read_graphviz(in, g,dp , "name") ; I'm constantly seeing compiler errors when i use something from dijkstra-example.cpp. // Dijkstra SRC is set to 1. vertex_descriptor src = vertex(1, g); // Just as in the example std::vector<vertex_descriptor> p(num_vertices(g)); std::vector<double> d(num_vertices(g)); //RESULTS in compiler errors. See below. dijkstra_shortest_paths( g, src, predecessor_map(&p[0]).distance_map(&d[0]) ) ; //USING This call works. But have no way to get the predecessor/distance info // This fails if ***Graph*** is defined as listS,listS but works if Graph is defined as listS,vecS or vecS,vecS dijkstra_shortest_paths( g, src, weight_map(get(&edge_properties::weight,network.g)) ); The compiler error is copied. Any Pointers will be helpful. (Version of boost used = v1.34) Thanks in advance make errors /usr/include/boost/graph/dijkstra_shortest_paths.hpp: In member function 'void boost::detail::dijkstra_bfs_visitor<UniformCostVisitor, UpdatableQueue, WeightMap, PredecessorMap, DistanceMap, BinaryFunction, BinaryPredicate>::examine_edge(Edge, Graph&) [with Edge = boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>, Graph = const boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, edge_properties, boost::no_property, boost::listS>, UniformCostVisitor = boost::dijkstra_visitor<boost::null_visitor>, UpdatableQueue = boost::relaxed_heap<long unsigned int, boost::indirect_cmp<double*, std::less<double> >, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, std::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, long unsigned int> >, WeightMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, edge_properties, boost::no_property>, boost::edge_weight_t>, ..... main.cpp:34: instantiated from here /usr/include/boost/graph/dijkstra_shortest_paths.hpp:121: error: no match for call to '(std::less<double>) (const boost::detail::error_property_not_found&, double&)' /usr/include/c++/4.3/bits/stl_function.h:229: note: candidates are: bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = double] make: *** [main.o] Error 1
On Tue, 16 Mar 2010, Kya Bey wrote:
Hi all, I'm trying to get Dijkstra's shortest path algorithm to work with my graph which has some bundled edge properties with weight as an attribute in the bundle
struct edge_properties { int capacity ; double weight ; };
typedef boost::adjacency_list<listS, vecS, bidirectionalS, //directedS, property<vertex_name_t, std::string>, edge_properties> Graph;
I read in the graph using the graph viz library and that works fine. (tested by printing the graph info)
dynamic_properties dp;
dp.property("weight", get(&edge_properties::weight, g)); dp.property("capacity", get(&edge_properties::capacity, g)); read_graphviz(in, g,dp , "name") ;
I'm constantly seeing compiler errors when i use something from dijkstra-example.cpp.
// Dijkstra SRC is set to 1. vertex_descriptor src = vertex(1, g); // Just as in the example std::vector<vertex_descriptor> p(num_vertices(g)); std::vector<double> d(num_vertices(g));
//RESULTS in compiler errors. See below. dijkstra_shortest_paths( g, src, predecessor_map(&p[0]).distance_map(&d[0]) ) ;
You are missing the weight map, which is a required argument to dijkstra_shortest_paths. The graph in dijkstra-example.cpp has a built-in weight map (using old-style properties); the default method for finding weight maps does not find bundled properties named "weight".
//USING This call works. But have no way to get the predecessor/distance info // This fails if ***Graph*** is defined as listS,listS but works if Graph is defined as listS,vecS or vecS,vecS dijkstra_shortest_paths( g, src, weight_map(get(&edge_properties::weight,network.g)) );
The reason that this fails with listS,listS is that the default distance map requires that the graph have a vertex index map; graphs with vecS as the vertex container have one built in, but graphs with listS require the user to define (and fill) one manually. -- Jeremiah Willcock
//RESULTS in compiler errors. See below.
dijkstra_shortest_paths( g, src, predecessor_map(&p[0]).distance_map(&d[0]) ) ;
You are missing the weight map, which is a required argument to dijkstra_shortest_paths. The graph in dijkstra-example.cpp has a built-in weight map (using old-style properties); the default method for finding weight maps does not find bundled properties named "weight".
That did it. I added the following predecessor_map(&p[0]).distance_map(&d[0]).weight_map(get(&edge_properties::weight,g)) ) and it worked ... Thanks a lot...
participants (2)
-
Jeremiah Willcock -
Kya Bey