boost/libs/graph/example/connected-components.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 <iostream>
  10 #include <vector>
  11 #include <boost/graph/connected_components.hpp>
  12 #include <boost/graph/adjacency_list.hpp>
  13
  14 int
  15 main()
  16 {
  17   using namespace boost;
  18   typedef adjacency_list < vecS, vecS, undirectedS > Graph;
  19   typedef graph_traits < Graph >::vertex_descriptor Vertex;
  20
  21   const int N = 6;
  22   Graph G(N);
  23   add_edge(0, 1, G);
  24   add_edge(1, 4, G);
  25   add_edge(4, 0, G);
  26   add_edge(2, 5, G);
  27
  28   std::vector<int> c(num_vertices(G));
  29   int num = connected_components
  30     (G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));
  31
  32   std::cout << std::endl;
  33   std::vector < int >::iterator i;
  34   std::cout << "Total number of components: " << num << std::endl;
  35   for (i = c.begin(); i != c.end(); ++i)
  36     std::cout << "Vertex " << i - c.begin()
  37       << " is in component " << *i << std::endl;
  38   std::cout << std::endl;
  39   return EXIT_SUCCESS;
  40 }