fork download
  1. #include <iostream> // for std::cout
  2. #include <boost/graph/adjacency_list.hpp>
  3. #include <boost/graph/depth_first_search.hpp>
  4. #include <boost/graph/visitors.hpp>
  5.  
  6. using namespace boost;
  7.  
  8. struct cycle_detector: public dfs_visitor<> {
  9. cycle_detector(bool& has_cycle) :
  10. _has_cycle(has_cycle) {
  11. }
  12.  
  13. template<class Edge, class Graph>
  14. void back_edge(Edge, Graph&) {
  15. _has_cycle = true;
  16. }
  17. protected:
  18. bool& _has_cycle;
  19. };
  20.  
  21. int main(int, char*[]) {
  22. // create a typedef for the Graph type
  23. typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
  24.  
  25. // Make convenient labels for the vertices
  26. enum {
  27. A, B, C, N
  28. };
  29. const int num_vertices = N;
  30.  
  31. // writing out the edges in the graph
  32. typedef std::pair<int, int> Edge;
  33. Edge edge_array[] = {
  34. Edge(A, B), Edge(C, B), Edge(A, C)
  35. };
  36. const int num_edges = sizeof(edge_array) / sizeof(edge_array[0]);
  37.  
  38. // declare a graph object
  39. Graph g(num_vertices);
  40.  
  41. // add the edges to the graph object
  42. for (int i = 0; i < num_edges; ++i)
  43. add_edge(edge_array[i].first, edge_array[i].second, g);
  44.  
  45. bool has_cycle = false;
  46. cycle_detector vis(has_cycle);
  47. boost::depth_first_search(g, visitor(vis));
  48. std::cerr << "has_cycle: " << std::boolalpha << has_cycle << std::endl;
  49. return 0;
  50. }
Success #stdin #stdout 0.02s 2820KB
stdin
Standard input is empty
stdout
Standard output is empty