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?
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
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:
#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