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
  14 #include <boost/lexical_cast.hpp>
  15 #include <boost/random.hpp>
  16 #include <boost/graph/adjacency_list.hpp>
  17 #include <boost/graph/dijkstra_shortest_paths.hpp>
  18 #include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
  19 #include <boost/graph/properties.hpp>
  20 #include <boost/graph/random.hpp>
  21 #include <boost/test/minimal.hpp>
  22 #include <boost/graph/iteration_macros.hpp>
  23
  24 #define INITIALIZE_VERTEX 0
  25 #define DISCOVER_VERTEX 1
  26 #define EXAMINE_VERTEX 2
  27 #define EXAMINE_EDGE 3
  28 #define EDGE_RELAXED 4
  29 #define EDGE_NOT_RELAXED 5
  30 #define FINISH_VERTEX 6
  31
  32 template <typename Graph>
  33 void run_dijkstra_test(const Graph& graph)
  34 {
  35   using namespace boost;
  36
  37   // Set up property maps
  38   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  39
  40   typedef typename std::map<vertex_t, vertex_t> vertex_map_t;
  41   typedef associative_property_map<vertex_map_t> predecessor_map_t;
  42   vertex_map_t default_vertex_map, no_color_map_vertex_map;
  43   predecessor_map_t default_predecessor_map(default_vertex_map),
  44                     no_color_map_predecessor_map(no_color_map_vertex_map);
  45
  46   typedef typename std::map<vertex_t, double> vertex_double_map_t;
  47   typedef associative_property_map<vertex_double_map_t> distance_map_t;
  48   vertex_double_map_t default_vertex_double_map, no_color_map_vertex_double_map;
  49   distance_map_t default_distance_map(default_vertex_double_map),
  50                  no_color_map_distance_map(no_color_map_vertex_double_map);
  51
  52   // Run dijkstra algoirthms
  53   dijkstra_shortest_paths(graph, vertex(0, graph),
  54                           predecessor_map(default_predecessor_map)
  55                           .distance_map(default_distance_map));
  56
  57   dijkstra_shortest_paths_no_color_map(graph, vertex(0, graph),
  58                                        predecessor_map(no_color_map_predecessor_map)
  59                                        .distance_map(no_color_map_distance_map));
  60
  61   // Verify that predecessor maps are equal
  62   BOOST_CHECK(std::equal(default_vertex_map.begin(), default_vertex_map.end(),
  63               no_color_map_vertex_map.begin()));
  64
  65   // Verify that distance maps are equal
  66   BOOST_CHECK(std::equal(default_vertex_double_map.begin(), default_vertex_double_map.end(),
  67               no_color_map_vertex_double_map.begin()));
  68 }
  69
  70 int test_main(int argc, char* argv[])
  71 {
  72   using namespace boost;
  73
  74   int vertices_to_create = 10;
  75   int edges_to_create = 500;
  76   std::size_t random_seed = time(0);
  77
  78   if (argc > 1) {
  79     vertices_to_create = lexical_cast<int>(argv[1]);
  80   }
  81
  82   if (argc > 2) {
  83     edges_to_create = lexical_cast<int>(argv[2]);
  84   }
  85
  86   if (argc > 3) {
  87     random_seed = lexical_cast<std::size_t>(argv[3]);
  88   }
  89
  90   minstd_rand generator(random_seed);
  91
  92   // Set up graph
  93   typedef adjacency_list<listS, listS, directedS,
  94     property<vertex_index_t, int >,
  95     property<edge_weight_t, double> > graph_t;
  96
  97   graph_t graph;
  98   generate_random_graph(graph, vertices_to_create, edges_to_create, generator);
  99
 100   // Set up property maps
 101   typedef property_map<graph_t, vertex_index_t>::type index_map_t;
 102   index_map_t index_map = get(vertex_index, graph);
 103   int vertex_index = 0;
 104
 105   BGL_FORALL_VERTICES(current_vertex, graph, graph_t) {
 106     put(index_map, current_vertex, vertex_index++);
 107   }
 108
 109   randomize_property<edge_weight_t>(graph, generator);
 110
 111   // Run comparison test with original dijkstra_shortest_paths
 112   std::cout << "Running dijkstra shortest paths test with " << num_vertices(graph) <<
 113     " vertices and " << num_edges(graph) << " edges " << std::endl;
 114
 115   run_dijkstra_test(graph);
 116
 117   return 0;
 118 }
 119