boost_1_45_0/libs/graph/test/dijkstra_no_color_map_compare.cpp

//=======================================================================
// Copyright 2009 Trustees of Indiana University.
// Authors: Michael Hansen
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#include <iostream>
#include <map>
#include <vector>

#include <boost/lexical_cast.hpp>
#include <boost/random.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/random.hpp>
#include <boost/test/minimal.hpp>
#include <boost/graph/iteration_macros.hpp>

#define INITIALIZE_VERTEX 0
#define DISCOVER_VERTEX 1
#define EXAMINE_VERTEX 2
#define EXAMINE_EDGE 3
#define EDGE_RELAXED 4
#define EDGE_NOT_RELAXED 5
#define FINISH_VERTEX 6

template <typename Graph>
void run_dijkstra_test(const Graph& graph)
{
  using namespace boost;
  
  // Set up property maps
  typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  
  typedef typename std::map<vertex_t, vertex_t> vertex_map_t;
  typedef associative_property_map<vertex_map_t> predecessor_map_t;
  vertex_map_t default_vertex_map, no_color_map_vertex_map;
  predecessor_map_t default_predecessor_map(default_vertex_map),
                    no_color_map_predecessor_map(no_color_map_vertex_map);

  typedef typename std::map<vertex_t, double> vertex_double_map_t;
  typedef associative_property_map<vertex_double_map_t> distance_map_t;
  vertex_double_map_t default_vertex_double_map, no_color_map_vertex_double_map;
  distance_map_t default_distance_map(default_vertex_double_map),
                 no_color_map_distance_map(no_color_map_vertex_double_map);

  // Run dijkstra algoirthms
  dijkstra_shortest_paths(graph, vertex(0, graph),
                          predecessor_map(default_predecessor_map)
                          .distance_map(default_distance_map));
                                       
  dijkstra_shortest_paths_no_color_map(graph, vertex(0, graph),
                                       predecessor_map(no_color_map_predecessor_map)
                                       .distance_map(no_color_map_distance_map));

  // Verify that predecessor maps are equal
  BOOST_CHECK(std::equal(default_vertex_map.begin(), default_vertex_map.end(),
              no_color_map_vertex_map.begin()));

  // Verify that distance maps are equal
  BOOST_CHECK(std::equal(default_vertex_double_map.begin(), default_vertex_double_map.end(),
              no_color_map_vertex_double_map.begin()));
}

int test_main(int argc, char* argv[])
{
  using namespace boost;

  int vertices_to_create = 10; 
  int edges_to_create = 500;
  std::size_t random_seed = time(0);
  
  if (argc > 1) {
    vertices_to_create = lexical_cast<int>(argv[1]);
  }
  
  if (argc > 2) {
    edges_to_create = lexical_cast<int>(argv[2]);
  }
  
  if (argc > 3) {
    random_seed = lexical_cast<std::size_t>(argv[3]);
  }

  minstd_rand generator(random_seed);

  // Set up graph
  typedef adjacency_list<listS, listS, directedS,
    property<vertex_index_t, int >,
    property<edge_weight_t, double> > graph_t;

  typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
  typedef graph_traits<graph_t>::edge_descriptor edge_t;

  graph_t graph;  
  generate_random_graph(graph, vertices_to_create, edges_to_create, generator);

  // Set up property maps
  typedef property_map<graph_t, vertex_index_t>::type index_map_t;
  index_map_t index_map = get(vertex_index, graph);
  int vertex_index = 0;

  BGL_FORALL_VERTICES(current_vertex, graph, graph_t) {
    put(index_map, current_vertex, vertex_index++);
  }

  typedef property_map<graph_t, edge_weight_t>::type weight_map_t;
  weight_map_t weight_map = get(edge_weight, graph);
  randomize_property<edge_weight_t>(graph, generator);

  // Run comparison test with original dijkstra_shortest_paths
  std::cout << "Running dijkstra shortest paths test with " << num_vertices(graph) <<
    " vertices and " << num_edges(graph) << " edges " << std::endl;
    
  run_dijkstra_test(graph);

  return 0;
}