ceph/src/boost/libs/graph/test/stoer_wagner_test.cpp

   1 //            Copyright Daniel Trebbien 2010.
   2 // Distributed under the Boost Software License, Version 1.0.
   3 //   (See accompanying file LICENSE_1_0.txt or the copy at
   4 //         http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #if defined(_MSC_VER) && !defined(_CRT_SECURE_NO_WARNINGS)
   7 #define _CRT_SECURE_NO_WARNINGS
   8 #endif
   9
  10 #include <fstream>
  11 #include <iostream>
  12 #include <map>
  13 #include <vector>
  14 #include <string>
  15 #include <boost/graph/adjacency_list.hpp>
  16 #include <boost/graph/connected_components.hpp>
  17 #include <boost/graph/exception.hpp>
  18 #include <boost/graph/graph_traits.hpp>
  19 #include <boost/graph/read_dimacs.hpp>
  20 #include <boost/graph/stoer_wagner_min_cut.hpp>
  21 #include <boost/graph/property_maps/constant_property_map.hpp>
  22 #include <boost/property_map/property_map.hpp>
  23 #include <boost/core/lightweight_test.hpp>
  24 #include <boost/tuple/tuple.hpp>
  25
  26 typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
  27     boost::no_property, boost::property< boost::edge_weight_t, int > >
  28     undirected_graph;
  29 typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type
  30     weight_map_type;
  31 typedef boost::property_traits< weight_map_type >::value_type weight_type;
  32
  33 typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS >
  34     undirected_unweighted_graph;
  35
  36 std::string test_dir;
  37
  38 struct edge_t
  39 {
  40     unsigned long first;
  41     unsigned long second;
  42 };
  43
  44 // the example from Stoer & Wagner (1997)
  45 void test0()
  46 {
  47     edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
  48         { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } };
  49     weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 };
  50     undirected_graph g(edges, edges + 12, ws, 8, 12);
  51
  52     weight_map_type weights = get(boost::edge_weight, g);
  53     std::map< int, bool > parity;
  54     boost::associative_property_map< std::map< int, bool > > parities(parity);
  55     int w
  56         = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
  57     BOOST_TEST_EQ(w, 4);
  58     const bool parity0 = get(parities, 0);
  59     BOOST_TEST_EQ(parity0, get(parities, 1));
  60     BOOST_TEST_EQ(parity0, get(parities, 4));
  61     BOOST_TEST_EQ(parity0, get(parities, 5));
  62     const bool parity2 = get(parities, 2);
  63     BOOST_TEST_NE(parity0, parity2);
  64     BOOST_TEST_EQ(parity2, get(parities, 3));
  65     BOOST_TEST_EQ(parity2, get(parities, 6));
  66     BOOST_TEST_EQ(parity2, get(parities, 7));
  67 }
  68
  69 void test1()
  70 {
  71     { // if only one vertex, can't run `boost::stoer_wagner_min_cut`
  72         undirected_graph g;
  73         add_vertex(g);
  74
  75         BOOST_TEST_THROWS(
  76             boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g)),
  77             boost::bad_graph);
  78     }
  79     { // three vertices with one multi-edge
  80         typedef boost::graph_traits< undirected_graph >::vertex_descriptor
  81             vertex_descriptor;
  82
  83         edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 1, 2 }, { 2, 0 } };
  84         weight_type ws[] = { 3, 1, 1, 1 };
  85         undirected_graph g(edges, edges + 4, ws, 3, 4);
  86
  87         weight_map_type weights = get(boost::edge_weight, g);
  88         std::map< int, bool > parity;
  89         boost::associative_property_map< std::map< int, bool > > parities(
  90             parity);
  91         std::map< vertex_descriptor, vertex_descriptor > assignment;
  92         boost::associative_property_map<
  93             std::map< vertex_descriptor, vertex_descriptor > >
  94             assignments(assignment);
  95         int w = boost::stoer_wagner_min_cut(g, weights,
  96             boost::parity_map(parities).vertex_assignment_map(assignments));
  97         BOOST_TEST_EQ(w, 3);
  98         const bool parity2 = get(parities, 2), parity0 = get(parities, 0);
  99         BOOST_TEST_NE(parity2, parity0);
 100         BOOST_TEST_EQ(parity0, get(parities, 1));
 101     }
 102 }
 103
 104 // example by Daniel Trebbien
 105 void test2()
 106 {
 107     edge_t edges[] = { { 5, 2 }, { 0, 6 }, { 5, 6 }, { 3, 1 }, { 0, 1 },
 108         { 6, 3 }, { 4, 6 }, { 2, 4 }, { 5, 3 } };
 109     weight_type ws[] = { 1, 3, 4, 6, 4, 1, 2, 5, 2 };
 110     undirected_graph g(edges, edges + 9, ws, 7, 9);
 111
 112     std::map< int, bool > parity;
 113     boost::associative_property_map< std::map< int, bool > > parities(parity);
 114     int w = boost::stoer_wagner_min_cut(
 115         g, get(boost::edge_weight, g), boost::parity_map(parities));
 116     BOOST_TEST_EQ(w, 3);
 117     const bool parity2 = get(parities, 2);
 118     BOOST_TEST_EQ(parity2, get(parities, 4));
 119     const bool parity5 = get(parities, 5);
 120     BOOST_TEST_NE(parity2, parity5);
 121     BOOST_TEST_EQ(parity5, get(parities, 3));
 122     BOOST_TEST_EQ(parity5, get(parities, 6));
 123     BOOST_TEST_EQ(parity5, get(parities, 1));
 124     BOOST_TEST_EQ(parity5, get(parities, 0));
 125 }
 126
 127 // example by Daniel Trebbien
 128 void test3()
 129 {
 130     edge_t edges[] = { { 3, 4 }, { 3, 6 }, { 3, 5 }, { 0, 4 }, { 0, 1 },
 131         { 0, 6 }, { 0, 7 }, { 0, 5 }, { 0, 2 }, { 4, 1 }, { 1, 6 }, { 1, 5 },
 132         { 6, 7 }, { 7, 5 }, { 5, 2 }, { 3, 4 } };
 133     weight_type ws[] = { 0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4 };
 134     undirected_graph g(edges, edges + 16, ws, 8, 16);
 135
 136     weight_map_type weights = get(boost::edge_weight, g);
 137     std::map< int, bool > parity;
 138     boost::associative_property_map< std::map< int, bool > > parities(parity);
 139     int w
 140         = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
 141     BOOST_TEST_EQ(w, 7);
 142     const bool parity1 = get(parities, 1);
 143     BOOST_TEST_EQ(parity1, get(parities, 5));
 144     const bool parity0 = get(parities, 0);
 145     BOOST_TEST_NE(parity1, parity0);
 146     BOOST_TEST_EQ(parity0, get(parities, 2));
 147     BOOST_TEST_EQ(parity0, get(parities, 3));
 148     BOOST_TEST_EQ(parity0, get(parities, 4));
 149     BOOST_TEST_EQ(parity0, get(parities, 6));
 150     BOOST_TEST_EQ(parity0, get(parities, 7));
 151 }
 152
 153 void test4()
 154 {
 155     typedef boost::graph_traits<
 156         undirected_unweighted_graph >::vertex_descriptor vertex_descriptor;
 157     typedef boost::graph_traits< undirected_unweighted_graph >::edge_descriptor
 158         edge_descriptor;
 159
 160     edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
 161         { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 },
 162         { 0, 4 }, { 6, 7 } };
 163     undirected_unweighted_graph g(edges, edges + 14, 8);
 164
 165     std::map< vertex_descriptor, bool > parity;
 166     boost::associative_property_map< std::map< vertex_descriptor, bool > >
 167         parities(parity);
 168     std::map< vertex_descriptor, vertex_descriptor > assignment;
 169     boost::associative_property_map<
 170         std::map< vertex_descriptor, vertex_descriptor > >
 171         assignments(assignment);
 172     int w = boost::stoer_wagner_min_cut(g,
 173         boost::make_constant_property< edge_descriptor >(weight_type(1)),
 174         boost::vertex_assignment_map(assignments).parity_map(parities));
 175     BOOST_TEST_EQ(w, 2);
 176     const bool parity0 = get(parities, 0);
 177     BOOST_TEST_EQ(parity0, get(parities, 1));
 178     BOOST_TEST_EQ(parity0, get(parities, 4));
 179     BOOST_TEST_EQ(parity0, get(parities, 5));
 180     const bool parity2 = get(parities, 2);
 181     BOOST_TEST_NE(parity0, parity2);
 182     BOOST_TEST_EQ(parity2, get(parities, 3));
 183     BOOST_TEST_EQ(parity2, get(parities, 6));
 184     BOOST_TEST_EQ(parity2, get(parities, 7));
 185 }
 186
 187 // The input for the `test_prgen` family of tests comes from a program, named
 188 // `prgen`, that comes with a package of min-cut solvers by Chandra Chekuri,
 189 // Andrew Goldberg, David Karger, Matthew Levine, and Cliff Stein. `prgen` was
 190 // used to generate input graphs and the solvers were used to verify the return
 191 // value of `boost::stoer_wagner_min_cut` on the input graphs.
 192 //
 193 // http://www.columbia.edu/~cs2035/code.html
 194 //
 195 // Note that it is somewhat more difficult to verify the parities because
 196 // "`prgen` graphs" often have several min-cuts. This is why only the cut
 197 // weight of the min-cut is verified.
 198
 199 // 3 min-cuts
 200 void test_prgen_20_70_2()
 201 {
 202     typedef boost::graph_traits< undirected_graph >::vertex_descriptor
 203         vertex_descriptor;
 204
 205     std::ifstream ifs(
 206         (test_dir + "/prgen_input_graphs/prgen_20_70_2.net").c_str());
 207     undirected_graph g;
 208     boost::read_dimacs_min_cut(
 209         g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
 210
 211     std::map< vertex_descriptor, std::size_t > component;
 212     boost::associative_property_map<
 213         std::map< vertex_descriptor, std::size_t > >
 214         components(component);
 215     BOOST_TEST_EQ(boost::connected_components(g, components),
 216         1U); // verify the connectedness assumption
 217
 218     typedef boost::shared_array_property_map< weight_type,
 219         boost::property_map< undirected_graph,
 220             boost::vertex_index_t >::const_type >
 221         distances_type;
 222     distances_type distances = boost::make_shared_array_property_map(
 223         num_vertices(g), weight_type(0), get(boost::vertex_index, g));
 224     typedef std::vector< vertex_descriptor >::size_type index_in_heap_type;
 225     typedef boost::shared_array_property_map< index_in_heap_type,
 226         boost::property_map< undirected_graph,
 227             boost::vertex_index_t >::const_type >
 228         indicesInHeap_type;
 229     indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(
 230         num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
 231     boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
 232         distances_type, std::greater< weight_type > >
 233         pq(distances, indicesInHeap);
 234
 235     int w = boost::stoer_wagner_min_cut(
 236         g, get(boost::edge_weight, g), boost::max_priority_queue(pq));
 237     BOOST_TEST_EQ(w, 3407);
 238 }
 239
 240 // 7 min-cuts
 241 void test_prgen_50_40_2()
 242 {
 243     typedef boost::graph_traits< undirected_graph >::vertex_descriptor
 244         vertex_descriptor;
 245
 246     std::ifstream ifs(
 247         (test_dir + "/prgen_input_graphs/prgen_50_40_2.net").c_str());
 248     undirected_graph g;
 249     boost::read_dimacs_min_cut(
 250         g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
 251
 252     std::map< vertex_descriptor, std::size_t > component;
 253     boost::associative_property_map<
 254         std::map< vertex_descriptor, std::size_t > >
 255         components(component);
 256     BOOST_TEST_EQ(boost::connected_components(g, components),
 257         1U); // verify the connectedness assumption
 258
 259     int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g));
 260     BOOST_TEST_EQ(w, 10056);
 261 }
 262
 263 // 6 min-cuts
 264 void test_prgen_50_70_2()
 265 {
 266     typedef boost::graph_traits< undirected_graph >::vertex_descriptor
 267         vertex_descriptor;
 268
 269     std::ifstream ifs(
 270         (test_dir + "/prgen_input_graphs/prgen_50_70_2.net").c_str());
 271     undirected_graph g;
 272     boost::read_dimacs_min_cut(
 273         g, get(boost::edge_weight, g), boost::dummy_property_map(), ifs);
 274
 275     std::map< vertex_descriptor, std::size_t > component;
 276     boost::associative_property_map<
 277         std::map< vertex_descriptor, std::size_t > >
 278         components(component);
 279     BOOST_TEST_EQ(boost::connected_components(g, components),
 280         1U); // verify the connectedness assumption
 281
 282     int w = boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g));
 283     BOOST_TEST_EQ(w, 21755);
 284 }
 285
 286 int main(int argc, char* argv[])
 287 {
 288     if (BOOST_TEST(argc == 2)) {
 289         test_dir = argv[1];
 290         test0();
 291         test1();
 292         test2();
 293         test3();
 294         test4();
 295         test_prgen_20_70_2();
 296         test_prgen_50_70_2();
 297     }
 298     return boost::report_errors();
 299 }