Search code examples
boostboost-graph

How does distance_recorder work in boost graph library?

I am learning breath first search algorithm. The graph is a complete binary tree. I want to print the distance of each node to the root. For example, d[0, 0] = 0, d[0, 1] = 1, d[0, 2] = 1, d[0, 3] = 2, d[0, 7] = 3.

enter image description here

The dot file is here.

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

The program is pretty straightforward, make_bfs_visitor take a distance_recorder to record the distance between tree edges.

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

The output is not what I expected.

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

What am I doing wrong here?

Solution

  • How does it work?

    record_distances is a factory for an event visitor. make_bfs_visitor ties that into an (otherwise default) BFS visitor model.

    I'm guessing this wasn't your question. It's not clear what you do expect, as the output doesn't look at all informative to me. Perhaps you want to display it in a more useful format:

    for (auto vd : boost::make_iterator_range(boost::vertices(g)))
    std::cout << "d[" << vd0 << ", " << vd << "] = " << distances.at(vd) << "\n";

    Now the output is:

    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

    Now, what gives? Because in the heading of your question you suggest you expect:

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

    There's a clear mismatch! d[0,7] = 1 doesn't match the "more logical" d[0,7] = 3. Yet, you didn't do anything /wrong/ and the distance calculation isn't wrong.

    There's a subtle observer error! You think vertex descriptor 7 refers to the vertex that you showed with that number in the input. However, if you print the graph that read_graphviz reads:

    enter image description here

    AHA! Something went wrong, or differently than you expected. In fact, if you removed the "magic bit" about ignore_other_properties that you didn't actually know the meaning of:

    boost::dynamic_properties dp; // {boost::ignore_other_properties};

    You'd have been told about it:

    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.

    Indeed, you told Boost to read the vertices, but to ignore the vertex id from the Dot file. So, the result is a guaranteed isomorphism of the graph in your input, but the IDs are in unspecified/implementation-defined order.

    Fixing It: read a node id

    Let's keep with adjacency_list<> pure and simple, so lets create an external id map:

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

    Now, when we write the graph back using the original node ids:

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

    We get our original picture back. Phew.

    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

    Use the node-id in the report

    From here it's relatively easy to fix the reporting:

    for (auto vd : boost::make_iterator_range(boost::vertices(g)))
    std::cout << "d[" << id_map[vd0] << ", " << id_map[vd] << "] = " << distances.at(vd) << "\n";

    Prints:

    d[0, 0] = 0
d[0, 1] = 1
...
d[0, 6] = 2
d[0, 7] = 3
...

    Yay! Sanity restored.

    Bonus: Visualizing the distances

    Let's add a label to each edge displaying the distance from root to its target vertex:

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

    Now, we have this beautiful, reassuring output:

    enter image description here

    Full Demo Listing

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