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

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 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 #include <boost/config.hpp>
  11 #include <iostream>
  12 #include <vector>
  13 #include <algorithm>
  14 #include <utility>
  15 #include <boost/graph/adjacency_list.hpp>
  16 #include <boost/graph/connected_components.hpp>
  17
  18 /*
  19
  20   This example demonstrates the usage of the connected_components
  21   algorithm on a undirected graph. The example graphs come from
  22   "Introduction to Algorithms", Cormen, Leiserson, and Rivest p. 87
  23   (though we number the vertices from zero instead of one).
  24
  25   Sample output:
  26
  27   Total number of components: 3
  28   Vertex 0 is in component 0
  29   Vertex 1 is in component 0
  30   Vertex 2 is in component 1
  31   Vertex 3 is in component 2
  32   Vertex 4 is in component 0
  33   Vertex 5 is in component 1
  34
  35  */
  36
  37 using namespace std;
  38
  39 int main(int, char*[])
  40 {
  41     using namespace boost;
  42     {
  43         typedef adjacency_list< vecS, vecS, undirectedS > Graph;
  44
  45         Graph G;
  46         add_edge(0, 1, G);
  47         add_edge(1, 4, G);
  48         add_edge(4, 0, G);
  49         add_edge(2, 5, G);
  50
  51         std::vector< int > component(num_vertices(G));
  52         int num = connected_components(G, &component[0]);
  53
  54         std::vector< int >::size_type i;
  55         cout << "Total number of components: " << num << endl;
  56         for (i = 0; i != component.size(); ++i)
  57             cout << "Vertex " << i << " is in component " << component[i]
  58                  << endl;
  59         cout << endl;
  60     }
  61     return 0;
  62 }