I am trying to use depth first search starting from a particular vertex. For that I need to supply a visitor and a color map.
If I don't supply a starting vertex then I don't need to supply a color map either and everything works fine. However, I didn't find a signature that would accept a starting vertex without requiring a color map.
I use C++ 17 (Embarcadero C++ Builder) Here is the code:
#include <stdio.h>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/topological_sort.hpp>
struct EdgeProps
{
int value;
};
struct VertexProps
{
int value;
};
struct cycle_detector : public boost::default_dfs_visitor
{
cycle_detector( bool& has_cycle)
: _has_cycle(has_cycle) { }
template <class Edge, class Graph>
void back_edge(Edge, Graph&) {
_has_cycle = true;
}
protected:
bool& _has_cycle;
};
int _tmain(int argc, _TCHAR* argv[])
{
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps> Graph;
Graph g;
auto v0 = boost::add_vertex(g);
auto v1 = boost::add_vertex(g);
auto v2 = boost::add_vertex(g);
auto v3 = boost::add_vertex(g);
auto v4 = boost::add_vertex(g);
boost::add_edge(v0, v1, g);
boost::add_edge(v0, v2, g);
boost::add_edge(v0, v3, g);
boost::add_edge(v2, v4, g);
boost::add_edge(v3, v4, g);
bool has_cycle = false;
std::vector<boost::default_color_type> colors(boost::num_vertices(g));
boost::iterator_property_map color_map(colors.begin(), boost::get(boost::vertex_index, g));
boost::depth_first_search(g, boost::visitor(cycle_detector(has_cycle)), color_map, v0);
return 0;
}
I get a barrage of error message complaining about the visitor. Yet if I dont' supply a map and a a starting vertex then everything is fine.
Here are the messages:
bcc32c command line for "DFS.cpp"
c:\program files (x86)\embarcadero\studio\21.0\bin\bcc32c.exe -cc1 -D _DEBUG -output-dir .\Win32\Debug -I D:\Study\Trees -I D:\Study\Trees -isystem
"c:\program files (x86)\embarcadero\studio\21.0\include" -isystem "c:\program files (x86)\embarcadero\studio\21.0\include\dinkumware64" -isystem
"c:\program files (x86)\embarcadero\studio\21.0\include\windows\crtl" -isystem "c:\program files (x86)\embarcadero\studio\21.0\include\windows\sdk"
-isystem "c:\program files (x86)\embarcadero\studio\21.0\include\windows\rtl" -isystem "c:\program files
(x86)\embarcadero\studio\21.0\include\windows\vcl" -isystem "c:\program files (x86)\embarcadero\studio\21.0\include\windows\fmx" -isystem
C:\Users\Public\Documents\Embarcadero\Studio\21.0\hpp\Win32 -isystem "c:\program files (x86)\embarcadero\studio\21.0\include\boost_1_70" -isystem
"D:\Icrfs\Components\TeeChart 2020.30\Compiled\Delphi27.win32\Include" -isystem "D:\ICRFS\Components\Orpheus Sydney\Win32\hpp" -isystem "c:\program
files (x86)\embarcadero\studio\21.0\include\boost_1_70\\BOOST" -isystem D:\ICRFS\Components\SimpleGraph\hpp -isystem
C:\Users\Public\Documents\Embarcadero\Studio\21.0\hpp\Win32 -debug-info-kind=standalone -fborland-extensions -nobuiltininc -nostdsysteminc -triple
i686-pc-windows-omf -emit-obj -mrelocation-model static -masm-verbose -ffunction-sections -fexceptions -fcxx-exceptions -fseh -mstack-alignment=16
-fno-spell-checking -fno-use-cxa-atexit -fno-threadsafe-statics -main-file-name DFS.cpp -x c++ -std=c++17 -O0 -fmath-errno -tC -tM -o
.\Win32\Debug\DFS.obj --auto-dependency-output -MT .\Win32\Debug\DFS.obj -include-pch .\Win32\Debug\TreesPCH1.pch DFS.cpp
[bcc32c Error] depth_first_search.hpp(234): no member named 'initialize_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
DFS.cpp(62): in instantiation of function template specialization 'boost::depth_first_search<boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps, boost::no_property, boost::listS>, boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>, boost::iterator_property_map<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<boost::default_color_type> > >, boost::vec_adj_list_vertex_id_map<VertexProps, unsigned int>, boost::default_color_type, boost::default_color_type &> >' requested here
[bcc32c Error] depth_first_search.hpp(237): no member named 'start_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(245): no member named 'start_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(39): no member named 'initialize_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
general.hpp(47): in instantiation of member function 'boost::DFSVisitorConcept<boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>, boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps, boost::no_property, boost::listS> >::constraints' requested here
depth_first_search.hpp(227): in instantiation of member function 'boost::concepts::constraint<boost::DFSVisitorConcept<boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>, boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps, boost::no_property, boost::listS> > >::failed' requested here
DFS.cpp(62): in instantiation of function template specialization 'boost::depth_first_search<boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps, boost::no_property, boost::listS>, boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>, boost::iterator_property_map<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<boost::default_color_type> > >, boost::vec_adj_list_vertex_id_map<VertexProps, unsigned int>, boost::default_color_type, boost::default_color_type &> >' requested here
[bcc32c Error] depth_first_search.hpp(40): no member named 'start_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(41): no member named 'discover_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(42): no member named 'examine_edge' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(43): no member named 'tree_edge' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(44): no member named 'back_edge' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(45): no member named 'forward_or_cross_edge' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(47): no member named 'finish_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(134): no member named 'discover_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
depth_first_search.hpp(238): in instantiation of function template specialization 'boost::detail::depth_first_visit_impl<boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps, boost::no_property, boost::listS>, boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>, boost::iterator_property_map<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<boost::default_color_type> > >, boost::vec_adj_list_vertex_id_map<VertexProps, unsigned int>, boost::default_color_type, boost::default_color_type &>, boost::detail::nontruth2>' requested here
DFS.cpp(62): in instantiation of function template specialization 'boost::depth_first_search<boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProps, EdgeProps, boost::no_property, boost::listS>, boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>, boost::iterator_property_map<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<boost::default_color_type> > >, boost::vec_adj_list_vertex_id_map<VertexProps, unsigned int>, boost::default_color_type, boost::default_color_type &> >' requested here
[bcc32c Error] depth_first_search.hpp(155): no member named 'examine_edge' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(158): no member named 'tree_edge' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(163): no member named 'discover_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
[bcc32c Error] depth_first_search.hpp(179): no member named 'finish_vertex' in 'boost::bgl_named_params<cycle_detector, boost::graph_visitor_t, boost::no_property>'
Failed
Elapsed time: 00:00:02.8
Any help would be much appreciated
By wrapping your visitor in boost::visitor you are confusing with the named-parameter overload. Just pass the visitor:
boost::depth_first_search(g, cycle_detector{has_cycle}, color_map, v0);
Or pass all arguments as named paramaeters:
boost::depth_first_search(g,
boost::visitor(cycle_detector{has_cycle})
.color_map(color_map)
.root_vertex(v0));
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/topological_sort.hpp>
#include <stdio.h>
#ifndef IHAVEASANECOMPILER_PLATFORM
#define _tmain main
#define _TCHAR char
#endif
struct EdgeProps {
int value;
};
struct VertexProps {
int value;
};
struct cycle_detector : boost::default_dfs_visitor {
cycle_detector(bool& has_cycle) : _has_cycle(has_cycle) {}
template <class Edge, class Graph> void back_edge(Edge, Graph&) {
_has_cycle = true;
}
bool& _has_cycle;
};
int _tmain() {
typedef boost::adjacency_list<boost::setS, boost::vecS,
boost::bidirectionalS, VertexProps, EdgeProps>
Graph;
Graph g;
auto v0 = boost::add_vertex(g);
auto v1 = boost::add_vertex(g);
auto v2 = boost::add_vertex(g);
auto v3 = boost::add_vertex(g);
auto v4 = boost::add_vertex(g);
boost::add_edge(v0, v1, g);
boost::add_edge(v0, v2, g);
boost::add_edge(v0, v3, g);
boost::add_edge(v2, v4, g);
boost::add_edge(v3, v4, g);
bool has_cycle = false;
std::vector<boost::default_color_type> colors(boost::num_vertices(g));
boost::iterator_property_map color_map(colors.begin(), boost::get(boost::vertex_index, g));
boost::depth_first_search(g, cycle_detector{has_cycle}, color_map, v0);
}