Как это работает?
record_distances - фабрика для посетителя мероприятия.make_bfs_visitor связывает это с моделью посетителя BFS (по умолчанию).
Полагаю, это был не ваш вопрос.Неясно, что вы делаете ожидаете, так как вывод не выглядит для меня информативным.Возможно, вы хотите отобразить его в более полезном формате:
for (auto vd : boost::make_iterator_range(boost::vertices(g)))
std::cout << "d[" << vd0 << ", " << vd << "] = " << distances.at(vd) << "\n";
Теперь вывод:
d[0, 0] = 0
d[0, 1] = 1
d[0, 2] = 3
d[0, 3] = 3
d[0, 4] = 3
d[0, 5] = 3
d[0, 6] = 3
d[0, 7] = 1
d[0, 8] = 2
d[0, 9] = 2
d[0, 10] = 2
d[0, 11] = 2
d[0, 12] = 3
d[0, 13] = 3
d[0, 14] = 3
Теперь, что дает?Потому что в заголовке вашего вопроса вы предлагаете ожидать:
Например, d [0, 0] = 0, d [0, 1] = 1, d [0, 2] = 1, d [0, 3] = 2, d [0, 7] = 3.
Существует явное несоответствие!d[0,7] = 1 не соответствует «более логичному» d[0,7] = 3.Тем не менее, вы ничего не сделали / неправильно / и вычисление расстояния не так.
Есть небольшая ошибка наблюдателя!Вы думаете, дескриптор вершины 7 относится к вершине, которую вы показали с этим числом во входных данных.Однако, если вы напечатаете график, который read_graphviz читает:
АГА!Что-то пошло не так, или иначе, чем вы ожидали .На самом деле, если бы вы удалили «магический бит» о ignore_other_properties, который вы на самом деле не знали значения:
boost::dynamic_properties dp; // {boost::ignore_other_properties};
Вам бы сказали об этом:
terminate called after throwing an instance of 'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::property_not_found> >'
what(): Property not found: node_id.
Действительно, вы сказали Boost читать вершины , но игнорировать идентификатор вершины из файла Dot.Таким образом, результатом является гарантированный изоморфизм графа в ваших входных данных, но идентификаторы находятся в неопределенном / определяемом реализацией порядке.
Исправляем: читаем идентификатор узла
Давайте сохраним adjacency_list<> чисто и просто, поэтому давайте создадим внешнюю карту идентификаторов:
DiGraph g;
std::map<DiGraph::vertex_descriptor, int> vertex_ids;
auto id_map = boost::make_assoc_property_map(vertex_ids);
boost::dynamic_properties dp;
dp.property("node_id", id_map);
std::ifstream dot_file("graph.dot");
boost::read_graphviz(dot_file, g, dp);
Теперь, когда мы запишем график обратно, используя исходные идентификаторы узлов:
boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, g));
std::ofstream dot_file("output.dot");
boost::write_graphviz_dp(dot_file, g, dp);
Мы возвращаем наше оригинальное изображение.Фу.
Примечание Для записи расстояний мы по-прежнему используем «технический» vertex_descriptor в качестве неявного идентификатора вершины.Это потому, что это облегчает использование vector<> в качестве карты расстояний.
В качестве альтернативы, мы можем использовать «удобный для пользователя» id_map и хранить в ассоциативном LvaluePropertMap
Используйте идентификатор узла в отчете
Отсюда относительно легко исправить отчет:
for (auto vd : boost::make_iterator_range(boost::vertices(g)))
std::cout << "d[" << id_map[vd0] << ", " << id_map[vd] << "] = " << distances.at(vd) << "\n";
Отпечатки:
d[0, 0] = 0
d[0, 1] = 1
...
d[0, 6] = 2
d[0, 7] = 3
...
Ууу!Разумность восстановлена.
Бонус: визуализация расстояний
Давайте добавим метку к каждому ребру, отображающую расстояние от корня до его целевой вершины:
std::map<DiGraph::edge_descriptor, int> edge_labels;
auto label_map = boost::make_assoc_property_map(edge_labels);
for (auto ed : boost::make_iterator_range(boost::edges(g)))
label_map[ed] = distances.at(target(ed, g));
boost::dynamic_properties dp;
dp.property("node_id", id_map);
dp.property("label", label_map);
std::ofstream dot_file("output.dot");
boost::write_graphviz_dp(dot_file, g, dp);
Теперь мы имеемЭтот красивый, обнадеживающий вывод:
Полный список демонстраций
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graphviz.hpp>
using DiGraph = boost::adjacency_list<>;
int main()
{
DiGraph g;
std::map<DiGraph::vertex_descriptor, int> vertex_ids;
auto id_map = boost::make_assoc_property_map(vertex_ids);
{
boost::dynamic_properties dp;
dp.property("node_id", id_map);
std::ifstream dot_file("graph.dot");
boost::read_graphviz(dot_file, g, dp);
}
auto vd0 = *boost::vertices(g).first;
std::vector<int> distances(boost::num_vertices(g));
auto dist_pmap = boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, g));
auto vis = boost::make_bfs_visitor(
boost::record_distances(dist_pmap, boost::on_tree_edge()));
boost::breadth_first_search(g, vd0, visitor(vis));
for (auto vd : boost::make_iterator_range(boost::vertices(g)))
std::cout << "d[" << id_map[vd0] << ", " << id_map[vd] << "] = " << distances.at(vd) << "\n";
{
std::map<DiGraph::edge_descriptor, int> edge_labels;
auto label_map = boost::make_assoc_property_map(edge_labels);
for (auto ed : boost::make_iterator_range(boost::edges(g)))
label_map[ed] = distances.at(target(ed, g));
boost::dynamic_properties dp;
dp.property("node_id", id_map);
dp.property("label", label_map);
std::ofstream dot_file("output.dot");
boost::write_graphviz_dp(dot_file, g, dp);
}
}