distance_recorder 如何在 boost 图形库中工作？

Question

我正在学习呼吸优先搜索算法。该图是一个完全二叉树。我想打印每个节点到根的距离。例如，d[0, 0] = 0, d[0, 1] = 1, d[0, 2] = 1, d[0, 3] = 2, d[0, 7] = 3.

点文件在这里。

digraph G {
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
10;
11;
12;
13;
14;
0->1 ;
0->2 ;
1->3 ;
1->4 ;
2->5 ;
2->6 ;
3->7 ;
3->8 ;
4->9 ;
4->10 ;
5->11 ;
5->12 ;
6->13 ;
6->14 ;
}

程序很简单，make_bfs_visitor取一个distance_recorder记录树边的距离。

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
    using DiGraph = boost::adjacency_list<>;
    DiGraph g;
    std::ifstream dot_file("graph.dot");
    boost::dynamic_properties dp{ boost::ignore_other_properties };
    boost::read_graphviz(dot_file, g, dp);

    auto vd0 = *boost::vertices(g).first;

    using vertices_size_type = boost::graph_traits<DiGraph>::vertices_size_type;

    std::vector<vertices_size_type> 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 d : distances)
        std::cout << d << ' ';
    std::cout << '\n';

    for (auto d : boost::make_iterator_range(boost::vertices(g)))
      std::cout << d << ' ';
    std::cout << '\n';
    return 0;
}

输出不是我预期的。

0 1 3 3 3 3 3 1 2 2 2 2 3 3 3 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

我做错了什么？

Answer 1

它是如何工作的？

record_distances 是事件访问者的工厂。 make_bfs_visitor 将其与（否则默认）BFS 访问者模型联系起来。

我猜这不是你的问题。不清楚您 do 期望什么，因为输出对我来说并没有提供任何信息。也许您想以更有用的格式显示它：

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

现在，给出了什么？因为在你的问题标题中你建议你期望：

For example, d[0, 0] = 0, d[0, 1] = 1, d[0, 2] = 1, d[0, 3] = 2, d[0, 7] = 3.

明显不匹配！ d[0,7] = 1 与 "more logical" d[0,7] = 3 不匹配。然而，你什么都没做/错/而且距离计算没有错。

有一个微妙的观察者错误！您 think 顶点描述符 7 指的是您在输入中用该数字显示的顶点。但是，如果打印 read_graphviz 显示的图形：

啊哈！出了点问题，或者与您预期的不同。事实上，如果你删除了关于 ignore_other_properties 的 "magic bit" 你实际上并不知道的含义：

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 文件中的顶点 ID。因此，结果是输入中图形的同构保证，但 ID 按 unspecified/implementation-defined 顺序排列。

修复：读取节点 ID

让我们保持 adjacency_list<> 纯粹和简单，所以让我们创建一个外部 ID 映射：

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

现在，当我们使用原始节点 ID 写回图时：

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

我们取回了原始图片。呸

Note For recording the distances we still keep using the "technical" vertex_descriptor as the implicit vertex-id. This is because that makes it easier to use the vector<> as the distance-map.

Alternatively, we can use the "user-friendly" id_map and store in an associative LvaluePropertMap

在报告中使用node-id

从这里修复报告相对容易：

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

distance_recorder 如何在 boost 图形库中工作？

How does distance_recorder work in boost graph library?

boost

boost-graph

修复：读取节点 ID

在报告中使用node-id

奖励：可视化距离

完整的演示清单