提升图：dijkstra_shortest_paths：无法形成对'void'的引用 [英] Boost graph: dijkstra_shortest_paths: cannot form a reference to 'void'

问题描述

  struct顶点
 {
 octomap :: point3d coord; 
 OcTreeNode *节点; 
}; 
 
 typedef boost :: adjacency_list< boost :: listS，boost :: vecS，boost :: undirectedS，Vertex>图形; 
 typedef boost :: graph_traits< Graph> :: vertex_descriptor VertexDesc; 
 typedef boost :: graph_traits< Graph> :: edge_descriptor EdgeDesc; 
 
 struct GraphContainer 
 {
 std :: map< OcTreeNode *，VertexDesc> revmap; 
图形图形; 
}; 
  

我试图用dijkstra来计算最短路径：

  GraphContainer * gc = ...; 
 VertexDesc vGoal = ...; 
 std :: vector< VertexDesc> PR（升压::为num_vertices（G->图））; 
 std :: vector< int> d（升压::为num_vertices（G->图））; 
 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）
）
）
）; 
  

然而，它无法编译带有难解释的错误：

 从plugin.cpp包含的文件中：14：
从/usr/local/include/boost/graph/adjacency_list.hpp:223包含的文件中： 
 /usr/local/include/boost/graph/detail/adjacency_list.hpp:2697:27：错误：无法形成对
'void'的引用
 typedef value_type&参考; 
 ^ 
 /usr/local/include/boost/graph/detail/adjacency_list.hpp:2730:9：注意：在模板实例化
 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>'here requested 
：adj_list_choose_edge_pmap_helper< Tag> :: type :: template bind_< Graph，Property，Tag> 
 ^ 
 /usr/local/include/boost/graph/detail/adjacency_list.hpp:2734:21：注意：在模板的实例化中
 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>'here here 
 struct bind_：adj_list_choose_edge_pmap< Tag，Graph，Property> {}; 
 ^ 
 /usr/local/include/boost/graph/properties.hpp:193:9：注意：在模板类的实例化中
'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>'here here 
：edge_property_selector< 
 ^ 
 /usr/local/include/boost/graph/properties.hpp:213:5：注意：在模板类的实例中
'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>'这里要求
 mpl :: if_< 
 ^ 
 /usr/local/include/boost/graph/named_function_params.hpp:261:49：note：在实例化模板
 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>'
请求这里
 struct const_type_as_type {typedef typename T :: const_type type;}; 
 ^ 
 /usr/local/include/boost/mpl/eval_if.hpp:38:22：注意：（在回溯中跳过1个上下文;使用
 -ftemplate-backtrace-limit = 0查看全部）
 typedef typename f _ :: type type; 
 ^ 
 /usr/local/include/boost/mpl/eval_if.hpp:38:22：注意：在模板类的实例中
'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> >'在此处请求
 /usr/local/include/boost/graph/named_function_params.hpp:270:7：注意：在模板
 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> >'这里请求
 boost :: mpl :: eval_if< 
 ^ 
 /usr/local/include/boost/graph/named_function_params.hpp:304:20：注意：在模板实例化
 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>'here here 
 typename detail :: choose_impl_result< boost :: mpl :: true_，Graph，Param，PropertyTag> :: type 
 ^ 
 /usr/local/include/boost/graph/dijkstra_shortest_paths.hpp:612:8：注意：在将推导出的
模板参数代入函数模板'choose_const_pmap'[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：注意：在函数
的模板专业化'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_pa​​rams< 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> >'在此处请求
 dijkstra_shortest_paths（g-> graph，vGoal，
 ^ 
从plugin.cpp包含的文件中：14：
从/ usr / local /include/boost/graph/adjacency_list.hpp:223：
 /usr/local/include/boost/graph/detail/adjacency_list.hpp:2698:33：错误：无法形成对
'的引用void'
 typedef const value_type& const_reference; 
 ^ 
在plugin.cpp包含的文件中：15：
 /usr/local/include/boost/graph/dijkstra_shortest_paths.hpp： 612：8：错误：没有匹配函数调用
到'choose_const_pmap'
 choose_const_pmap（get_param（params，edge_weight），g，edge_weight），
 ^ ~~~~~~~~ ~~~~~~~~ 
 plugin.cpp：780：5：注意：在函数
模板特化的实例化中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_pa​​rams< 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> >'在此处请求
 dijkstra_shortest_paths（g-> graph，vGoal，
 ^ 
 /usr/local/include/boost/graph/named_function_params.hpp:305:3：note：candidate模板被忽略：
替换失败[使用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标记）
 ^ 
  

如何解决这个问题？

解决方案

如果你仔细观察或者咨询文档，你会发现Dijkstra需要边权。你没有提供它们。这是一个错误。

事实上，如果你想让迪杰斯特拉没有权重， a BFS会做：

在某些边权重为负的情况下使用Bellman-Ford算法。 当所有边权重等于1时，使用广度优先搜索而不是Dijkstra算法。 $ b

现在来幽默一下，让我们添加一个恒定的边缘权重为1.0： Live Live Coliru

  #include< boost / graph / adjacency_list.hpp> 
 #include< boost / graph / dijkstra_shortest_paths.hpp> 
 
 namespace octomap {
 struct point3d {double x，y，z; }; 
} 
 
 struct OcTreeNode {}; 
 
结构顶点{
 octomap :: point3d coord; 
 OcTreeNode *节点; 
}; 
 
 typedef boost :: adjacency_list< boost :: listS，boost :: vecS，boost :: undirectedS，Vertex>图形; 
 typedef boost :: graph_traits< Graph> :: vertex_descriptor VertexDesc; 
 typedef boost :: graph_traits< Graph> :: edge_descriptor EdgeDesc; 
 
 struct GraphContainer {
 std :: map< OcTreeNode *，VertexDesc> revmap; 
图形图形; 
}; 
 
 int main（）{
 GraphContainer gc; 
 add_vertex（gc.graph）; //确保我们有一个有效的开始顶点
 VertexDesc vGoal =顶点（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））
）; 
} 
  

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?

解决方案

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))
    );
}

这篇关于提升图：dijkstra_shortest_paths：无法形成对'void'的引用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！