Search code examples
c++boost-graph

boost graph breadth first search predecessor compile error

why does this code

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
int main() {
        // set up syntax
       using namespace boost;
       typedef adjacency_list<vecS, vecS, bidirectionalS> graph_t;
       typedef graph_traits<graph_t>::vertex_descriptor v_t;

       // create simple test graph
       graph_t g( 3 );
       add_edge( 0, 1, g );
       add_edge( 1, 2, g );
       add_edge( 2, 3, g );

       // construct predecessors
       std::vector< v_t > predecessors(3);

       // search
       breadth_first_search(
            g,
            0,
            boost::visitor(
                boost::make_bfs_visitor(
                    boost::record_predecessors(predecessors.begin(),
                                               boost::on_tree_edge{}))));
        // display results
        for( v_t v : predecessors )
            std::cout << v;

return 0
}

gives compiler error

C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp||In instantiation of 'void boost::predecessor_recorder<PredecessorMap, Tag>::operator()(Edge, const Graph&) [with Edge = boost::detail::edge_desc_impl<boost::bidirectional_tag, long long unsigned int>; Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; PredecessorMap = __gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >; Tag = boost::on_tree_edge]':|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|105|required from 'void boost::detail::invoke_dispatch(Visitor&, T, Graph&, mpl_::true_) [with Visitor = boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >, boost::on_tree_edge>; T = boost::detail::edge_desc_impl<boost::bidirectional_tag, long long unsigned int>; Graph = const boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; mpl_::true_ = mpl_::bool_<true>]'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|126|required from 'void boost::invoke_visitors(Visitor&, T, Graph&, Tag) [with Visitor = boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >, boost::on_tree_edge>; T = boost::detail::edge_desc_impl<boost::bidirectional_tag, long long unsigned int>; Graph = const boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; Tag = boost::on_tree_edge]'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|183|required from 'boost::graph::bfs_visitor_event_not_overridden boost::bfs_visitor<Visitors>::tree_edge(Edge, Graph&) [with Edge = boost::detail::edge_desc_impl<boost::bidirectional_tag, long long unsigned int>; Graph = const boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; Visitors = boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >, boost::on_tree_edge>]'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|83|required from 'void boost::breadth_first_visit(const IncidenceGraph&, SourceIterator, SourceIterator, Buffer&, BFSVisitor, ColorMap) [with IncidenceGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; Buffer = boost::queue<long long unsigned int, std::deque<long long unsigned int, std::allocator<long long unsigned int> > >; BFSVisitor = boost::bfs_visitor<boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >, boost|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|124|required from 'void boost::breadth_first_search(const VertexListGraph&, SourceIterator, SourceIterator, Buffer&, BFSVisitor, ColorMap) [with VertexListGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; SourceIterator = long long unsigned int*; Buffer = boost::queue<long long unsigned int, std::deque<long long unsigned int, std::allocator<long long unsigned int> > >; BFSVisitor = boost::bfs_visitor<boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*,|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|135|required from 'void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, Buffer&, BFSVisitor, ColorMap) [with VertexListGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; Buffer = boost::queue<long long unsigned int, std::deque<long long unsigned int, std::allocator<long long unsigned int> > >; BFSVisitor = boost::bfs_visitor<boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long |
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|258|required from 'void boost::detail::bfs_helper(VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, ColorMap, BFSVisitor, const boost::bgl_named_params<P, T, R>&, mpl_::false_) [with VertexListGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>; ColorMap = boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, long long unsigned int> >; BFSVisitor = boost::bfs_visitor<boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long un|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|313|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::vecS, boost::vecS, boost::bidirectionalS>; P = boost::bfs_visitor<boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >, boost::on_tree_edge> >; T = boost::graph_|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\breadth_first_search.hpp|344|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::vecS, boost::vecS, boost::bidirectionalS>; P = boost::bfs_visitor<boost::predecessor_recorder<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >, boost::on_tree_edge> >; T = boost::graph_visitor_t; R = boost::no_property; typename boost::graph|
C:\Users\James\code\maze\src\cMaze.cpp|440|required from here|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|140|error: no matching function for call to 'put(__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >&, long long unsigned int, long long unsigned int)'|
C:\Users\James\code\boost\boost_1_70_0\boost\property_map\property_map.hpp|195|note: candidate: 'template<class K, class V> void boost::put(const boost::writable_property_map_archetype<K, V>&, const typename boost::writable_property_map_archetype<K, V>::key_type&, const typename boost::writable_property_map_archetype<K, V>::value_type&)'|
C:\Users\James\code\boost\boost_1_70_0\boost\property_map\property_map.hpp|195|note:   template argument deduction/substitution failed:|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|140|note:   '__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >' is not derived from 'const boost::writable_property_map_archetype<K, V>'|
C:\Users\James\code\boost\boost_1_70_0\boost\property_map\property_map.hpp|309|note: candidate: 'template<class PropertyMap, class Reference, class K, class V> void boost::put(const boost::put_get_helper<Reference, PropertyMap>&, K, const V&)'|
C:\Users\James\code\boost\boost_1_70_0\boost\property_map\property_map.hpp|309|note:   template argument deduction/substitution failed:|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|140|note:   '__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >' is not derived from 'const boost::put_get_helper<Reference, PropertyMap>'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\property_maps\null_property_map.hpp|32|note: candidate: 'template<class K, class V> void boost::put(boost::null_property_map<K, V>&, const K&, const V&)'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\property_maps\null_property_map.hpp|32|note:   template argument deduction/substitution failed:|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|140|note:   '__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >' is not derived from 'boost::null_property_map<K, V>'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\detail\adjacency_list.hpp|1765|note: candidate: 'template<class Config, class Base, class Property, class Key, class Value> void boost::put(Property, boost::adj_list_helper<Config, Base>&, const Key&, const Value&)'|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\detail\adjacency_list.hpp|1765|note:   template argument deduction/substitution failed:|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|140|note:   mismatched types 'boost::adj_list_helper<Config, Base>' and 'long long unsigned int'|
C:\Users\James\code\boost\boost_1_70_0\boost\property_map\property_map.hpp|126|note: candidate: 'template<class T, class V> void put(T*, std::ptrdiff_t, const V&)'|
C:\Users\James\code\boost\boost_1_70_0\boost\property_map\property_map.hpp|126|note:   template argument deduction/substitution failed:|
C:\Users\James\code\boost\boost_1_70_0\boost\graph\visitors.hpp|140|note:   mismatched types 'T*' and '__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int> >'|
||=== Build failed: 1 error(s), 15 warning(s) (0 minute(s), 5 second(s)) ===|
Solution

  • A bare iterator doesn't qualify as a property map. If your iterator points to contiguous memory, a raw pointer WOULD be ok, though relatively unsafe because no concept or bounds checking occurs:

    auto vis = boost::make_bfs_visitor(
    boost::record_predecessors(&*predecessors.begin(), boost::on_tree_edge{}));

breadth_first_search(g, 0, boost::visitor(vis));

    If you have of course, favour predecessors.data(). However, I'd say favour the safe options below

    However you'd usually prefer to use iterator-property-maps:

    auto pmap = make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, g));
auto vis = make_bfs_visitor(
    boost::record_predecessors(pmap, boost::on_tree_edge{}));

    Which then offers the option of bounds-checking:

    auto pmap = make_safe_iterator_property_map(
    predecessors.begin(),
    predecessors.size(),
    get(boost::vertex_index, g));
auto vis = make_bfs_visitor(
    boost::record_predecessors(pmap, boost::on_tree_edge{}));

    Fixed Code

    Note that there WAS a bounds-error due to vertex 3 being out of range. This is why you want checked iterators.

    This was also fixed below, by increasing the constructor argument AND using boost::num_vertices instead of hardcoding the number later.

    Live On Coliru

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

int main() {
    // set up syntax
    using namespace boost;
    using graph_t = adjacency_list<vecS, vecS, bidirectionalS>;
    using v_t = graph_traits<graph_t>::vertex_descriptor;

    // create simple test graph
    graph_t g(4);
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 3, g);

    // construct predecessors
    std::vector<v_t> predecessors(num_vertices(g));

    // search
    auto do_it = [&](auto pmap) {
        std::cout << "\nRunning with " << boost::core::demangle(typeid(pmap).name()) << "\n";
        auto vis = make_bfs_visitor(
            boost::record_predecessors(pmap, boost::on_tree_edge{}));

        breadth_first_search(g, 0, boost::visitor(vis));

        // display results
        for (v_t v : predecessors)
            std::cout << v << " ";
    };

    do_it(&*predecessors.begin());

    do_it(make_iterator_property_map(
        predecessors.begin(),
        get(boost::vertex_index, g)));

    do_it(make_safe_iterator_property_map(
        predecessors.begin(),
        predecessors.size(),
        get(boost::vertex_index, g)));
}

    Prints

    Running with unsigned long*
0 0 1 2 
Running with boost::iterator_property_map<__gnu_cxx::__normal_iterator<unsigned long*, std::vector<unsigned long, std::allocator<unsigned long> > >, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long>, unsigned long, unsigned long&>
0 0 1 2 
Running with boost::safe_iterator_property_map<__gnu_cxx::__normal_iterator<unsigned long*, std::vector<unsigned long, std::allocator<unsigned long> > >, boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long>, unsigned long, unsigned long&>
0 0 1 2