#include <iostream>
#include <utility>
#include <vector>

#include <boost/foreach.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/make_maximal_planar.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/make_connected.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
//#include <boost/graph/topological_sort.hpp>

# define foreach BOOST_FOREACH

using namespace boost;

namespace fag
{
  struct point
  {
    point() { }
    point(int x_, int y_, int v_) : x(x_), y(y_), v(v_) { }

    int x;
    int y;
    int v;
  };

  struct edge
  {
    edge() : is_road(false) { }

    bool is_road;
  };

  template <typename G>
    void print_graph(const G& g)
    {
      typedef typename graph_traits<G>::edge_descriptor edge_t;
      typedef typename graph_traits<G>::vertex_descriptor vertex_t;

      std::cout << "Vertices : " << std::endl;
      foreach (vertex_t p, vertices(g))
	std::cout << p << " : (" << g[p].x << ", " << g[p].y << ", " << g[p].v << ")" << std::endl;

      std::cout << std::endl
	<< "Edges : " << std::endl;

      foreach (edge_t e, edges(g))
	std::cout << e << " : (is_road : " << g[e].is_road << ")" << std::endl;
    }
}

int main()
{
  //typedef adjacency_list< vecS, vecS, bidirectionalS, fag::point, fag::edge > graph_t;
  typedef adjacency_list< vecS, vecS, undirectedS, property< vertex_index_t, std::pair<int, int> >, property<edge_index_t, int> > graph_t;
  typedef graph_traits<graph_t>::edge_descriptor edge_t;
  typedef graph_traits<graph_t>::vertex_descriptor vertex_t;

  graph_t g;

#if 0
  vertex_t v = add_vertex(g);
  g[v] = fag::point(0, 0, 10);
  v = add_vertex(g);
  g[v] = fag::point(10, 0, 20);
  v = add_vertex(g);
  g[v] = fag::point(5, 10, 20);
#else
  add_vertex(std::make_pair(0, 0), g);
  add_vertex(std::make_pair(10, 0), g);
  add_vertex(std::make_pair(5, 10), g);
#endif

  add_edge(0, 1, g);
  add_edge(0, 2, g);
  add_edge(1, 2, g);

  //add_vertex(std::make_pair(5, 5), g);
  add_vertex(std::make_pair(5, 5), g);
  add_vertex(std::make_pair(0, 5), g);
  //add_edge(0, 3, g);
  //add_edge(1, 3, g);

  //Initialize the interior edge index
  property_map<graph_t, edge_index_t>::type e_index = get(edge_index, g);
  graph_traits<graph_t>::edges_size_type edge_count = 0;
  graph_traits<graph_t>::edge_iterator ei, ei_end;
  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    put(e_index, *ei, edge_count++);

  std::cout << "Before : " << std::endl;
  boost::print_graph(g);

#if 0
  typedef std::vector<edge_t> edge_list_t;
  std::vector<edge_list_t> embedding(num_vertices(g));
  boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
#endif

  typedef std::vector< edge_t > edge_list_t;
  std::vector<edge_list_t> embedding(num_vertices(g));

  // 1 - Make the graph connected
  boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
  edge_count = 0;
  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    put(e_index, *ei, edge_count++);
  make_connected(g);
  std::cout << "After make_connected : " << std::endl;
  boost::print_graph(g);

  // 2 - Make the graph biconnected
  boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
  edge_count = 0;
  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    put(e_index, *ei, edge_count++);
  make_biconnected_planar(g, &embedding[0]);
  std::cout << "After make_biconnected_planar : " << std::endl;
  boost::print_graph(g);

  // 3 - Make the graph maximal planar
  boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding[0]);
  edge_count = 0;
  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    put(e_index, *ei, edge_count++);
  make_maximal_planar(g, &embedding[0]);
  std::cout << "After make_maximal_planar : " << std::endl;
  boost::print_graph(g);

  //edge_count = 0;
  //for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
  //  put(e_index, *ei, edge_count++);
  //boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding);
  //make_maximal_planar(g, embedding);
}