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

   1 //=======================================================================
   2 // Copyright 2013 University of Warsaw.
   3 // Authors: Piotr Wygocki
   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 #include <boost/core/lightweight_test.hpp>
  11
  12 #include <boost/graph/cycle_canceling.hpp>
  13 #include <boost/graph/edmonds_karp_max_flow.hpp>
  14
  15 #include "min_cost_max_flow_utils.hpp"
  16
  17 void cycle_canceling_def_test()
  18 {
  19     boost::SampleGraph::vertex_descriptor s, t;
  20     boost::SampleGraph::Graph g;
  21     boost::SampleGraph::getSampleGraph(g, s, t);
  22
  23     boost::edmonds_karp_max_flow(g, s, t);
  24     boost::cycle_canceling(g);
  25
  26     int cost = boost::find_flow_cost(g);
  27     BOOST_TEST_EQ(cost, 29);
  28 }
  29
  30 void path_augmentation_def_test2()
  31 {
  32     boost::SampleGraph::vertex_descriptor s, t;
  33     boost::SampleGraph::Graph g;
  34     boost::SampleGraph::getSampleGraph2(g, s, t);
  35
  36     boost::edmonds_karp_max_flow(g, s, t);
  37     boost::cycle_canceling(g);
  38
  39     int cost = boost::find_flow_cost(g);
  40     BOOST_TEST_EQ(cost, 7);
  41 }
  42
  43 void cycle_canceling_test()
  44 {
  45     boost::SampleGraph::vertex_descriptor s, t;
  46     typedef boost::SampleGraph::Graph Graph;
  47     boost::SampleGraph::Graph g;
  48     boost::SampleGraph::getSampleGraph(g, s, t);
  49
  50     int N = num_vertices(g);
  51     std::vector< int > dist(N);
  52     typedef boost::graph_traits< Graph >::edge_descriptor edge_descriptor;
  53     std::vector< edge_descriptor > pred(N);
  54
  55     boost::property_map< Graph, boost::vertex_index_t >::const_type idx
  56         = get(boost::vertex_index, g);
  57
  58     boost::edmonds_karp_max_flow(g, s, t);
  59     boost::cycle_canceling(g,
  60         boost::distance_map(
  61             boost::make_iterator_property_map(dist.begin(), idx))
  62             .predecessor_map(
  63                 boost::make_iterator_property_map(pred.begin(), idx))
  64             .vertex_index_map(idx));
  65
  66     int cost = boost::find_flow_cost(g);
  67     BOOST_TEST_EQ(cost, 29);
  68 }
  69
  70 int main()
  71 {
  72     cycle_canceling_def_test();
  73     path_augmentation_def_test2();
  74     cycle_canceling_test();
  75     return boost::report_errors();
  76 }