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:-
8 A: 0 A
9 B: 11 A
10
11 Actual Output:-
12 A: 0 A
13 B: 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
main(int,char * [])23 int 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(edge_weight, g);
49
50 int i = 0;
51 for (boost::tie(ei, ei_end) = edges(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, int(numVertex), weight_pmap,
63 boost::make_iterator_property_map(
64 parent.begin(), get(boost::vertex_index, g)),
65 boost::make_iterator_property_map(
66 distance.begin(), get(boost::vertex_index, g)),
67 closed_plus< int >(), std::less< int >(), 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(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 weight_map(weight_pmap)
93 .distance_map(boost::make_iterator_property_map(
94 distance2.begin(), get(boost::vertex_index, g)))
95 .predecessor_map(boost::make_iterator_property_map(
96 parent2.begin(), get(boost::vertex_index, g)))
97 .root_vertex(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