[Boost-users] Dijkstra Shortest path problem

Subject: [Boost-users] Dijkstra Shortest path problem
From: Kya Bey (kyabey_at_[hidden])
Date: 2010-03-16 01:37:21

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