ceph/src/boost/libs/graph/example/edge-connectivity.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
   9 /*
  10    IMPORTANT!!!
  11    ~~~~~~~~~~~~
  12    This example uses interfaces that have been deprecated and removed from Boost.Grpah.
  13    Someone needs to update it, as it does NOT compile.
  14 */
  15
  16 #include <boost/config.hpp>
  17 #include <algorithm>
  18 #include <utility>
  19 #include <boost/graph/edmonds_karp_max_flow.hpp>
  20 #include <boost/graph/push_relabel_max_flow.hpp>
  21 #include <boost/graph/adjacency_list.hpp>
  22 #include <boost/graph/graphviz.hpp>
  23
  24 namespace boost
  25 {
  26   template < typename Graph >
  27     std::pair < typename graph_traits < Graph >::vertex_descriptor,
  28     typename graph_traits < Graph >::degree_size_type >
  29     min_degree_vertex(Graph & g)
  30   {
  31     typename graph_traits < Graph >::vertex_descriptor p;
  32     typedef typename graph_traits < Graph >::degree_size_type size_type;
  33     size_type delta = (std::numeric_limits < size_type >::max)();
  34     typename graph_traits < Graph >::vertex_iterator i, iend;
  35     for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
  36       if (degree(*i, g) < delta)
  37       {
  38         delta = degree(*i, g);
  39         p = *i;
  40       }
  41     return std::make_pair(p, delta);
  42   }
  43
  44   template < typename Graph, typename OutputIterator >
  45     void neighbors(const Graph & g,
  46                    typename graph_traits < Graph >::vertex_descriptor u,
  47                    OutputIterator result)
  48   {
  49     typename graph_traits < Graph >::adjacency_iterator ai, aend;
  50     for (boost::tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
  51       *result++ = *ai;
  52   }
  53   template < typename Graph, typename VertexIterator,
  54     typename OutputIterator > void neighbors(const Graph & g,
  55                                              VertexIterator first,
  56                                              VertexIterator last,
  57                                              OutputIterator result)
  58   {
  59     for (; first != last; ++first)
  60       neighbors(g, *first, result);
  61   }
  62
  63   template < typename VertexListGraph, typename OutputIterator >
  64   typename graph_traits < VertexListGraph >::degree_size_type
  65   edge_connectivity(VertexListGraph & g, OutputIterator disconnecting_set)
  66   {
  67     typedef typename graph_traits <
  68       VertexListGraph >::vertex_descriptor vertex_descriptor;
  69     typedef typename graph_traits <
  70       VertexListGraph >::degree_size_type degree_size_type;
  71     typedef color_traits < default_color_type > Color;
  72     typedef typename adjacency_list_traits < vecS, vecS,
  73       directedS >::edge_descriptor edge_descriptor;
  74     typedef adjacency_list < vecS, vecS, directedS, no_property,
  75       property < edge_capacity_t, degree_size_type,
  76       property < edge_residual_capacity_t, degree_size_type,
  77       property < edge_reverse_t, edge_descriptor > > > > FlowGraph;
  78
  79     vertex_descriptor u, v, p, k;
  80     edge_descriptor e1, e2;
  81     bool inserted;
  82     typename graph_traits < VertexListGraph >::vertex_iterator vi, vi_end;
  83     degree_size_type delta, alpha_star, alpha_S_k;
  84     std::set < vertex_descriptor > S, neighbor_S;
  85     std::vector < vertex_descriptor > S_star, nonneighbor_S;
  86     std::vector < default_color_type > color(num_vertices(g));
  87     std::vector < edge_descriptor > pred(num_vertices(g));
  88
  89     FlowGraph flow_g(num_vertices(g));
  90     typename property_map < FlowGraph, edge_capacity_t >::type
  91       cap = get(edge_capacity, flow_g);
  92     typename property_map < FlowGraph, edge_residual_capacity_t >::type
  93       res_cap = get(edge_residual_capacity, flow_g);
  94     typename property_map < FlowGraph, edge_reverse_t >::type
  95       rev_edge = get(edge_reverse, flow_g);
  96
  97     typename graph_traits < VertexListGraph >::edge_iterator ei, ei_end;
  98     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
  99       u = source(*ei, g), v = target(*ei, g);
 100       boost::tie(e1, inserted) = add_edge(u, v, flow_g);
 101       cap[e1] = 1;
 102       boost::tie(e2, inserted) = add_edge(v, u, flow_g);
 103       cap[e2] = 1;
 104       rev_edge[e1] = e2;
 105       rev_edge[e2] = e1;
 106     }
 107
 108     boost::tie(p, delta) = min_degree_vertex(g);
 109     S_star.push_back(p);
 110     alpha_star = delta;
 111     S.insert(p);
 112     neighbor_S.insert(p);
 113     neighbors(g, S.begin(), S.end(),
 114               std::inserter(neighbor_S, neighbor_S.begin()));
 115     std::set_difference(vertices(g).first, vertices(g).second,
 116                         neighbor_S.begin(), neighbor_S.end(),
 117                         std::back_inserter(nonneighbor_S));
 118
 119     while (!nonneighbor_S.empty()) {
 120       k = nonneighbor_S.front();
 121       alpha_S_k = edmonds_karp_max_flow
 122         (flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
 123       if (alpha_S_k < alpha_star) {
 124         alpha_star = alpha_S_k;
 125         S_star.clear();
 126         for (boost::tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
 127           if (color[*vi] != Color::white())
 128             S_star.push_back(*vi);
 129       }
 130       S.insert(k);
 131       neighbor_S.insert(k);
 132       neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
 133       nonneighbor_S.clear();
 134       std::set_difference(vertices(g).first, vertices(g).second,
 135                           neighbor_S.begin(), neighbor_S.end(),
 136                           std::back_inserter(nonneighbor_S));
 137     }
 138
 139     std::vector < bool > in_S_star(num_vertices(g), false);
 140     typename std::vector < vertex_descriptor >::iterator si;
 141     for (si = S_star.begin(); si != S_star.end(); ++si)
 142       in_S_star[*si] = true;
 143     degree_size_type c = 0;
 144     for (si = S_star.begin(); si != S_star.end(); ++si) {
 145       typename graph_traits < VertexListGraph >::out_edge_iterator ei, ei_end;
 146       for (boost::tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
 147         if (!in_S_star[target(*ei, g)]) {
 148           *disconnecting_set++ = *ei;
 149           ++c;
 150         }
 151     }
 152
 153     return c;
 154   }
 155
 156 }
 157
 158 int
 159 main()
 160 {
 161   using namespace boost;
 162   GraphvizGraph g;
 163   read_graphviz("figs/edge-connectivity.dot", g);
 164
 165   typedef graph_traits < GraphvizGraph >::edge_descriptor edge_descriptor;
 166   typedef graph_traits < GraphvizGraph >::degree_size_type degree_size_type;
 167   std::vector < edge_descriptor > disconnecting_set;
 168   degree_size_type c =
 169     edge_connectivity(g, std::back_inserter(disconnecting_set));
 170
 171   std::cout << "The edge connectivity is " << c << "." << std::endl;
 172
 173   property_map < GraphvizGraph, vertex_attribute_t >::type
 174     attr_map = get(vertex_attribute, g);
 175
 176   std::cout << "The disconnecting set is {";
 177   for (std::vector < edge_descriptor >::iterator i =
 178        disconnecting_set.begin(); i != disconnecting_set.end(); ++i)
 179     std::
 180       cout << "(" << attr_map[source(*i, g)]["label"] << "," <<
 181       attr_map[target(*i, g)]["label"] << ") ";
 182   std::cout << "}." << std::endl;
 183   return EXIT_SUCCESS;
 184 }