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