|
Boost Users : |
Subject: Re: [Boost-users] Cycle detection in a directed graph with adjacency_matrix
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-04-12 22:40:13
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
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net