ceph/src/boost/libs/graph/test/dijkstra_no_color_map_compare.cpp

   1 //=======================================================================
   2 // Copyright 2009 Trustees of Indiana University.
   3 // Authors: Michael Hansen
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #include <iostream>
  11 #include <map>
  12 #include <vector>
  13 #include <boost/config.hpp>
  14
  15 #ifdef BOOST_MSVC
  16 // Without disabling this we get hard errors about initialialized pointers:
  17 #pragma warning(disable:4703)
  18 #endif
  19
  20 #include <boost/lexical_cast.hpp>
  21 #include <boost/random.hpp>
  22 #include <boost/graph/adjacency_list.hpp>
  23 #include <boost/graph/dijkstra_shortest_paths.hpp>
  24 #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
  25 #include <boost/graph/properties.hpp>
  26 #include <boost/graph/random.hpp>
  27 #include <boost/test/minimal.hpp>
  28 #include <boost/graph/iteration_macros.hpp>
  29
  30 #define INITIALIZE_VERTEX 0
  31 #define DISCOVER_VERTEX 1
  32 #define EXAMINE_VERTEX 2
  33 #define EXAMINE_EDGE 3
  34 #define EDGE_RELAXED 4
  35 #define EDGE_NOT_RELAXED 5
  36 #define FINISH_VERTEX 6
  37
  38
  39 template <typename Graph>
  40 void run_dijkstra_test(const Graph& graph)
  41 {
  42   using namespace boost;
  43
  44   // Set up property maps
  45   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  46
  47   typedef typename std::map<vertex_t, vertex_t> vertex_map_t;
  48   typedef associative_property_map<vertex_map_t> predecessor_map_t;
  49   vertex_map_t default_vertex_map, no_color_map_vertex_map;
  50   predecessor_map_t default_predecessor_map(default_vertex_map),
  51                     no_color_map_predecessor_map(no_color_map_vertex_map);
  52
  53   typedef typename std::map<vertex_t, double> vertex_double_map_t;
  54   typedef associative_property_map<vertex_double_map_t> distance_map_t;
  55   vertex_double_map_t default_vertex_double_map, no_color_map_vertex_double_map;
  56   distance_map_t default_distance_map(default_vertex_double_map),
  57                  no_color_map_distance_map(no_color_map_vertex_double_map);
  58
  59   // Run dijkstra algoirthms
  60   dijkstra_shortest_paths(graph, vertex(0, graph),
  61                           predecessor_map(default_predecessor_map)
  62                           .distance_map(default_distance_map));
  63
  64   dijkstra_shortest_paths_no_color_map(graph, vertex(0, graph),
  65                                        predecessor_map(no_color_map_predecessor_map)
  66                                        .distance_map(no_color_map_distance_map));
  67
  68   // Verify that predecessor maps are equal
  69   BOOST_CHECK(std::equal(default_vertex_map.begin(), default_vertex_map.end(),
  70               no_color_map_vertex_map.begin()));
  71
  72   // Verify that distance maps are equal
  73   BOOST_CHECK(std::equal(default_vertex_double_map.begin(), default_vertex_double_map.end(),
  74               no_color_map_vertex_double_map.begin()));
  75 }
  76
  77 int test_main(int argc, char* argv[])
  78 {
  79   using namespace boost;
  80
  81   int vertices_to_create = 10;
  82   int edges_to_create = 500;
  83   std::size_t random_seed = time(0);
  84
  85   if (argc > 1) {
  86     vertices_to_create = lexical_cast<int>(argv[1]);
  87   }
  88
  89   if (argc > 2) {
  90     edges_to_create = lexical_cast<int>(argv[2]);
  91   }
  92
  93   if (argc > 3) {
  94     random_seed = lexical_cast<std::size_t>(argv[3]);
  95   }
  96
  97   minstd_rand generator(random_seed);
  98
  99   // Set up graph
 100   typedef adjacency_list<listS, listS, directedS,
 101     property<vertex_index_t, int >,
 102     property<edge_weight_t, double> > graph_t;
 103
 104   graph_t graph;
 105   generate_random_graph(graph, vertices_to_create, edges_to_create, generator);
 106
 107   // Set up property maps
 108   typedef property_map<graph_t, vertex_index_t>::type index_map_t;
 109   index_map_t index_map = get(vertex_index, graph);
 110   int vertex_index = 0;
 111
 112   BGL_FORALL_VERTICES(current_vertex, graph, graph_t) {
 113     put(index_map, current_vertex, vertex_index++);
 114   }
 115
 116   randomize_property<edge_weight_t>(graph, generator);
 117
 118   // Run comparison test with original dijkstra_shortest_paths
 119   std::cout << "Running dijkstra shortest paths test with " << num_vertices(graph) <<
 120     " vertices and " << num_edges(graph) << " edges " << std::endl;
 121
 122   run_dijkstra_test(graph);
 123
 124   return 0;
 125 }
 126