我试图做一些简单的事情，比如获取从一个节点到所有其他节点的距离，但我没有正确地将breadth_first_search用于我的图。。。我得到了很多编译错误，我不知道为什么。
我甚至尝试了其他问题中提出的解决方案，但它们对我不起作用
有人能帮我吗？
定义：
class Position {
public:
Position() : x(0), y(0) {}
Position(int a, int b) : x(a), y(b) {}
// operator overrides
int x, y;
};
struct Group {
Group(Position pos, short c, short s) : position(pos), color(c), size(s) {}
Group() {}
Position position;
short color;
short size;
};
inline bool operator==(const Group& g1, const Group& g2) {
return g1.position == g2.position;
};
inline bool operator!=(const Group& g1, const Group& g2) {
return g1.position != g2.position;
};
typedef boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
最小示例：
int main() {
Graph graph;
// build graph
VertexDescriptor v = *boost::vertices(graph).first;
std::vector<int> distances(boost::num_vertices(graph));
boost::breadth_first_search(graph, v, boost::visitor( boost::make_bfs_visitor( boost::record_distances(distances.begin(), boost::on_tree_edge{}))));
return 0;
}
编译错误：
In file included from /usr/include/boost/graph/adjacency_list.hpp:223,
from src/../include/graph.hpp:4,
from src/main.cpp:3:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::adj_list_any_vertex_pa::bind_<boost::vertex_index_t, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, Group>’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2617:12: required from ‘struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, Group>’
/usr/include/boost/graph/detail/adjacency_list.hpp:2754:12: required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, Group, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:201:12: required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:212:10: required from ‘struct boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void>’
/usr/include/boost/mpl/eval_if.hpp:38:31: recursively required from ‘struct boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >, boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >’
/usr/include/boost/mpl/eval_if.hpp:38:31: required from ‘struct 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::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >, boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >, boost::mpl::identity<boost::param_not_found> >’
/usr/include/boost/graph/named_function_params.hpp:273:12: required from ‘struct boost::detail::choose_impl_result<mpl_::bool_<true>, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::param_not_found, boost::vertex_index_t>’
/usr/include/boost/graph/named_function_params.hpp:309:3: required by substitution of ‘template<class Param, class Graph, class PropertyTag> typename boost::detail::choose_impl_result<mpl_::bool_<true>, Graph, Param, PropertyTag>::type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag) [with Param = boost::param_not_found; Graph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; PropertyTag = boost::vertex_index_t]’
/usr/include/boost/graph/breadth_first_search.hpp:315:30: required from ‘static void boost::detail::bfs_dispatch<boost::param_not_found>::apply(VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&, boost::param_not_found) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’
/usr/include/boost/graph/breadth_first_search.hpp:343:35: required from ‘void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’
src/main.cpp:41:151: required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2547:29: error: forming reference to void
2547 | typedef value_type& reference;
| ^~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2548:35: error: forming reference to void
2548 | typedef const value_type& const_reference;
| ^~~~~~~~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2551:47: error: forming reference to void
2551 | <Graph, value_type, reference, Tag> type;
| ^~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2553:53: error: forming reference to void
2553 | <Graph, value_type, const_reference, Tag> const_type;
| ^~~~~~~~~~
In file included from src/main.cpp:7:
/usr/include/boost/graph/breadth_first_search.hpp: In instantiation of ‘static void boost::detail::bfs_dispatch<boost::param_not_found>::apply(VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&, boost::param_not_found) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’:
/usr/include/boost/graph/breadth_first_search.hpp:343:35: required from ‘void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’
src/main.cpp:41:151: required from here
/usr/include/boost/graph/breadth_first_search.hpp:315:30: error: no matching function for call to ‘choose_const_pmap(const type&, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>&, boost::vertex_index_t)’
315 | choose_const_pmap(get_param(params, vertex_index),
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
316 | g, vertex_index)),
| ~~~~~~~~~~~~~~~~
In file included from /usr/include/boost/graph/breadth_first_search.hpp:23,
from src/main.cpp:7:
/usr/include/boost/graph/named_function_params.hpp:309:3: note: candidate: ‘template<class Param, class Graph, class PropertyTag> typename boost::detail::choose_impl_result<mpl_::bool_<true>, Graph, Param, PropertyTag>::type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag)’
309 | choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag)
| ^~~~~~~~~~~~~~~~~
/usr/include/boost/graph/named_function_params.hpp:309:3: note: substitution of deduced template arguments resulted in errors seen above
的两个问题
问题1：顶点索引
breath_firstrongearch的文档化要求包括顶点索引。由于使用了基于节点的容器选择器(listS(，因此没有隐式索引，因此应该提供一个：
注意：如果使用此默认值，请确保图具有内部vertex_index属性。例如，具有VertexList=listS的相邻列表没有内部vertex_index属性
下面是一个简化的例子，显示vecS的工作原理：
实时编译器浏览器
using Graph =
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Group>;
using V = Graph::vertex_descriptor;
int main() {
Graph graph(10);
V v = vertex(0, graph);
auto vis = boost::default_bfs_visitor{};
breadth_first_search(graph, v, visitor(vis));
}
现在将vecS更改为listS:
using Graph =
boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, Group>;
未按预期编译(Live(。所以我们可以提供一个外部的临时索引：实时
std::map<V, int> tmp_index;
for (auto v : boost::make_iterator_range(vertices(graph)))
tmp_index[v] = tmp_index.size();
auto index_map = boost::make_assoc_property_map(tmp_index);
breadth_first_search(graph, v, visitor(vis).vertex_index_map(index_map));
即使具有唯一的边，它仍然可以编译(setS，Live(。
现在，让我们记录距离。
问题2：距离贴图关键点
距离贴图的关键点必须是顶点描述符。cco
您可以判断，因为编译错误表明distance _ recorder试图调用：
put(m_distance, v, get(m_distance, u) + 1);
其中v和u是顶点描述符(m_distance是您提供的距离属性映射(。
两种解决方案
您可以再次使用关联地图：实时
std::map<V, int> distances; auto vis = make_bfs_visitor(record_distances( boost::make_assoc_property_map(distances), boost::on_tree_edge{}));您可以通过临时顶点索引投影密钥来修复属性映射：Live
auto index_map = boost::make_assoc_property_map(tmp_index); auto dist_map = make_safe_iterator_property_map(dist.begin(), dist.size(), index_map); auto vis = make_bfs_visitor(record_distances(dist_map, boost::on_tree_edge{}));
实际上，似乎存在复制粘贴错误，因为该页面错误地声明值类型也需要是顶点描述符。那是(显然？(从predecessor_recorder的文档中粘贴的副本。。。