ceph/src/boost/libs/graph/test/successive_shortest_path_nonnegative_weights_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 #define BOOST_TEST_MODULE successive_shortest_path_nonnegative_weights_test
  11
  12 #include <boost/test/unit_test.hpp>
  13
  14 #include <boost/graph/successive_shortest_path_nonnegative_weights.hpp>
  15 #include <boost/graph/find_flow_cost.hpp>
  16
  17 #include "min_cost_max_flow_utils.hpp"
  18
  19
  20 BOOST_AUTO_TEST_CASE(path_augmentation_def_test) {
  21     boost::SampleGraph::vertex_descriptor s,t;
  22     boost::SampleGraph::Graph g;
  23     boost::SampleGraph::getSampleGraph(g, s, t);
  24
  25     boost::successive_shortest_path_nonnegative_weights(g, s, t);
  26
  27     int cost =  boost::find_flow_cost(g);
  28     BOOST_CHECK_EQUAL(cost, 29);
  29 }
  30
  31 BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
  32     boost::SampleGraph::vertex_descriptor s,t;
  33     boost::SampleGraph::Graph g;
  34     boost::SampleGraph::getSampleGraph2(g, s, t);
  35
  36     boost::successive_shortest_path_nonnegative_weights(g, s, t);
  37
  38     int cost =  boost::find_flow_cost(g);
  39     BOOST_CHECK_EQUAL(cost, 7);
  40 }
  41
  42 BOOST_AUTO_TEST_CASE(path_augmentation_test) {
  43     boost::SampleGraph::vertex_descriptor s,t;
  44     typedef boost::SampleGraph::Graph Graph;
  45     Graph g;
  46     boost::SampleGraph::getSampleGraph(g, s, t);
  47
  48     int N = boost::num_vertices(g);
  49     std::vector<int> dist(N);
  50     std::vector<int> dist_prev(N);
  51     typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
  52     std::vector<edge_descriptor> pred(N);
  53
  54     boost::property_map<Graph, boost::vertex_index_t>::const_type
  55       idx = get(boost::vertex_index, g);
  56
  57     boost::successive_shortest_path_nonnegative_weights(g, s, t,
  58             boost::distance_map(boost::make_iterator_property_map(dist.begin(), idx)).
  59             predecessor_map(boost::make_iterator_property_map(pred.begin(), idx)).
  60             distance_map2(boost::make_iterator_property_map(dist_prev.begin(), idx)).
  61             vertex_index_map(idx));
  62
  63     int cost =  boost::find_flow_cost(g);
  64     BOOST_CHECK_EQUAL(cost, 29);
  65 }
  66
  67