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

   1 //=======================================================================
   2 // Copyright 2000 University of Notre Dame.
   3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
   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
  14    Boost.Grpah. Someone needs to update it, as it does NOT compile.
  15 */
  16
  17 #include <boost/config.hpp>
  18 #include <set>
  19 #include <iostream>
  20 #include <iterator>
  21 #include <algorithm>
  22 #include <boost/graph/adjacency_list.hpp>
  23 #include <boost/graph/edge_connectivity.hpp>
  24
  25 using namespace boost;
  26
  27 int main()
  28 {
  29     const int N = 8;
  30     typedef adjacency_list< vecS, vecS, undirectedS > UndirectedGraph;
  31     UndirectedGraph g(N);
  32
  33     add_edge(0, 1, g);
  34     add_edge(0, 2, g);
  35     add_edge(0, 3, g);
  36     add_edge(1, 2, g);
  37     add_edge(1, 3, g);
  38     add_edge(2, 3, g);
  39     add_edge(3, 4, g);
  40     add_edge(3, 7, g);
  41     add_edge(4, 5, g);
  42     add_edge(4, 6, g);
  43     add_edge(4, 7, g);
  44     add_edge(5, 6, g);
  45     add_edge(5, 7, g);
  46     add_edge(6, 7, g);
  47
  48     typedef graph_traits< UndirectedGraph >::edge_descriptor edge_descriptor;
  49     typedef graph_traits< UndirectedGraph >::degree_size_type degree_size_type;
  50     std::vector< edge_descriptor > disconnecting_set;
  51
  52     degree_size_type c
  53         = edge_connectivity(g, std::back_inserter(disconnecting_set));
  54
  55     std::cout << "The edge connectivity is " << c << "." << std::endl;
  56     std::cout << "The disconnecting set is {";
  57
  58     std::copy(disconnecting_set.begin(), disconnecting_set.end(),
  59         std::ostream_iterator< edge_descriptor >(std::cout, " "));
  60     std::cout << "}." << std::endl;
  61
  62     return 0;
  63 }