| // (C) Copyright Jeremy Siek 2004 |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // From Louis Lavery <Louis@devilsChimney.co.uk> |
| /*Expected Output:- |
| A: 0 A |
| B: 11 A |
| |
| Actual Output:- |
| A: 0 A |
| B: 2147483647 B |
| */ |
| |
| #include <iostream> |
| #include <iomanip> |
| #include <boost/graph/adjacency_list.hpp> |
| #include <boost/graph/bellman_ford_shortest_paths.hpp> |
| #include <boost/cstdlib.hpp> |
| #include <boost/test/minimal.hpp> |
| |
| int test_main(int, char*[]) |
| { |
| using namespace boost; |
| |
| enum { A, B, Z }; |
| char const name[] = "ABZ"; |
| int const numVertex = static_cast<int>(Z) + 1; |
| typedef std::pair<int,int> Edge; |
| Edge edge_array[] = {Edge(B,A)}; |
| int const numEdges = sizeof(edge_array) / sizeof(Edge); |
| int const weight[numEdges] = {11}; |
| |
| typedef adjacency_list<vecS,vecS,undirectedS, |
| no_property,property<edge_weight_t,int> > Graph; |
| |
| Graph g(edge_array, edge_array + numEdges, numVertex); |
| |
| Graph::edge_iterator ei, ei_end; |
| property_map<Graph,edge_weight_t>::type |
| weight_pmap = get(edge_weight, g); |
| |
| int i = 0; |
| for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei, ++i) |
| weight_pmap[*ei] = weight[i]; |
| |
| std::vector<int> parent(numVertex); |
| for(i = 0; i < numVertex; ++i) |
| parent[i] = i; |
| |
| int inf = (std::numeric_limits<int>::max)(); |
| std::vector<int> distance(numVertex, inf); |
| distance[A] = 0; // Set source distance to zero |
| |
| bool const r = bellman_ford_shortest_paths |
| (g, int (numVertex), |
| weight_pmap, |
| &parent[0], |
| &distance[0], |
| closed_plus<int>(), |
| std::less<int>(), |
| default_bellman_visitor()); |
| |
| if (r) { |
| for(int i = 0; i < numVertex; ++i) { |
| std::cout << name[i] << ": "; |
| if (distance[i] == inf) |
| std::cout << std::setw(3) << "inf"; |
| else |
| std::cout << std::setw(3) << distance[i]; |
| std::cout << " " << name[parent[i]] << std::endl; |
| } |
| } else { |
| std::cout << "negative cycle" << std::endl; |
| } |
| |
| #if !(defined(__INTEL_COMPILER) && __INTEL_COMPILER <= 700) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300) |
| graph_traits<Graph>::vertex_descriptor s = vertex(A, g); |
| std::vector<int> parent2(numVertex); |
| std::vector<int> distance2(numVertex, 17); |
| bool const r2 = bellman_ford_shortest_paths |
| (g, |
| weight_map(weight_pmap).distance_map(&distance2[0]). |
| predecessor_map(&parent2[0]).root_vertex(s)); |
| if (r2) { |
| for(int i = 0; i < numVertex; ++i) { |
| std::cout << name[i] << ": "; |
| if (distance2[i] == inf) |
| std::cout << std::setw(3) << "inf"; |
| else |
| std::cout << std::setw(3) << distance2[i]; |
| std::cout << " " << name[parent2[i]] << std::endl; |
| } |
| } else { |
| std::cout << "negative cycle" << std::endl; |
| } |
| |
| BOOST_CHECK(r == r2); |
| if (r && r2) { |
| BOOST_CHECK(parent == parent2); |
| BOOST_CHECK(distance == distance2); |
| } |
| #endif |
| |
| return boost::exit_success; |
| } |