Reputation: 13
I'm learning how to use Boost-graph library for a university project. I have a graph where I need to add and remove vertices, so I declared my adjacency list with listS as vertex list. I have a big problem with the call of depth_first_search() function: because of listS, I need to provide a Indexes Property Map, but I don't understand how I need to procedes. Here's the code:
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/depth_first_search.hpp>
struct VertexProperties {
int value;
};
typedef boost::adjacency_list<boost::vecS, // OutEdgeList
boost::listS, // VertexList
boost::bidirectionalS, // Directed
VertexProperties // VertexProperties
>
MyGraph;
typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;
typedef boost::graph_traits<MyGraph>::edge_descriptor MyEdge;
class dfs_visitor : public boost::default_dfs_visitor {
public:
dfs_visitor();
dfs_visitor(const dfs_visitor& other);
void initialize_vertex(MyVertex s, MyGraph g);
void start_vertex(MyVertex s, MyGraph g);
void discover_vertex(MyVertex s, MyGraph g);
void finish_vertex(MyVertex s, MyGraph g);
void examine_edge(MyEdge e, MyGraph g);
void tree_edge(MyEdge e, MyGraph g);
void back_edge(MyEdge e, MyGraph g);
void forward_or_cross_edge(MyEdge e, MyGraph g);
void finish_edge(MyEdge e, MyGraph g);
};
dfs_visitor::dfs_visitor() {}
dfs_visitor::dfs_visitor(const dfs_visitor& other) {}
void dfs_visitor::initialize_vertex(MyVertex s, MyGraph g){
std::cout << "Initialize: " << g[s].value << std::endl;
}
void dfs_visitor::start_vertex(MyVertex s, MyGraph g) {
std::cout << "Start: " << g[s].value << std::endl;
}
void dfs_visitor::discover_vertex(MyVertex s, MyGraph g) {
std::cout << "Discover: " << g[s].value << std::endl;
}
void dfs_visitor::finish_vertex(MyVertex s, MyGraph g) {
std::cout << "Finished: " << g[s].value << std::endl;
}
void dfs_visitor::examine_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::tree_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::back_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::forward_or_cross_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::finish_edge(MyEdge e, MyGraph g) {}
int main(){
MyGraph g{};
for(int i = 0; i < 10; i++) {
MyVertex v = boost::add_vertex(g);
g[v].value = i;
}
MyGraph::vertex_iterator v, v_end;
std::tie(v, v_end) = boost::vertices(g);
auto u = v;
u++;
while(v != v_end && u != v_end) {
boost::add_edge(*u, *v, g);
u++;
v++;
}
/* INDEX MAP CREATION*/
typedef std::map<MyVertex, size_t> MyIndexMap;
MyIndexMap i_map;
auto ipmap = boost::make_assoc_property_map(i_map);
std::tie(v, v_end) = boost::vertices(g);
while(v != v_end) {
i_map[*v] = i_map.size();
v++;
}
/* COLOR MAP CREATION */
typedef std::map<size_t, boost::default_color_type> ColorMap;
ColorMap c_map;
auto cpmap = boost::make_assoc_property_map(c_map);
std::tie(v, v_end) = boost::vertices(g);
while(v != v_end) {
c_map[ipmap[*v]] = boost::color_traits<boost::default_color_type>::white();
v++;
}
dfs_visitor vis{};
boost::depth_first_search(g,
boost::visitor(vis)),
boost::color_map(cpmap);
boost::vertex_index_map(ipmap);
}
When I'm going to compile this, this is the output:
In file included from /usr/include/boost/graph/adjacency_list.hpp:223,
from test.cpp:2:
/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::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, VertexProperties>’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2618:12: required from ‘struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, VertexProperties>’
/usr/include/boost/graph/detail/adjacency_list.hpp:2755:12: required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, VertexProperties, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:201:12: required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:212:10: required from ‘struct boost::property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, boost::vertex_index_t, void>’
/usr/include/boost/graph/named_function_params.hpp:416:69: [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
/usr/include/boost/graph/named_function_params.hpp:605:41: required from ‘struct boost::detail::map_maker<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>, boost::graph::keywords::tag::color_map, boost::default_color_type>’
/usr/include/boost/graph/named_function_params.hpp:621:7: required by substitution of ‘template<class Graph, class ArgPack> typename boost::detail::map_maker<Graph, ArgPack, boost::graph::keywords::tag::color_map, boost::default_color_type>::map_type boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::color_map, boost::default_color_type>::operator()<Graph, ArgPack>(const Graph&, const ArgPack&) const [with Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>]’
/usr/include/boost/graph/depth_first_search.hpp:337:80: required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>]’
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; P = dfs_visitor; T = boost::graph_visitor_t; R = boost::no_property; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
test.cpp:100:50: required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2548:29: error: forming reference to void
2548 | typedef value_type& reference;
| ^~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2549:35: error: forming reference to void
2549 | typedef const value_type& const_reference;
| ^~~~~~~~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2552:47: error: forming reference to void
2552 | <Graph, value_type, reference, Tag> type;
| ^~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2554:53: error: forming reference to void
2554 | <Graph, value_type, const_reference, Tag> const_type;
| ^~~~~~~~~~
In file included from /usr/include/boost/graph/graph_utility.hpp:24,
from test.cpp:3:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>]’:
/usr/include/boost/graph/depth_first_search.hpp:342:5: required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3: required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; P = dfs_visitor; T = boost::graph_visitor_t; R = boost::no_property; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
test.cpp:100:50: required from here
/usr/include/boost/graph/depth_first_search.hpp:337:80: error: no match for call to ‘(const boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::color_map, boost::default_color_type>) (const boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>&, const boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>&)’
337 | boost::detail::make_color_map_from_arg_pack(g, arg_pack),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/boost/graph/depth_first_search.hpp:21,
from /usr/include/boost/graph/graph_utility.hpp:24,
from test.cpp:3:
/usr/include/boost/graph/named_function_params.hpp:621:7: note: candidate: ‘template<class Graph, class ArgPack> typename boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type boost::detail::make_property_map_from_arg_pack_gen<MapTag, ValueType>::operator()(const Graph&, const ArgPack&) const [with Graph = Graph; ArgPack = ArgPack; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type]’
621 | operator()(const Graph& g, const ArgPack& ap) const {
| ^~~~~~~~
/usr/include/boost/graph/named_function_params.hpp:621:7: note: substitution of deduced template arguments resulted in errors seen above
I think this is a kind of template error. Can someone explain me where is the mistake?
Upvotes: 1
Views: 541
Reputation: 394054
The named parameters are not given correctly. They use Fluent Syntax:
boost::depth_first_search(g,
boost::visitor(vis)
.vertex_index_map(ipmap)
.color_map(cpmap));
Now, you can simplify the rest of the code significantly.
struct
const
using
) instead of legacy typedef
VertexProperties
with add_vertex
at onceboost::make_iterator_range
)default_color_type
, std::vector
or std::map
would already do thatEverything at once: Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
struct VertexProperties {
int value;
};
using MyGraph = boost::adjacency_list<boost::vecS, // OutEdgeList
boost::listS, // VertexList
boost::bidirectionalS, // Directed
VertexProperties // VertexProperties
>;
using MyVertex = boost::graph_traits<MyGraph>::vertex_descriptor;
using MyEdge = boost::graph_traits<MyGraph>::edge_descriptor;
struct dfs_visitor : boost::default_dfs_visitor {
void initialize_vertex(MyVertex s, MyGraph const& g) const { std::cout << "Initialize: " << g[s].value << std::endl; }
void start_vertex(MyVertex s, MyGraph const& g) const { std::cout << "Start: " << g[s].value << std::endl; }
void discover_vertex(MyVertex s, MyGraph const& g) const { std::cout << "Discover: " << g[s].value << std::endl; }
void finish_vertex(MyVertex s, MyGraph const& g) const { std::cout << "Finished: " << g[s].value << std::endl; }
};
int main() {
MyGraph g{};
for (int i = 0; i < 10; i++) {
add_vertex(VertexProperties{i}, g);
}
{
boost::optional<MyVertex> prev;
for (auto v : boost::make_iterator_range(vertices(g))) {
if (prev)
add_edge(v, *prev, g);
prev = v;
}
}
/* INDEX MAP CREATION*/
std::map<MyVertex, size_t> i_map;
for (auto v : boost::make_iterator_range(vertices(g))) {
i_map.emplace(v, i_map.size());
}
auto ipmap = boost::make_assoc_property_map(i_map);
/* COLOR MAP CREATION */
std::vector<boost::default_color_type> c_map(num_vertices(g));
auto cpmap = boost::make_iterator_property_map(c_map.begin(), ipmap);
dfs_visitor vis{};
boost::depth_first_search(g,
boost::visitor(vis)
.vertex_index_map(ipmap)
.color_map(cpmap));
}
Prints
Initialize: 0
Initialize: 1
Initialize: 2
Initialize: 3
Initialize: 4
Initialize: 5
Initialize: 6
Initialize: 7
Initialize: 8
Initialize: 9
Start: 0
Discover: 0
Finished: 0
Start: 1
Discover: 1
Finished: 1
Start: 2
Discover: 2
Finished: 2
Start: 3
Discover: 3
Finished: 3
Start: 4
Discover: 4
Finished: 4
Start: 5
Discover: 5
Finished: 5
Start: 6
Discover: 6
Finished: 6
Start: 7
Discover: 7
Finished: 7
Start: 8
Discover: 8
Finished: 8
Start: 9
Discover: 9
Finished: 9
Upvotes: 2