Re: [Boost-users] Cycle detection in a directed graph with adjacency_matrix

Subject: Re: [Boost-users] Cycle detection in a directed graph with adjacency_matrix
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-04-12 22:18:30

On Tue, 12 Apr 2011, albert kao wrote:

> Is it possible to detect any cycle in a directed graph with the adjacency_matrix of the Boost Graph Library?My test program has this compile errors:
> adjacency_matrix_is_cyclic.cpp:6: error: expected initializer before ‘<’ token
> adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’ token
> adjacency_matrix_is_cyclic.cpp:14: error: ‘edge_t’ has not been declared
> 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    
> 
>  
> $ 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 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;
> }          

Try adding "boost::" before "graph_traits" and see if that fixes any of 
the errors.

-- Jeremiah Willcock