Find distances to vertices using BFS-CodePudding

using namespace boost;

typedef adjacency_list<setS, vecS, bidirectionalS,
no_property,
property<edge_weight_t, float>> Graph_type;

typedef graph_traits<Graph_type>::edge_iterator edge_iterator;


int main() {
    // create graph
    Graph_type g;
    add_edge(0,1,g);
    add_edge(1,2,g);
    add_edge(2,0,g);

    
    // output graph
    std::pair<edge_iterator, edge_iterator> ei = edges(g);
    for (edge_iterator edge_iter = ei.first; edge_iter != ei.second;   edge_iter)
        std::cout << source(*edge_iter, g) << " - " << target(*edge_iter, g) << "\n";

    // attempt to find shortest distance from vetex 0 to all other vertices
    breadth_first_search(g,0);
    return 0;
}

I am attempting to call breadth_first_search, starting from vertex 0, and obtain the shortest distance to all other vertices in the graph. How am I calling the function incorrectly? And what container is recommended to store the result?

CodePudding user response：

Modernizing the code first:

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

using Graph_type =
    boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
                          boost::no_property,
                          boost::property<boost::edge_weight_t, float>>;

int main() {
    // create graph
    Graph_type g;
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 0, g);

    // output graph
    for (auto e : boost::make_iterator_range(edges(g)))
        std::cout << e << "\n";

    // attempt to find shortest distance from vetex 0 to all other vertices
    breadth_first_search(g, 0);
}

Clang and GCC give different diagnostics, GCC's are most elaborate:

<source>: In function 'int main()':
<source>:24:32: error: no matching function for call to 'breadth_first_search(Graph_type&, int)'
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from <source>:2:
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:123:6: note: candidate: 'template<class VertexListGraph, class SourceIterator, class Buffer, class BFSVisitor, class ColorMap> void boost::breadth_first_search(const VertexListGraph&, SourceIterator, SourceIterator, Buffer&, BFSVisitor, ColorMap)'
  123 | void breadth_first_search(const VertexListGraph& g,
      |      ^~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:123:6: note:   template argument deduction/substitution failed:
<source>:24:32: note:   candidate expects 6 arguments, 2 provided
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from <source>:2:
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:141:6: note: candidate: 'template<class VertexListGraph, class Buffer, class BFSVisitor, class ColorMap> void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, Buffer&, BFSVisitor, ColorMap)'
  141 | void breadth_first_search(const VertexListGraph& g,
      |      ^~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:141:6: note:   template argument deduction/substitution failed:
<source>:24:32: note:   candidate expects 5 arguments, 2 provided
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from <source>:2:
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:328:6: note: candidate: 'template<class VertexListGraph, class P, class T, class R> void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&)'
  328 | void breadth_first_search(const VertexListGraph& g,
      |      ^~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:328:6: note:   template argument deduction/substitution failed:
<source>:24:32: note:   candidate expects 3 arguments, 2 provided
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
Compiler returned: 1

Indeed checking the documentation shows no overload that takes 2 arguments. You need at least a third, boost::named_parameters object

Let's stick in a stub:

breadth_first_search(g, 0, boost::no_named_parameters{});

Now it should tell us which params are missing, if any: Success!

The reason you might want to pass parameters is in case your graph doesn't have implicit property maps (like vertex_index_map) for mandatory arguments, or when you want to override the default for a UTIL/OUT, like visitor. In your case it is very likely that you want to override the it because otherwise you won't be able to access the answer to your question:

std::vector<size_t> distances(num_vertices(g));
auto recorder = record_distances(distances.data(), boost::on_tree_edge{});

breadth_first_search(g, 0, visitor(make_bfs_visitor(recorder)));

for (auto v : boost::make_iterator_range(vertices(g)))
    std::cout << "distance 0 .. " << v << ": " << distances.at(v) << "\n";

Prints Live On Compiler Explorer:

(0,1)
(1,2)
(2,0)
distance 0 .. 0: 0
distance 0 .. 1: 1
distance 0 .. 2: 2

BONUS/Caveats

Caution: your graph model "has" edge_weight (although your example never initializes it to non-zero values). If they are relevant, then BFS is not enough. For non-negative weights you should use Dijkstra, which happens to be a bit easier to use in my opinion:

Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>

using G = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
                                boost::no_property,
                                boost::property<boost::edge_weight_t, float>>;
using V = G::vertex_descriptor;

int main() {
    // create graph
    G g;
    add_edge(0, 1, 30, g);
    add_edge(1, 2, 43, g);
    add_edge(2, 0, 5, g);

    // output graph
    auto wmap = get(boost::edge_weight, g);
    for (auto e : boost::make_iterator_range(edges(g)))
        std::cout << e << " weight " << wmap[e] << "\n";

    // attempt to find shortest distance from vetex 0 to all other vertices
    auto s = vertex(0, g);
    assert(s == 0);

    std::vector<size_t> distances(num_vertices(g));
    boost::dijkstra_shortest_paths(g, s, boost::distance_map(distances.data()));

    for (auto v : boost::make_iterator_range(vertices(g)))
        std::cout << "distance 0 .. " << v << ": " << distances.at(v) << "\n";
}

Prints

(0,1) weight 30
(1,2) weight 43
(2,0) weight 5
distance 0 .. 0: 0
distance 0 .. 1: 30
distance 0 .. 2: 73