BGL - 如何在捆绑属性图中使用 BFS 记录距离？
BGL - How to record distances with BFS in bundled properties graph?
我正在尝试做一些简单的事情，比如获取一个节点到所有其他节点的距离，但我没有正确了解如何在我的图表中使用 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：顶点索引
breadth_first_search 的记录要求包括顶点索引。由于您使用 node-based 容器选择器 (listS)，因此没有隐式索引，因此 you should provide one:
Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property
这是一个简化的示例，显示 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), as expected. So we could supply an external, temporary index: 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：距离映射键
距离图的键 are required to be the vertex descriptor.¹
你可以看出，因为编译错误表明 distance_recorder 试图调用：
put(m_distance, v, get(m_distance, u) + 1);
其中 v 和 u 是顶点描述符（m_distance 是您提供的距离属性图）。
两种解决方案
您可以再次使用关联映射：Live
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{}));
¹ 实际上看起来像是复制粘贴错误，因为该页面错误地声明值类型也需要是 vertex-descriptor。那是（显然？）来自 docs for predecessor_recorder...
的 copy-pasted
我正在尝试做一些简单的事情，比如获取一个节点到所有其他节点的距离，但我没有正确了解如何在我的图表中使用 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：顶点索引
breadth_first_search 的记录要求包括顶点索引。由于您使用 node-based 容器选择器 (listS)，因此没有隐式索引，因此 you should provide one:
Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property
这是一个简化的示例，显示 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), as expected. So we could supply an external, temporary index: 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：距离映射键
距离图的键 are required to be the vertex descriptor.¹
你可以看出，因为编译错误表明 distance_recorder 试图调用：
put(m_distance, v, get(m_distance, u) + 1);
其中 v 和 u 是顶点描述符（m_distance 是您提供的距离属性图）。
两种解决方案
您可以再次使用关联映射：Live
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{}));
¹ 实际上看起来像是复制粘贴错误，因为该页面错误地声明值类型也需要是 vertex-descriptor。那是（显然？）来自 docs for predecessor_recorder...