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/successive_shortest_path_nonnegative_weights.hpp>
13#include <boost/graph/find_flow_cost.hpp>
14
15#include "min_cost_max_flow_utils.hpp"
16
17void path_augmentation_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::successive_shortest_path_nonnegative_weights(g, s, t);
24
25 int cost = boost::find_flow_cost(g);
26 BOOST_TEST_EQ(cost, 29);
27}
28
29void path_augmentation_def_test2()
30{
31 boost::SampleGraph::vertex_descriptor s, t;
32 boost::SampleGraph::Graph g;
33 boost::SampleGraph::getSampleGraph2(g, s, t);
34
35 boost::successive_shortest_path_nonnegative_weights(g, s, t);
36
37 int cost = boost::find_flow_cost(g);
38 BOOST_TEST_EQ(cost, 7);
39}
40
41void path_augmentation_test()
42{
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_: 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 idx
55 = get(p: boost::vertex_index, g);
56
57 boost::successive_shortest_path_nonnegative_weights(g, s, t,
58 params: boost::distance_map(
59 p: boost::make_iterator_property_map(iter: dist.begin(), id: idx))
60 .predecessor_map(
61 p: boost::make_iterator_property_map(iter: pred.begin(), id: idx))
62 .distance_map2(
63 p: boost::make_iterator_property_map(iter: dist_prev.begin(), id: idx))
64 .vertex_index_map(p: idx));
65
66 int cost = boost::find_flow_cost(g);
67 BOOST_TEST_EQ(cost, 29);
68}
69
70int main()
71{
72 path_augmentation_def_test();
73 path_augmentation_def_test2();
74 path_augmentation_test();
75 return boost::report_errors();
76}
77

source code of boost/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp