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 

     8 /*

     9  * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

    10 */

    11 

    12 /*Expected Output:-

    13 A:   0 A

    14 B:  11 A

    15 

    16 Actual Output:-

    17 A:   0 A

    18 B: 2147483647 B

    19 */

    20 

    21 #include <iostream>

    22 #include <iomanip>

    23 #include <boost/graph/adjacency_list.hpp>

    24 #include <boost/graph/bellman_ford_shortest_paths.hpp>

    25 #include <boost/cstdlib.hpp>

    26 #include <boost/test/minimal.hpp>

    27 #ifdef __SYMBIAN32__

    28 #include "std_log_result.h"

    29 #define LOG_FILENAME_LINE __FILE__, __LINE__

    30 #endif

    31 int test_main(int, char*[])

    32 {

    33   using namespace boost;

    34 

    35   enum { A, B, Z };

    36   char const name[] = "ABZ";

    37   int const numVertex = static_cast<int>(Z) + 1;

    38   typedef std::pair<int,int> Edge;

    39   Edge edge_array[] = {Edge(B,A)};

    40   int const numEdges = sizeof(edge_array) / sizeof(Edge);

    41   int const weight[numEdges] = {11};

    42 

    43   typedef adjacency_list<vecS,vecS,undirectedS,

    44     no_property,property<edge_weight_t,int> > Graph;

    45 

    46   Graph g(edge_array, edge_array + numEdges, numVertex);

    47 

    48   Graph::edge_iterator ei, ei_end;

    49   property_map<Graph,edge_weight_t>::type

    50     weight_pmap = get(edge_weight, g);

    51 

    52   int i = 0;

    53   for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei, ++i)

    54     weight_pmap[*ei] = weight[i];

    55 

    56   std::vector<int> parent(numVertex);

    57   for(i = 0; i < numVertex; ++i)

    58     parent[i] = i;

    59 

    60   int inf = (std::numeric_limits<int>::max)();

    61   std::vector<int> distance(numVertex, inf);

    62   distance[A] = 0; // Set source distance to zero

    63 

    64   bool const r = bellman_ford_shortest_paths

    65     (g, int (numVertex),

    66      weight_pmap, 

    67      &parent[0],

    68      &distance[0],

    69      closed_plus<int>(),

    70      std::less<int>(),

    71      default_bellman_visitor());

    72 

    73   if (r) {

    74     for(int i = 0; i < numVertex; ++i) {

    75       std::cout << name[i] << ": ";

    76       if (distance[i] == inf)

    77         std::cout  << std::setw(3) << "inf";

    78       else

    79         std::cout << std::setw(3) << distance[i];

    80       std::cout << " " << name[parent[i]] << std::endl;

    81     }

    82   } else {

    83     std::cout << "negative cycle" << std::endl;

    84   }

    85 

    86 #if !(defined(__INTEL_COMPILER) && __INTEL_COMPILER <= 700) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300)

    87   graph_traits<Graph>::vertex_descriptor s = vertex(A, g);

    88   std::vector<int> parent2(numVertex);

    89   std::vector<int> distance2(numVertex, 17);

    90   bool const r2 = bellman_ford_shortest_paths

    91                     (g, 

    92                      weight_map(weight_pmap).distance_map(&distance2[0]).

    93                      predecessor_map(&parent2[0]).root_vertex(s));

    94   if (r2) {

    95     for(int i = 0; i < numVertex; ++i) {

    96       std::cout << name[i] << ": ";

    97       if (distance2[i] == inf)

    98         std::cout  << std::setw(3) << "inf";

    99       else

   100         std::cout << std::setw(3) << distance2[i];

   101       std::cout << " " << name[parent2[i]] << std::endl;

   102     }

   103   } else {

   104     std::cout << "negative cycle" << std::endl;

   105   }

   106 

   107   BOOST_CHECK(r == r2);

   108   if (r && r2) {

   109     BOOST_CHECK(parent == parent2);

   110     BOOST_CHECK(distance == distance2);

   111   }

   112 #endif

   113 

   114   #ifdef __SYMBIAN32__

   115 	std_log(LOG_FILENAME_LINE,"[End Test Case ]");

   116 

   117 	testResultXml("bellman-test");

   118 	close_log_file();

   119 #endif

   120   return boost::exit_success;

   121 }