Re: [Boost-users] Cycle detection in a directed graph with adjacency_matrix
On Tue, 12 Apr 2011, albert kao wrote:
After adding "boost::" before "graph_traits", the compile errors are: adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’ token adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const Graph&)’: adjacency_matrix_is_cyclic.cpp:26: error: ‘generic_dfs_v1’ was not declared in this scope
adjacency_matrix_is_cyclic.cpp: #include <iostream> #include <boost/graph/graph_utility.hpp> #include <boost/graph/adjacency_matrix.hpp>
typedef boost::adjacency_matrix<boost::directedS> Graph; typedef boost::graph_traits<Graph>::edge_descriptor edge_t; struct cycle_detector : public dfs_visitor_default { cycle_detector(bool & cycle): has_cycle(cycle) { } void back_edge(edge_t, const Graph &) { has_cycle = true; } bool & has_cycle; };
bool has_cycle(const Graph & g) { bool has_cycle = false; cycle_detector vis(has_cycle); generic_dfs_v1(g, vis); return has_cycle; }
enum { A, B, C, D, E, F, N }; const char* name = "ABCDEF";
int main(int argc, char *argv[]) { Graph g(N); add_edge(B, C, g); add_edge(B, F, g); add_edge(C, A, g); add_edge(C, C, g); add_edge(D, E, g); add_edge(E, D, g); add_edge(F, A, g);
std::cout << "vertex set: "; boost::print_vertices(g, name); std::cout << std::endl;
std::cout << "edge set: "; boost::print_edges(g, name); std::cout << std::endl;
std::cout << "out-edges: " << std::endl; boost::print_graph(g, name); std::cout << std::endl;
std::cout << "has_cycle(g) " << has_cycle(g) << std::endl;
return 0; }
You also need boost:: before dfs_visitor_default. You should also use boost::depth_first_search instead of generic_dfs_v1 (which is internal). -- Jeremiah Willcock
The compile errors are now: adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’ token adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const Graph&)’: adjacency_matrix_is_cyclic.cpp:26: error: no matching function for call to ‘depth_first_search(const boost::adjacency_matrix<boost::directedS, boost::no_property, boost::no_property, boost::no_property, std::allocator<bool> >&, cycle_detector&)’ $ cat adjacency_matrix_is_cyclic.cpp #include <iostream> #include <boost/graph/graph_utility.hpp> #include <boost/graph/adjacency_matrix.hpp> typedef boost::adjacency_matrix<boost::directedS> Graph; typedef boost::graph_traits<Graph>::edge_descriptor edge_t; struct cycle_detector : public boost::dfs_visitor_default { cycle_detector(bool & cycle): has_cycle(cycle) { } void back_edge(edge_t, const Graph &) { has_cycle = true; } bool & has_cycle; }; bool has_cycle(const Graph & g) { bool has_cycle = false; cycle_detector vis(has_cycle); boost::depth_first_search(g, vis); return has_cycle; } enum { A, B, C, D, E, F, N }; const char* name = "ABCDEF"; int main(int argc, char *argv[]) { Graph g(N); add_edge(B, C, g); add_edge(B, F, g); add_edge(C, A, g); add_edge(C, C, g); add_edge(D, E, g); add_edge(E, D, g); add_edge(F, A, g); std::cout << "vertex set: "; boost::print_vertices(g, name); std::cout << std::endl; std::cout << "edge set: "; boost::print_edges(g, name); std::cout << std::endl; std::cout << "out-edges: " << std::endl; boost::print_graph(g, name); std::cout << std::endl; std::cout << "has_cycle(g) " << has_cycle(g) << std::endl; return 0; } On Tue, Apr 12, 2011 at 10:40 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Tue, 12 Apr 2011, albert kao wrote:
After adding "boost::" before "graph_traits", the compile errors are:
adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’ token adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const Graph&)’: adjacency_matrix_is_cyclic.cpp:26: error: ‘generic_dfs_v1’ was not declared in this scope
adjacency_matrix_is_cyclic.cpp: #include <iostream> #include <boost/graph/graph_utility.hpp> #include <boost/graph/adjacency_matrix.hpp>
typedef boost::adjacency_matrix<boost::directedS> Graph; typedef boost::graph_traits<Graph>::edge_descriptor edge_t;
struct cycle_detector : public dfs_visitor_default { cycle_detector(bool & cycle): has_cycle(cycle) { } void back_edge(edge_t, const Graph &) { has_cycle = true; } bool & has_cycle; };
bool has_cycle(const Graph & g) { bool has_cycle = false; cycle_detector vis(has_cycle); generic_dfs_v1(g, vis); return has_cycle; }
enum { A, B, C, D, E, F, N }; const char* name = "ABCDEF";
int main(int argc, char *argv[]) { Graph g(N); add_edge(B, C, g); add_edge(B, F, g); add_edge(C, A, g); add_edge(C, C, g); add_edge(D, E, g); add_edge(E, D, g); add_edge(F, A, g);
std::cout << "vertex set: "; boost::print_vertices(g, name); std::cout << std::endl;
std::cout << "edge set: "; boost::print_edges(g, name); std::cout << std::endl;
std::cout << "out-edges: " << std::endl; boost::print_graph(g, name); std::cout << std::endl;
std::cout << "has_cycle(g) " << has_cycle(g) << std::endl;
return 0; }
You also need boost:: before dfs_visitor_default. You should also use boost::depth_first_search instead of generic_dfs_v1 (which is internal).
-- Jeremiah Willcock
On Tue, 12 Apr 2011, albert kao wrote:
The compile errors are now: adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’ token adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const Graph&)’: adjacency_matrix_is_cyclic.cpp:26: error: no matching function for call to ‘depth_first_search(const boost::adjacency_matrix<boost::directedS, boost::no_property, boost::no_property, boost::no_property, std::allocator<bool> >&, cycle_detector&)’
There is no class named "dfs_visitor_default". Could you please check whether that is spelled correctly? -- Jeremiah Willcock
participants (2)
-
albert kao
-
Jeremiah Willcock