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