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 | |
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(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 | |