I'm trying to do something as simple as getting the distances from one node to all the others, but I'm not getting it right about how to use the breadth_first_search with my graph... I'm getting a lot of compilation errors and I don't undestand why.

I even tried the solutions proposed in other questions, but they didn't work for me

Can some one help me?

Definitions:

class Position {
   public:
    Position() : x(0), y(0) {}
    Position(int a, int b) : x(a), y(b) {}

    // operator overrides
    
    int x, y;
};

struct Group {
    Group(Position pos, short c, short s) : position(pos), color(c), size(s) {}
    Group() {}
    Position position;
    short color;
    short size;
};

inline bool operator==(const Group& g1, const Group& g2) {
    return g1.position == g2.position;
};
inline bool operator!=(const Group& g1, const Group& g2) {
    return g1.position != g2.position;
};

typedef boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property> Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;

Minimal example:

int main() {
    Graph graph;

    // build graph

    VertexDescriptor v = *boost::vertices(graph).first;
    std::vector<int> distances(boost::num_vertices(graph));

    boost::breadth_first_search(graph, v, boost::visitor( boost::make_bfs_visitor( boost::record_distances(distances.begin(), boost::on_tree_edge{}))));

    return 0;
}

Compilation error:

In file included from /usr/include/boost/graph/adjacency_list.hpp:223,
                 from src/../include/graph.hpp:4,
                 from src/main.cpp:3:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::adj_list_any_vertex_pa::bind_<boost::vertex_index_t, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, Group>’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2617:12:   required from ‘struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, Group>’
/usr/include/boost/graph/detail/adjacency_list.hpp:2754:12:   required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, Group, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:201:12:   required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:212:10:   required from ‘struct boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void>’
/usr/include/boost/mpl/eval_if.hpp:38:31:   recursively required from ‘struct boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >, boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >’
/usr/include/boost/mpl/eval_if.hpp:38:31:   required from ‘struct boost::mpl::eval_if<boost::is_same<boost::param_not_found, boost::param_not_found>, boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >, boost::property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::vertex_index_t, void> >, boost::mpl::identity<boost::param_not_found> >’
/usr/include/boost/graph/named_function_params.hpp:273:12:   required from ‘struct boost::detail::choose_impl_result<mpl_::bool_<true>, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>, boost::param_not_found, boost::vertex_index_t>’
/usr/include/boost/graph/named_function_params.hpp:309:3:   required by substitution of ‘template<class Param, class Graph, class PropertyTag> typename boost::detail::choose_impl_result<mpl_::bool_<true>, Graph, Param, PropertyTag>::type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag) [with Param = boost::param_not_found; Graph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; PropertyTag = boost::vertex_index_t]’
/usr/include/boost/graph/breadth_first_search.hpp:315:30:   required from ‘static void boost::detail::bfs_dispatch<boost::param_not_found>::apply(VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&, boost::param_not_found) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’
/usr/include/boost/graph/breadth_first_search.hpp:343:35:   required from ‘void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’
src/main.cpp:41:151:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2547:29: error: forming reference to void
 2547 |         typedef value_type& reference;
      |                             ^~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2548:35: error: forming reference to void
 2548 |         typedef const value_type& const_reference;
      |                                   ^~~~~~~~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2551:47: error: forming reference to void
 2551 |           <Graph, value_type, reference, Tag> type;
      |                                               ^~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2553:53: error: forming reference to void
 2553 |           <Graph, value_type, const_reference, Tag> const_type;
      |                                                     ^~~~~~~~~~
In file included from src/main.cpp:7:
/usr/include/boost/graph/breadth_first_search.hpp: In instantiation of ‘static void boost::detail::bfs_dispatch<boost::param_not_found>::apply(VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&, boost::param_not_found) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’:
/usr/include/boost/graph/breadth_first_search.hpp:343:35:   required from ‘void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>; P = boost::bfs_visitor<boost::distance_recorder<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph_traits<Graph>::vertex_descriptor = void*]’
src/main.cpp:41:151:   required from here
/usr/include/boost/graph/breadth_first_search.hpp:315:30: error: no matching function for call to ‘choose_const_pmap(const type&, boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Group, boost::no_property>&, boost::vertex_index_t)’
  315 |             choose_const_pmap(get_param(params, vertex_index),
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  316 |                               g, vertex_index)),
      |                               ~~~~~~~~~~~~~~~~
In file included from /usr/include/boost/graph/breadth_first_search.hpp:23,
                 from src/main.cpp:7:
/usr/include/boost/graph/named_function_params.hpp:309:3: note: candidate: ‘template<class Param, class Graph, class PropertyTag> typename boost::detail::choose_impl_result<mpl_::bool_<true>, Graph, Param, PropertyTag>::type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag)’
  309 |   choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag)
      |   ^~~~~~~~~~~~~~~~~
/usr/include/boost/graph/named_function_params.hpp:309:3: note:   substitution of deduced template arguments resulted in errors seen above

CodePudding user response：

Two problems

Problem 1: Vertex Index

The documented requirements for breadth_first_search include a vertex index. Since you use a node-based container selector (listS) there is no implicit index, so you should provide one:

Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property

Here's a simplified example showing that vecS works:

Live On Compiler Explorer

using Graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Group>;
using V = Graph::vertex_descriptor;

int main() {
    Graph graph(10);

    V v = vertex(0, graph);

    auto vis = boost::default_bfs_visitor{};

    breadth_first_search(graph, v, visitor(vis));
}

Now changing vecS to listS:

using Graph =
    boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, Group>;

doesn't compile (Live), as expected. So we could supply an external, temporary index: Live

std::map<V, int> tmp_index;
for (auto v : boost::make_iterator_range(vertices(graph)))
    tmp_index[v] = tmp_index.size();

auto index_map = boost::make_assoc_property_map(tmp_index);
breadth_first_search(graph, v, visitor(vis).vertex_index_map(index_map));

It still compiles even with unique edges (setS, Live).

Now, let's record distances.

Problem 2: Distance Map Keys

The keys of the distance map are required to be the vertex descriptor.¹

You can tell because the compilation error indicates that the distance_recorder tries to call:

put(m_distance, v, get(m_distance, u)   1);

where v and u are vertex descriptors (and m_distance is the distance propertymap you supplied).

Two solutions

You can use an associative map again: Live

 std::map<V, int>  distances;
 auto vis = make_bfs_visitor(record_distances(
     boost::make_assoc_property_map(distances), boost::on_tree_edge{}));

You can fix the propertymap by projecting through the temporary vertex index: Live

 auto index_map = boost::make_assoc_property_map(tmp_index);
 auto dist_map  = make_safe_iterator_property_map(dist.begin(),
                                                 dist.size(), index_map);
 auto vis =
     make_bfs_visitor(record_distances(dist_map, boost::on_tree_edge{}));

¹ Actually it looks like there was a copy paste error because that page incorrectly claims the value type needs to be the vertex-descriptor as well. That is (obviously?) copy-pasted from the docs for predecessor_recorder...