#include <ctime>
#include <iostream>
#include <vector>

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/random.hpp>
#include <boost/random.hpp>

using namespace std;
using namespace boost;
// using namespace boost::random;

typedef adjacency_list < vecS, vecS, undirectedS, no_property,
			 property < edge_weight_t, double > > Graph;

unsigned dummy = 0;

struct dummy_event_visitor : public base_visitor<dummy_event_visitor> {
  typedef on_examine_vertex event_filter;
  template<typename V, typename G> void operator()(V v, G g) { ++dummy; }
};

struct dummy_dijkstra_visitor : public default_dijkstra_visitor {
  template<typename V, typename G> void examine_vertex(V v, G g) { ++dummy; }
};

int main() {
  clock_t c1, c2, c3, c4;
  Graph g;
  mt19937 intrnd;
  uniform_01<mt19937> realrnd(intrnd);
  cout << "Generating random graph..." << endl;
  generate_random_graph(g, 1000, 5000, intrnd);
  cout << "Choosing random edge weights..." << endl;
  randomize_property<edge_weight_t>(g, realrnd);

  vector<double> dist(num_vertices(g));
  property_map<Graph, vertex_index_t>::type indices=get(vertex_index_t(), g);

  c1=clock();
  cout << "Starting 1st Dijkstra... " ;
  dijkstra_shortest_paths(g, vertex(0, g),
	distance_map(make_iterator_property_map(dist.begin(), indices)));
  cout << dist[2] << endl;

  c2=clock();
  cout << "Starting 2nd Dijkstra... ";
  dummy_dijkstra_visitor dv;
  dijkstra_shortest_paths(g, vertex(0, g), visitor(dv).
	distance_map(make_iterator_property_map(dist.begin(), indices)));
  cout << dist[2] << endl;

  c3=clock();
  cout << "Starting 3rd Dijkstra... ";
  dummy_event_visitor ev;
  dijkstra_shortest_paths(g, vertex(0, g),
	visitor(make_dijkstra_visitor(ev)).
	distance_map(make_iterator_property_map(dist.begin(), indices)));
  cout << dist[2] << endl;

  c4=clock();
  cout << "Without any visitor:   " << (c2-c1) << endl;
  cout << "With dijkstra visitor: " << (c3-c2) << endl;
  cout << "With event visitor:    " << (c4-c3) << endl;
}