ceph/src/boost/libs/graph/example/strong_components.cpp

   1 //=======================================================================
   2 // Copyright 1997-2001 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 /*
  11    IMPORTANT!!!
  12    ~~~~~~~~~~~~
  13    This example uses interfaces that have been deprecated and removed from Boost.Grpah.
  14    Someone needs to update it, as it does NOT compile.
  15 */
  16
  17 #include <boost/config.hpp>
  18 #include <iostream>
  19 #include <vector>
  20 #include <boost/graph/strong_components.hpp>
  21 #include <boost/graph/adjacency_list.hpp>
  22 #include <boost/graph/graphviz.hpp>
  23 #include <boost/graph/graph_utility.hpp>
  24 /*
  25   Sample output:
  26   A directed graph:
  27   a --> b f h
  28   b --> c a
  29   c --> d b
  30   d --> e
  31   e --> d
  32   f --> g
  33   g --> f d
  34   h --> i
  35   i --> h j e c
  36   j -->
  37
  38   Total number of components: 4
  39   Vertex a is in component 3
  40   Vertex b is in component 3
  41   Vertex c is in component 3
  42   Vertex d is in component 0
  43   Vertex e is in component 0
  44   Vertex f is in component 1
  45   Vertex g is in component 1
  46   Vertex h is in component 3
  47   Vertex i is in component 3
  48   Vertex j is in component 2
  49  */
  50
  51 int main(int, char*[])
  52 {
  53   using namespace boost;
  54   const char* name = "abcdefghij";
  55
  56   adjacency_list<vecS, vecS, directedS> G;
  57   dynamic_properties dp;
  58   read_graphviz("scc.dot", G, dp);
  59
  60   std::cout << "A directed graph:" << std::endl;
  61   print_graph(G, name);
  62   std::cout << std::endl;
  63
  64   typedef graph_traits<adjacency_list<vecS, vecS, directedS> >::vertex_descriptor Vertex;
  65
  66   std::vector<int> component(num_vertices(G)), discover_time(num_vertices(G));
  67   std::vector<default_color_type> color(num_vertices(G));
  68   std::vector<Vertex> root(num_vertices(G));
  69   int num = strong_components(G, make_iterator_property_map(component.begin(), get(vertex_index, G)),
  70                               root_map(make_iterator_property_map(root.begin(), get(vertex_index, G))).
  71                               color_map(make_iterator_property_map(color.begin(), get(vertex_index, G))).
  72                               discover_time_map(make_iterator_property_map(discover_time.begin(), get(vertex_index, G))));
  73
  74   std::cout << "Total number of components: " << num << std::endl;
  75   std::vector<int>::size_type i;
  76   for (i = 0; i != component.size(); ++i)
  77     std::cout << "Vertex " << name[i]
  78          <<" is in component " << component[i] << std::endl;
  79
  80   return 0;
  81 }