1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/bellman-test.cpp	Fri Jun 15 03:10:57 2012 +0200
     1.3 @@ -0,0 +1,121 @@
     1.4 +//  (C) Copyright Jeremy Siek 2004 
     1.5 +//  Distributed under the Boost Software License, Version 1.0. (See
     1.6 +//  accompanying file LICENSE_1_0.txt or copy at
     1.7 +//  http://www.boost.org/LICENSE_1_0.txt)
     1.8 +
     1.9 +// From Louis Lavery <Louis@devilsChimney.co.uk>
    1.10 +
    1.11 +/*
    1.12 + * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.
    1.13 +*/
    1.14 +
    1.15 +/*Expected Output:-
    1.16 +A:   0 A
    1.17 +B:  11 A
    1.18 +
    1.19 +Actual Output:-
    1.20 +A:   0 A
    1.21 +B: 2147483647 B
    1.22 +*/
    1.23 +
    1.24 +#include <iostream>
    1.25 +#include <iomanip>
    1.26 +#include <boost/graph/adjacency_list.hpp>
    1.27 +#include <boost/graph/bellman_ford_shortest_paths.hpp>
    1.28 +#include <boost/cstdlib.hpp>
    1.29 +#include <boost/test/minimal.hpp>
    1.30 +#ifdef __SYMBIAN32__
    1.31 +#include "std_log_result.h"
    1.32 +#define LOG_FILENAME_LINE __FILE__, __LINE__
    1.33 +#endif
    1.34 +int test_main(int, char*[])
    1.35 +{
    1.36 +  using namespace boost;
    1.37 +
    1.38 +  enum { A, B, Z };
    1.39 +  char const name[] = "ABZ";
    1.40 +  int const numVertex = static_cast<int>(Z) + 1;
    1.41 +  typedef std::pair<int,int> Edge;
    1.42 +  Edge edge_array[] = {Edge(B,A)};
    1.43 +  int const numEdges = sizeof(edge_array) / sizeof(Edge);
    1.44 +  int const weight[numEdges] = {11};
    1.45 +
    1.46 +  typedef adjacency_list<vecS,vecS,undirectedS,
    1.47 +    no_property,property<edge_weight_t,int> > Graph;
    1.48 +
    1.49 +  Graph g(edge_array, edge_array + numEdges, numVertex);
    1.50 +
    1.51 +  Graph::edge_iterator ei, ei_end;
    1.52 +  property_map<Graph,edge_weight_t>::type
    1.53 +    weight_pmap = get(edge_weight, g);
    1.54 +
    1.55 +  int i = 0;
    1.56 +  for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei, ++i)
    1.57 +    weight_pmap[*ei] = weight[i];
    1.58 +
    1.59 +  std::vector<int> parent(numVertex);
    1.60 +  for(i = 0; i < numVertex; ++i)
    1.61 +    parent[i] = i;
    1.62 +
    1.63 +  int inf = (std::numeric_limits<int>::max)();
    1.64 +  std::vector<int> distance(numVertex, inf);
    1.65 +  distance[A] = 0; // Set source distance to zero
    1.66 +
    1.67 +  bool const r = bellman_ford_shortest_paths
    1.68 +    (g, int (numVertex),
    1.69 +     weight_pmap, 
    1.70 +     &parent[0],
    1.71 +     &distance[0],
    1.72 +     closed_plus<int>(),
    1.73 +     std::less<int>(),
    1.74 +     default_bellman_visitor());
    1.75 +
    1.76 +  if (r) {
    1.77 +    for(int i = 0; i < numVertex; ++i) {
    1.78 +      std::cout << name[i] << ": ";
    1.79 +      if (distance[i] == inf)
    1.80 +        std::cout  << std::setw(3) << "inf";
    1.81 +      else
    1.82 +        std::cout << std::setw(3) << distance[i];
    1.83 +      std::cout << " " << name[parent[i]] << std::endl;
    1.84 +    }
    1.85 +  } else {
    1.86 +    std::cout << "negative cycle" << std::endl;
    1.87 +  }
    1.88 +
    1.89 +#if !(defined(__INTEL_COMPILER) && __INTEL_COMPILER <= 700) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300)
    1.90 +  graph_traits<Graph>::vertex_descriptor s = vertex(A, g);
    1.91 +  std::vector<int> parent2(numVertex);
    1.92 +  std::vector<int> distance2(numVertex, 17);
    1.93 +  bool const r2 = bellman_ford_shortest_paths
    1.94 +                    (g, 
    1.95 +                     weight_map(weight_pmap).distance_map(&distance2[0]).
    1.96 +                     predecessor_map(&parent2[0]).root_vertex(s));
    1.97 +  if (r2) {
    1.98 +    for(int i = 0; i < numVertex; ++i) {
    1.99 +      std::cout << name[i] << ": ";
   1.100 +      if (distance2[i] == inf)
   1.101 +        std::cout  << std::setw(3) << "inf";
   1.102 +      else
   1.103 +        std::cout << std::setw(3) << distance2[i];
   1.104 +      std::cout << " " << name[parent2[i]] << std::endl;
   1.105 +    }
   1.106 +  } else {
   1.107 +    std::cout << "negative cycle" << std::endl;
   1.108 +  }
   1.109 +
   1.110 +  BOOST_CHECK(r == r2);
   1.111 +  if (r && r2) {
   1.112 +    BOOST_CHECK(parent == parent2);
   1.113 +    BOOST_CHECK(distance == distance2);
   1.114 +  }
   1.115 +#endif
   1.116 +
   1.117 +  #ifdef __SYMBIAN32__
   1.118 +	std_log(LOG_FILENAME_LINE,"[End Test Case ]");
   1.119 +
   1.120 +	testResultXml("bellman-test");
   1.121 +	close_log_file();
   1.122 +#endif
   1.123 +  return boost::exit_success;
   1.124 +}