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

   1 //  Copyright (c) 2006, Stephan Diederich
   2 //
   3 //  This code may be used under either of the following two licences:
   4 //
   5 //    Permission is hereby granted, free of charge, to any person
   6 //    obtaining a copy of this software and associated documentation
   7 //    files (the "Software"), to deal in the Software without
   8 //    restriction, including without limitation the rights to use,
   9 //    copy, modify, merge, publish, distribute, sublicense, and/or
  10 //    sell copies of the Software, and to permit persons to whom the
  11 //    Software is furnished to do so, subject to the following
  12 //    conditions:
  13 //
  14 //    The above copyright notice and this permission notice shall be
  15 //    included in all copies or substantial portions of the Software.
  16 //
  17 //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18 //    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  19 //    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20 //    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  21 //    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  22 //    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23 //    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  24 //    OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
  25 //
  26 //  Or:
  27 //
  28 //    Distributed under the Boost Software License, Version 1.0.
  29 //    (See accompanying file LICENSE_1_0.txt or copy at
  30 //    http://www.boost.org/LICENSE_1_0.txt)
  31
  32 #include <vector>
  33 #include <iterator>
  34 #include <iostream>
  35 #include <algorithm>
  36 #include <fstream>
  37
  38 #include <boost/test/minimal.hpp>
  39 #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
  40
  41 #include <boost/graph/adjacency_list.hpp>
  42 #include <boost/graph/adjacency_matrix.hpp>
  43 #include <boost/graph/random.hpp>
  44 #include <boost/property_map/property_map.hpp>
  45 #include <boost/random/linear_congruential.hpp>
  46 #include <boost/lexical_cast.hpp>
  47
  48 using namespace boost;
  49
  50 template <typename Graph, typename CapacityMap, typename ReverseEdgeMap>
  51 std::pair< typename graph_traits<Graph>::vertex_descriptor,typename graph_traits<Graph>::vertex_descriptor>
  52 fill_random_max_flow_graph(Graph& g, CapacityMap cap, ReverseEdgeMap rev, typename graph_traits<Graph>::vertices_size_type n_verts,
  53                            typename graph_traits<Graph>::edges_size_type n_edges, std::size_t seed)
  54 {
  55   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
  56   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  57   const int cap_low = 1;
  58   const int cap_high = 1000;
  59
  60   //init random numer generator
  61   minstd_rand gen(seed);
  62   //generate graph
  63   generate_random_graph(g, n_verts, n_edges, gen);
  64
  65   //init an uniform distribution int generator
  66   typedef variate_generator<minstd_rand, uniform_int<int> > tIntGen;
  67   tIntGen int_gen(gen, uniform_int<int>(cap_low, cap_high));
  68   //randomize edge-capacities
  69   //randomize_property<edge_capacity, Graph, tIntGen> (g,int_gen); //we cannot use this, as we have no idea how properties are stored, right?
  70   typename graph_traits<Graph>::edge_iterator ei, e_end;
  71   for(boost::tie(ei,e_end) = edges(g); ei != e_end; ++ei)
  72     cap[*ei] = int_gen();
  73
  74   //get source and sink node
  75   vertex_descriptor s = random_vertex(g, gen);
  76   vertex_descriptor t = graph_traits<Graph>::null_vertex();
  77   while(t == graph_traits<Graph>::null_vertex() || t == s)
  78     t = random_vertex(g, gen);
  79
  80   //add reverse edges (ugly... how to do better?!)
  81   std::list<edge_descriptor> edges_copy;
  82   boost::tie(ei, e_end) = edges(g);
  83   std::copy(ei, e_end, std::back_insert_iterator< std::list<edge_descriptor> >(edges_copy));
  84   while(!edges_copy.empty()){
  85     edge_descriptor old_edge = edges_copy.front();
  86     edges_copy.pop_front();
  87     vertex_descriptor source_vertex = target(old_edge, g);
  88     vertex_descriptor target_vertex = source(old_edge, g);
  89     bool inserted;
  90     edge_descriptor  new_edge;
  91     boost::tie(new_edge,inserted) = add_edge(source_vertex, target_vertex, g);
  92     assert(inserted);
  93     rev[old_edge] = new_edge;
  94     rev[new_edge] = old_edge ;
  95     cap[new_edge] = 0;
  96   }
  97   return std::make_pair(s,t);
  98 }
  99
 100 long test_adjacency_list_vecS(int n_verts, int n_edges, std::size_t seed){
 101   typedef adjacency_list_traits<vecS, vecS, directedS> tVectorTraits;
 102   typedef adjacency_list<vecS, vecS, directedS,
 103   property<vertex_index_t, long,
 104   property<vertex_predecessor_t, tVectorTraits::edge_descriptor,
 105   property<vertex_color_t, boost::default_color_type,
 106   property<vertex_distance_t, long> > > >,
 107   property<edge_capacity_t, long,
 108   property<edge_residual_capacity_t, long,
 109   property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
 110
 111   tVectorGraph g;
 112
 113   graph_traits<tVectorGraph>::vertex_descriptor src,sink;
 114   boost::tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
 115
 116   return boykov_kolmogorov_max_flow(g, get(edge_capacity, g),
 117                                     get(edge_residual_capacity, g),
 118                                     get(edge_reverse, g),
 119                                     get(vertex_predecessor, g),
 120                                     get(vertex_color, g),
 121                                     get(vertex_distance, g),
 122                                     get(vertex_index, g),
 123                                     src, sink);
 124 }
 125
 126 long test_adjacency_list_listS(int n_verts, int n_edges, std::size_t seed){
 127   typedef adjacency_list_traits<listS, listS, directedS> tListTraits;
 128   typedef adjacency_list<listS, listS, directedS,
 129   property<vertex_index_t, long,
 130   property<vertex_predecessor_t, tListTraits::edge_descriptor,
 131   property<vertex_color_t, boost::default_color_type,
 132   property<vertex_distance_t, long> > > >,
 133   property<edge_capacity_t, long,
 134   property<edge_residual_capacity_t, long,
 135   property<edge_reverse_t, tListTraits::edge_descriptor > > > > tListGraph;
 136
 137   tListGraph g;
 138
 139   graph_traits<tListGraph>::vertex_descriptor src,sink;
 140   boost::tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
 141
 142   //initialize vertex indices
 143   graph_traits<tListGraph>::vertex_iterator vi,v_end;
 144   graph_traits<tListGraph>::vertices_size_type index = 0;
 145   for(boost::tie(vi, v_end) = vertices(g); vi != v_end; ++vi){
 146     put(vertex_index, g, *vi, index++);
 147   }
 148   return boykov_kolmogorov_max_flow(g, get(edge_capacity, g),
 149                                     get(edge_residual_capacity, g),
 150                                     get(edge_reverse, g),
 151                                     get(vertex_predecessor, g),
 152                                     get(vertex_color, g),
 153                                     get(vertex_distance, g),
 154                                     get(vertex_index, g),
 155                                     src, sink);
 156 }
 157
 158 template<typename EdgeDescriptor>
 159     struct Node{
 160   boost::default_color_type vertex_color;
 161   long vertex_distance;
 162   EdgeDescriptor vertex_predecessor;
 163 };
 164
 165 template<typename EdgeDescriptor>
 166     struct Link{
 167   long edge_capacity;
 168   long edge_residual_capacity;
 169   EdgeDescriptor edge_reverse;
 170 };
 171
 172 long test_bundled_properties(int n_verts, int n_edges, std::size_t seed){
 173   typedef adjacency_list_traits<vecS, vecS, directedS> tTraits;
 174   typedef Node<tTraits::edge_descriptor> tVertex;
 175   typedef Link<tTraits::edge_descriptor> tEdge;
 176   typedef adjacency_list<vecS, vecS, directedS, tVertex, tEdge> tBundleGraph;
 177
 178   tBundleGraph g;
 179
 180   graph_traits<tBundleGraph>::vertex_descriptor src,sink;
 181   boost::tie(src,sink) = fill_random_max_flow_graph(g, get(&tEdge::edge_capacity,g), get(&tEdge::edge_reverse, g), n_verts, n_edges, seed);
 182   return boykov_kolmogorov_max_flow(g, get(&tEdge::edge_capacity, g),
 183                                     get(&tEdge::edge_residual_capacity, g),
 184                                     get(&tEdge::edge_reverse, g),
 185                                     get(&tVertex::vertex_predecessor, g),
 186                                     get(&tVertex::vertex_color, g),
 187                                     get(&tVertex::vertex_distance, g),
 188                                     get(vertex_index, g),
 189                                     src, sink);
 190 }
 191
 192 long test_overloads(int n_verts, int n_edges, std::size_t seed){
 193   typedef adjacency_list_traits<vecS, vecS, directedS> tTraits;
 194   typedef property <edge_capacity_t, long,
 195      property<edge_residual_capacity_t, long,
 196      property<edge_reverse_t, tTraits::edge_descriptor> > >tEdgeProperty;
 197   typedef adjacency_list<vecS, vecS, directedS, no_property, tEdgeProperty> tGraph;
 198
 199   tGraph g;
 200
 201   graph_traits<tGraph>::vertex_descriptor src,sink;
 202   boost::tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
 203
 204   std::vector<graph_traits<tGraph>::edge_descriptor> predecessor_vec(n_verts);
 205   std::vector<default_color_type> color_vec(n_verts);
 206   std::vector<graph_traits<tGraph>::vertices_size_type> distance_vec(n_verts);
 207
 208   long flow_overload_1 =
 209     boykov_kolmogorov_max_flow(g,
 210                                get(edge_capacity,g),
 211                                get(edge_residual_capacity,g),
 212                                get(edge_reverse,g),
 213                                get(vertex_index,g),
 214                                src, sink);
 215
 216   long flow_overload_2 =
 217     boykov_kolmogorov_max_flow(g,
 218                                get(edge_capacity,g),
 219                                get(edge_residual_capacity,g),
 220                                get(edge_reverse,g),
 221                                boost::make_iterator_property_map(
 222                                  color_vec.begin(), get(vertex_index, g)),
 223                                get(vertex_index,g),
 224                                src, sink);
 225
 226   BOOST_CHECK(flow_overload_1 == flow_overload_2);
 227   return flow_overload_1;
 228 }
 229
 230 template<class Graph,
 231          class EdgeCapacityMap,
 232          class ResidualCapacityEdgeMap,
 233          class ReverseEdgeMap,
 234          class PredecessorMap,
 235          class ColorMap,
 236          class DistanceMap,
 237          class IndexMap>
 238 class boykov_kolmogorov_test
 239   : public detail::bk_max_flow<
 240       Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
 241       PredecessorMap, ColorMap, DistanceMap, IndexMap
 242     >
 243 {
 244
 245   typedef typename graph_traits<Graph>::edge_descriptor tEdge;
 246   typedef typename graph_traits<Graph>::vertex_descriptor tVertex;
 247   typedef typename property_traits< typename property_map<Graph, edge_capacity_t>::const_type>::value_type tEdgeVal;
 248   typedef typename graph_traits<Graph>::vertex_iterator tVertexIterator;
 249   typedef typename graph_traits<Graph>::out_edge_iterator tOutEdgeIterator;
 250   typedef typename property_traits<ColorMap>::value_type tColorValue;
 251   typedef color_traits<tColorValue> tColorTraits;
 252   typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
 253   typedef typename detail::bk_max_flow<
 254     Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
 255     PredecessorMap, ColorMap, DistanceMap, IndexMap
 256   > tSuper;
 257   public:
 258         boykov_kolmogorov_test(Graph& g,
 259                                typename graph_traits<Graph>::vertex_descriptor src,
 260                                typename graph_traits<Graph>::vertex_descriptor sink)
 261           : tSuper(g, get(edge_capacity,g), get(edge_residual_capacity,g),
 262                    get(edge_reverse, g), get(vertex_predecessor, g),
 263                    get(vertex_color, g), get(vertex_distance, g),
 264                    get(vertex_index, g), src, sink)
 265           { }
 266
 267         void invariant_four(tVertex v) const{
 268           //passive nodes in S or T
 269           if(v == tSuper::m_source || v == tSuper::m_sink)
 270             return;
 271           typename std::list<tVertex>::const_iterator it = find(tSuper::m_orphans.begin(), tSuper::m_orphans.end(), v);
 272           // a node is active, if its in the active_list AND (is has_a_parent, or its already in the orphans_list or its the sink, or its the source)
 273           bool is_active = (tSuper::m_in_active_list_map[v] && (tSuper::has_parent(v) || it != tSuper::m_orphans.end() ));
 274           if(this->get_tree(v) != tColorTraits::gray() && !is_active){
 275             typename graph_traits<Graph>::out_edge_iterator ei,e_end;
 276             for(boost::tie(ei, e_end) = out_edges(v, tSuper::m_g); ei != e_end; ++ei){
 277               const tVertex& other_node = target(*ei, tSuper::m_g);
 278               if(this->get_tree(other_node) != this->get_tree(v)){
 279                 if(this->get_tree(v) == tColorTraits::black())
 280                   BOOST_CHECK(tSuper::m_res_cap_map[*ei] == 0);
 281                 else
 282                   BOOST_CHECK(tSuper::m_res_cap_map[tSuper::m_rev_edge_map[*ei]] == 0);
 283               }
 284              }
 285           }
 286         }
 287
 288         void invariant_five(const tVertex& v) const{
 289           BOOST_CHECK(this->get_tree(v) != tColorTraits::gray() || tSuper::m_time_map[v] <= tSuper::m_time);
 290         }
 291
 292         void invariant_six(const tVertex& v) const{
 293           if(this->get_tree(v) == tColorTraits::gray() || tSuper::m_time_map[v] != tSuper::m_time)
 294             return;
 295           else{
 296             tVertex current_node = v;
 297             tDistanceVal distance = 0;
 298             tColorValue color = this->get_tree(v);
 299             tVertex terminal = (color == tColorTraits::black()) ? tSuper::m_source : tSuper::m_sink;
 300             while(current_node != terminal){
 301               BOOST_CHECK(tSuper::has_parent(current_node));
 302               tEdge e = this->get_edge_to_parent(current_node);
 303               ++distance;
 304               current_node = (color == tColorTraits::black())? source(e, tSuper::m_g) : target(e, tSuper::m_g);
 305               if(distance > tSuper::m_dist_map[v])
 306                 break;
 307             }
 308             BOOST_CHECK(distance == tSuper::m_dist_map[v]);
 309           }
 310         }
 311
 312         void invariant_seven(const tVertex& v) const{
 313           if(this->get_tree(v) == tColorTraits::gray())
 314             return;
 315           else{
 316             tColorValue color = this->get_tree(v);
 317             long time = tSuper::m_time_map[v];
 318             tVertex current_node = v;
 319             while(tSuper::has_parent(current_node)){
 320               tEdge e = this->get_edge_to_parent(current_node);
 321               current_node = (color == tColorTraits::black()) ? source(e, tSuper::m_g) : target(e, tSuper::m_g);
 322               BOOST_CHECK(tSuper::m_time_map[current_node] >= time);
 323             }
 324           }
 325         }//invariant_seven
 326
 327         void invariant_eight(const tVertex& v) const{
 328           if(this->get_tree(v) == tColorTraits::gray())
 329              return;
 330           else{
 331             tColorValue color = this->get_tree(v);
 332             long time = tSuper::m_time_map[v];
 333             tDistanceVal distance = tSuper::m_dist_map[v];
 334             tVertex current_node = v;
 335             while(tSuper::has_parent(current_node)){
 336               tEdge e = this->get_edge_to_parent(current_node);
 337               current_node = (color == tColorTraits::black()) ? source(e, tSuper::m_g) : target(e, tSuper::m_g);
 338               if(tSuper::m_time_map[current_node] == time)
 339                 BOOST_CHECK(tSuper::m_dist_map[current_node] < distance);
 340             }
 341           }
 342         }//invariant_eight
 343
 344         void check_invariants(){
 345           tVertexIterator vi, v_end;
 346           for(boost::tie(vi, v_end) = vertices(tSuper::m_g); vi != v_end; ++vi){
 347             invariant_four(*vi);
 348             invariant_five(*vi);
 349             invariant_six(*vi);
 350             invariant_seven(*vi);
 351             invariant_eight(*vi);
 352           }
 353         }
 354
 355         tEdgeVal test(){
 356           this->add_active_node(this->m_sink);
 357           this->augment_direct_paths();
 358           check_invariants();
 359           //start the main-loop
 360           while(true){
 361             bool path_found;
 362             tEdge connecting_edge;
 363             boost::tie(connecting_edge, path_found) = this->grow(); //find a path from source to sink
 364             if(!path_found){
 365                 //we're finished, no more paths were found
 366               break;
 367             }
 368             check_invariants();
 369             this->m_time++;
 370             this->augment(connecting_edge); //augment that path
 371             check_invariants();
 372             this->adopt(); //rebuild search tree structure
 373             check_invariants();
 374           }
 375
 376           //check if flow is the sum of outgoing edges of src
 377           tOutEdgeIterator ei, e_end;
 378           tEdgeVal src_sum = 0;
 379           for(boost::tie(ei, e_end) = out_edges(this->m_source, this->m_g); ei != e_end; ++ei){
 380             src_sum += this->m_cap_map[*ei] - this->m_res_cap_map[*ei];
 381           }
 382           BOOST_CHECK(this->m_flow == src_sum);
 383           //check if flow is the sum of ingoing edges of sink
 384           tEdgeVal sink_sum = 0;
 385           for(boost::tie(ei, e_end) = out_edges(this->m_sink, this->m_g); ei != e_end; ++ei){
 386             tEdge in_edge = this->m_rev_edge_map[*ei];
 387             sink_sum += this->m_cap_map[in_edge] - this->m_res_cap_map[in_edge];
 388           }
 389           BOOST_CHECK(this->m_flow == sink_sum);
 390           return this->m_flow;
 391         }
 392 };
 393
 394 long test_algorithms_invariant(int n_verts, int n_edges, std::size_t seed)
 395 {
 396   typedef adjacency_list_traits<vecS, vecS, directedS> tVectorTraits;
 397   typedef adjacency_list<vecS, vecS, directedS,
 398   property<vertex_index_t, long,
 399   property<vertex_predecessor_t, tVectorTraits::edge_descriptor,
 400   property<vertex_color_t, default_color_type,
 401   property<vertex_distance_t, long> > > >,
 402   property<edge_capacity_t, long,
 403   property<edge_residual_capacity_t, long,
 404   property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
 405
 406   tVectorGraph g;
 407
 408   graph_traits<tVectorGraph>::vertex_descriptor src, sink;
 409   boost::tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
 410
 411   typedef property_map<tVectorGraph, edge_capacity_t>::type tEdgeCapMap;
 412   typedef property_map<tVectorGraph, edge_residual_capacity_t>::type tEdgeResCapMap;
 413   typedef property_map<tVectorGraph, edge_reverse_t>::type tRevEdgeMap;
 414   typedef property_map<tVectorGraph, vertex_predecessor_t>::type tVertexPredMap;
 415   typedef property_map<tVectorGraph, vertex_color_t>::type tVertexColorMap;
 416   typedef property_map<tVectorGraph, vertex_distance_t>::type tDistanceMap;
 417   typedef property_map<tVectorGraph, vertex_index_t>::type tIndexMap;
 418   typedef boykov_kolmogorov_test<
 419     tVectorGraph, tEdgeCapMap, tEdgeResCapMap, tRevEdgeMap, tVertexPredMap,
 420     tVertexColorMap, tDistanceMap, tIndexMap
 421   > tKolmo;
 422   tKolmo instance(g, src, sink);
 423   return instance.test();
 424 }
 425
 426 int test_main(int argc, char* argv[])
 427 {
 428   int n_verts = 10;
 429   int n_edges = 500;
 430   std::size_t seed = 1;
 431
 432   if (argc > 1) n_verts = lexical_cast<int>(argv[1]);
 433   if (argc > 2) n_edges = lexical_cast<int>(argv[2]);
 434   if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);
 435
 436   //we need at least 2 vertices to create src and sink in random graphs
 437   //this case is also caught in boykov_kolmogorov_max_flow
 438   if (n_verts<2)
 439     n_verts = 2;
 440
 441   // below are checks for different calls to boykov_kolmogorov_max_flow and different graph-types
 442
 443   //checks support of vecS storage
 444   long flow_vecS = test_adjacency_list_vecS(n_verts, n_edges, seed);
 445   std::cout << "vecS flow: " << flow_vecS << std::endl;
 446   //checks support of listS storage (especially problems with vertex indices)
 447   long flow_listS = test_adjacency_list_listS(n_verts, n_edges, seed);
 448   std::cout << "listS flow: " << flow_listS << std::endl;
 449   BOOST_CHECK(flow_vecS == flow_listS);
 450   //checks bundled properties
 451   long flow_bundles = test_bundled_properties(n_verts, n_edges, seed);
 452   std::cout << "bundles flow: " << flow_bundles << std::endl;
 453   BOOST_CHECK(flow_listS == flow_bundles);
 454   //checks overloads
 455   long flow_overloads = test_overloads(n_verts, n_edges, seed);
 456   std::cout << "overloads flow: " << flow_overloads << std::endl;
 457   BOOST_CHECK(flow_bundles == flow_overloads);
 458
 459   // excessive test version where Boykov-Kolmogorov's algorithm invariants are
 460   // checked
 461   long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed);
 462   std::cout << "invariants flow: " << flow_invariants << std::endl;
 463   BOOST_CHECK(flow_overloads == flow_invariants);
 464   return 0;
 465 }