#include <boost/config.hpp>
#include <iostream>
#include <fstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

int main(int, char *[])
{
  typedef boost::property<boost::edge_weight_t, float> EdgeWeightProperty;
  typedef boost::undirected_graph<boost::no_property, EdgeWeightProperty > graph_t;
  typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
  typedef boost::graph_traits < graph_t >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;

  // Create a graph
  graph_t g;

  // Add vertices
  graph_t::vertex_descriptor v0 = g.add_vertex();
  graph_t::vertex_descriptor v1 = g.add_vertex();
  graph_t::vertex_descriptor v2 = g.add_vertex();

  // Add weighted edges
  EdgeWeightProperty weight0 = 5;
  g.add_edge(v0, v1, weight0);

  EdgeWeightProperty weight1 = 3;
  g.add_edge(v1, v2, weight1);
  
  EdgeWeightProperty weight2 = 2;
  g.add_edge(v2, v0, weight2);

  // Create things for Dijkstra
  std::vector<vertex_descriptor> p(boost::num_vertices(g));
  std::vector<int> d(boost::num_vertices(g));

  // Compute shortest paths
  boost::dijkstra_shortest_paths(g, v0, boost::predecessor_map(&p[0]).distance_map(&d[0]));

  // Output results
  std::cout << "distances and parents:" << std::endl;
  boost::graph_traits < graph_t >::vertex_iterator vi, vend;
  for (boost::tie(vi, vend) = boost::vertices(g); vi != vend; ++vi) 
  {
  //  std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
  //  std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::endl;
  }
  std::cout << std::endl;

  return EXIT_SUCCESS;
}