1// (C) Copyright Jeremy Siek 2004
2// Distributed under the Boost Software License, Version 1.0. (See
3// accompanying file LICENSE_1_0.txt or copy at
4// http://www.boost.org/LICENSE_1_0.txt)
5
6// From Louis Lavery <Louis@devilsChimney.co.uk>
7/*Expected Output:-
8A: 0 A
9B: 11 A
10
11Actual Output:-
12A: 0 A
13B: 2147483647 B
14*/
15
16#include <iostream>
17#include <iomanip>
18#include <boost/graph/adjacency_list.hpp>
19#include <boost/graph/bellman_ford_shortest_paths.hpp>
20#include <boost/cstdlib.hpp>
21#include <boost/core/lightweight_test.hpp>
22
23int main(int, char*[])
24{
25 using namespace boost;
26
27 enum
28 {
29 A,
30 B,
31 Z
32 };
33 char const name[] = "ABZ";
34 int const numVertex = static_cast< int >(Z) + 1;
35 typedef std::pair< int, int > Edge;
36 Edge edge_array[] = { Edge(B, A) };
37 int const numEdges = sizeof(edge_array) / sizeof(Edge);
38 int const weight[numEdges] = { 11 };
39
40 typedef adjacency_list< vecS, vecS, undirectedS, no_property,
41 property< edge_weight_t, int > >
42 Graph;
43
44 Graph g(edge_array, edge_array + numEdges, numVertex);
45
46 Graph::edge_iterator ei, ei_end;
47 property_map< Graph, edge_weight_t >::type weight_pmap
48 = get(p: edge_weight, g);
49
50 int i = 0;
51 for (boost::tie(t0&: ei, t1&: ei_end) = edges(g_: g); ei != ei_end; ++ei, ++i)
52 weight_pmap[*ei] = weight[i];
53
54 std::vector< int > parent(numVertex);
55 for (i = 0; i < numVertex; ++i)
56 parent[i] = i;
57
58 int inf = (std::numeric_limits< int >::max)();
59 std::vector< int > distance(numVertex, inf);
60 distance[A] = 0; // Set source distance to zero
61
62 bool const r = bellman_ford_shortest_paths(g, N: int(numVertex), weight: weight_pmap,
63 pred: boost::make_iterator_property_map(
64 iter: parent.begin(), id: get(p: boost::vertex_index, g)),
65 distance: boost::make_iterator_property_map(
66 iter: distance.begin(), id: get(p: boost::vertex_index, g)),
67 combine: closed_plus< int >(), compare: std::less< int >(), v: default_bellman_visitor());
68
69 if (r)
70 {
71 for (int i = 0; i < numVertex; ++i)
72 {
73 std::cout << name[i] << ": ";
74 if (distance[i] == inf)
75 std::cout << std::setw(3) << "inf";
76 else
77 std::cout << std::setw(3) << distance[i];
78 std::cout << " " << name[parent[i]] << std::endl;
79 }
80 }
81 else
82 {
83 std::cout << "negative cycle" << std::endl;
84 }
85
86#if !(defined(__INTEL_COMPILER) && __INTEL_COMPILER <= 700) \
87 && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300)
88 graph_traits< Graph >::vertex_descriptor s = vertex(n: A, g);
89 std::vector< int > parent2(numVertex);
90 std::vector< int > distance2(numVertex, 17);
91 bool const r2 = bellman_ford_shortest_paths(g,
92 params: weight_map(p: weight_pmap)
93 .distance_map(p: boost::make_iterator_property_map(
94 iter: distance2.begin(), id: get(p: boost::vertex_index, g)))
95 .predecessor_map(p: boost::make_iterator_property_map(
96 iter: parent2.begin(), id: get(p: boost::vertex_index, g)))
97 .root_vertex(p: s));
98 if (r2)
99 {
100 for (int i = 0; i < numVertex; ++i)
101 {
102 std::cout << name[i] << ": ";
103 if (distance2[i] == inf)
104 std::cout << std::setw(3) << "inf";
105 else
106 std::cout << std::setw(3) << distance2[i];
107 std::cout << " " << name[parent2[i]] << std::endl;
108 }
109 }
110 else
111 {
112 std::cout << "negative cycle" << std::endl;
113 }
114
115 BOOST_TEST(r == r2);
116 if (r && r2)
117 {
118 BOOST_TEST(parent == parent2);
119 BOOST_TEST(distance == distance2);
120 }
121#endif
122
123 return boost::report_errors();
124}
125

source code of boost/libs/graph/test/bellman-test.cpp