fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MbvUI
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!