ceph/src/boost/libs/graph/example/cycle-file-dep.cpp

   1 //=======================================================================
   2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8 #include <boost/config.hpp>
   9 #include <fstream>
  10 #include <iostream>
  11 #include <string>
  12 #include <boost/graph/adjacency_list.hpp>
  13 #include <boost/graph/graph_utility.hpp>
  14
  15 using namespace boost;
  16
  17 namespace std
  18 {
  19   template < typename T >
  20     std::istream & operator >> (std::istream & in, std::pair < T, T > &p)
  21   {
  22     in >> p.first >> p.second;
  23     return in;
  24   }
  25 }
  26
  27 typedef adjacency_list < listS, // Store out-edges of each vertex in a std::list
  28   vecS,                         // Store vertex set in a std::vector
  29   directedS                     // The file dependency graph is directed
  30 > file_dep_graph;
  31
  32 typedef graph_traits < file_dep_graph >::vertex_descriptor vertex_t;
  33 typedef graph_traits < file_dep_graph >::edge_descriptor edge_t;
  34
  35 bool
  36 has_cycle_dfs(const file_dep_graph & g, vertex_t u,
  37               default_color_type * color)
  38 {
  39   color[u] = gray_color;
  40   graph_traits < file_dep_graph >::adjacency_iterator vi, vi_end;
  41   for (boost::tie(vi, vi_end) = adjacent_vertices(u, g); vi != vi_end; ++vi)
  42     if (color[*vi] == white_color) {
  43       if (has_cycle_dfs(g, *vi, color))
  44         return true;            // cycle detected, return immediately
  45     } else if (color[*vi] == gray_color)        // *vi is an ancestor!
  46       return true;
  47   color[u] = black_color;
  48   return false;
  49 }
  50
  51 bool
  52 has_cycle(const file_dep_graph & g)
  53 {
  54   std::vector < default_color_type > color(num_vertices(g), white_color);
  55   graph_traits < file_dep_graph >::vertex_iterator vi, vi_end;
  56   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  57     if (color[*vi] == white_color)
  58       if (has_cycle_dfs(g, *vi, &color[0]))
  59         return true;
  60   return false;
  61 }
  62
  63
  64 int
  65 main(int argc, const char** argv)
  66 {
  67   std::ifstream file_in(argc >= 2 ? argv[1] : "makefile-dependencies.dat");
  68   typedef graph_traits < file_dep_graph >::vertices_size_type size_type;
  69   size_type n_vertices;
  70   file_in >> n_vertices;        // read in number of vertices
  71   std::istream_iterator < std::pair < size_type,
  72     size_type > > input_begin(file_in), input_end;
  73 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  74   // VC++ has trouble with the edge iterator constructor
  75   file_dep_graph g(n_vertices);
  76   while (input_begin != input_end) {
  77     size_type i, j;
  78     boost::tie(i, j) = *input_begin++;
  79     add_edge(i, j, g);
  80   }
  81 #else
  82   file_dep_graph g(input_begin, input_end, n_vertices);
  83 #endif
  84
  85   std::vector < std::string > name(num_vertices(g));
  86   std::ifstream name_in(argc >= 3 ? argv[2] : "makefile-target-names.dat");
  87   graph_traits < file_dep_graph >::vertex_iterator vi, vi_end;
  88   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  89     name_in >> name[*vi];
  90
  91   assert(has_cycle(g) == false);
  92   return 0;
  93 }