Boost graph: dijkstra_shortest_paths: cannot form

Question

I have these graph classes:

struct Vertex
{
    octomap::point3d coord;
    OcTreeNode *node;
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;

struct GraphContainer
{
    std::map<OcTreeNode*, VertexDesc> revmap;
    Graph graph;
};

and I'm trying to use dijkstra to compute shortest paths:

GraphContainer *gc = ...;
VertexDesc vGoal = ...;
std::vector<VertexDesc> pr(boost::num_vertices(g->graph));
std::vector<int> d(boost::num_vertices(g->graph));
dijkstra_shortest_paths(g->graph, vGoal,
    boost::predecessor_map(
        boost::make_iterator_property_map(
            pr.begin(),
            boost::get(boost::vertex_index, g->graph)
        )
    ).distance_map(
        boost::make_iterator_property_map(
            d.begin(),
            boost::get(boost::vertex_index, g->graph)
        )
    )
);

however it fails to compile with the error of difficult interpretation:

In file included from plugin.cpp:14:
In file included from /usr/local/include/boost/graph/adjacency_list.hpp:223:
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2697:27: error: cannot form a reference to
      'void'
        typedef value_type& reference;
                          ^
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2730:9: note: in instantiation of template
      class 'boost::detail::adj_list_any_edge_pmap::bind_<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::no_property, boost::edge_weight_t>' requested here
      : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag>
        ^
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2734:21: note: in instantiation of template
      class 'boost::detail::adj_list_choose_edge_pmap<boost::edge_weight_t,
      boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex, boost::no_property,
      boost::no_property, boost::listS>, boost::no_property>' requested here
      struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {};
                    ^
/usr/local/include/boost/graph/properties.hpp:193:9: note: in instantiation of template class
      'boost::detail::adj_list_edge_property_selector::bind_<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::no_property, boost::edge_weight_t>' requested here
      : edge_property_selector<
        ^
/usr/local/include/boost/graph/properties.hpp:213:5: note: in instantiation of template class
      'boost::detail::edge_property_map<boost::adjacency_list<boost::listS, boost::vecS,
      boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::edge_weight_t>' requested here
    mpl::if_<
    ^
/usr/local/include/boost/graph/named_function_params.hpp:261:49: note: in instantiation of template
      class 'boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
      Vertex, boost::no_property, boost::no_property, boost::listS>, boost::edge_weight_t, void>'
      requested here
    struct const_type_as_type {typedef typename T::const_type type;};
                                                ^
/usr/local/include/boost/mpl/eval_if.hpp:38:22: note: (skipping 1 context in backtrace; use
      -ftemplate-backtrace-limit=0 to see all)
    typedef typename f_::type type;
                     ^
/usr/local/include/boost/mpl/eval_if.hpp:38:22: note: in instantiation of template class
      'boost::mpl::eval_if<mpl_::bool_<true>,
      boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::edge_weight_t, void> >, boost::property_map<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::edge_weight_t, void> >' requested here
/usr/local/include/boost/graph/named_function_params.hpp:270:7: note: in instantiation of template
      class 'boost::mpl::eval_if<boost::is_same<boost::param_not_found, boost::param_not_found>,
      boost::mpl::eval_if<mpl_::bool_<true>,
      boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::edge_weight_t, void> >, boost::property_map<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::edge_weight_t, void> >, boost::mpl::identity<boost::param_not_found> >' requested here
      boost::mpl::eval_if<
      ^
/usr/local/include/boost/graph/named_function_params.hpp:304:20: note: in instantiation of template
      class 'boost::detail::choose_impl_result<mpl_::bool_<true>, boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::param_not_found, boost::edge_weight_t>' requested here
  typename detail::choose_impl_result<boost::mpl::true_, Graph, Param, PropertyTag>::type
                   ^
/usr/local/include/boost/graph/dijkstra_shortest_paths.hpp:612:8: note: while substituting deduced
      template arguments into function template 'choose_const_pmap' [with Param =
      boost::param_not_found, Graph = boost::adjacency_list<boost::listS, boost::vecS,
      boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>, PropertyTag =
      boost::edge_weight_t]
       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
       ^
plugin.cpp:780:5: note: in instantiation of function
      template specialization 'boost::dijkstra_shortest_paths<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::iterator_property_map<std::__1::__wrap_iter<int *>,
      boost::vec_adj_list_vertex_id_map<Vertex, unsigned long>, int, int &>, boost::vertex_distance_t,
      boost::bgl_named_params<boost::iterator_property_map<std::__1::__wrap_iter<unsigned long *>,
      boost::vec_adj_list_vertex_id_map<Vertex, unsigned long>, unsigned long, unsigned long &>,
      boost::vertex_predecessor_t, boost::no_property> >' requested here
    dijkstra_shortest_paths(g->graph, vGoal,
    ^
In file included from plugin.cpp:14:
In file included from /usr/local/include/boost/graph/adjacency_list.hpp:223:
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2698:33: error: cannot form a reference to
      'void'
        typedef const value_type& const_reference;
                                ^
In file included from plugin.cpp:15:
/usr/local/include/boost/graph/dijkstra_shortest_paths.hpp:612:8: error: no matching function for call
      to 'choose_const_pmap'
       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
       ^~~~~~~~~~~~~~~~~
plugin.cpp:780:5: note: in instantiation of function
      template specialization 'boost::dijkstra_shortest_paths<boost::adjacency_list<boost::listS,
      boost::vecS, boost::undirectedS, Vertex, boost::no_property, boost::no_property, boost::listS>,
      boost::iterator_property_map<std::__1::__wrap_iter<int *>,
      boost::vec_adj_list_vertex_id_map<Vertex, unsigned long>, int, int &>, boost::vertex_distance_t,
      boost::bgl_named_params<boost::iterator_property_map<std::__1::__wrap_iter<unsigned long *>,
      boost::vec_adj_list_vertex_id_map<Vertex, unsigned long>, unsigned long, unsigned long &>,
      boost::vertex_predecessor_t, boost::no_property> >' requested here
    dijkstra_shortest_paths(g->graph, vGoal,
    ^
/usr/local/include/boost/graph/named_function_params.hpp:305:3: note: candidate template ignored:
      substitution failure [with Param = boost::param_not_found, Graph =
      boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex, boost::no_property,
      boost::no_property, boost::listS>, PropertyTag = boost::edge_weight_t]
  choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag)
  ^

how to fix that?

Answer 1

If you look closely, or consult the docs, you'll find that Dijkstra wants edge weights.

You didn't supply them. That's an error.

In fact, if you want Dijkstra without weights, a BFS would do:

Use the Bellman-Ford algorithm for the case when some edge weights are negative. Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one.

Now to humour you, let's add a constant edge-weight of 1.0:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

namespace octomap {
    struct point3d { double x,y,z; };
}

struct OcTreeNode {};

struct Vertex {
    octomap::point3d coord;
    OcTreeNode *node;
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;

struct GraphContainer {
    std::map<OcTreeNode*, VertexDesc> revmap;
    Graph graph;
};

int main() {
    GraphContainer gc;
    add_vertex(gc.graph); // make sure we have a valid start vertex
    VertexDesc vGoal = vertex(0, gc.graph);

    std::vector<VertexDesc> pr(num_vertices(gc.graph));
    std::vector<int> d(num_vertices(gc.graph));

    auto idmap = get(boost::vertex_index, gc.graph); 

    dijkstra_shortest_paths(gc.graph, vGoal,
            boost::predecessor_map(boost::make_iterator_property_map(pr.begin(), idmap))
            .distance_map(boost::make_iterator_property_map(d.begin(), idmap))
            .weight_map(boost::make_constant_property<EdgeDesc>(1.0))
    );
}