#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <iostream>

using namespace boost;
using namespace std;

typedef adjacency_list<vecS,
                       vecS,
                       undirectedS,
                       property<vertex_index_t, int>,
                       property<edge_index_t, int>
                       > Graph;
  
typedef std::vector< std::vector< graph_traits<Graph>::edge_descriptor > >
		embedding_storage_t;
typedef boost::iterator_property_map
		< embedding_storage_t::iterator,
		  property_map<Graph, vertex_index_t>::type
		>
		embedding_t;

struct face_output_visitor: public planar_face_traversal_visitor
{
  void begin_face() {
    std::cout << "New face: ";
  }
  
  template <typename Vertex> void next_vertex(Vertex v) {
    std::cout << v << " ";
  }
  
  void end_face() {
    std::cout << "visitor done. " << std::endl;
  }
};

int main(void) 
{
  typedef pair<int,int> Edge;
  Edge edge_array[] = {
    Edge(1,0),
    Edge(3,2),
    Edge(4,2),
    Edge(4,3),
    Edge(5,2),
    Edge(6,0),
    Edge(6,3),
    Edge(6,5),
    Edge(7,1),
    Edge(7,4),
    Edge(7,5),
    Edge(7,6),
    Edge(8,0),
    Edge(8,3),
    Edge(9,1),
    Edge(9,4),
    Edge(9,8)
  };

  Graph G(10);

  const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
  for (int i = 0; i < num_edges; ++i)
    add_edge(edge_array[i].first, edge_array[i].second, G);
  
  embedding_storage_t embedding_storage(num_vertices(G));
  embedding_t embedding(embedding_storage.begin(), get(vertex_index, G));

  if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph = G, boyer_myrvold_params::embedding = embedding)) {
    cerr << "not planar" << endl;
  }

  face_output_visitor f_vis;

  cerr << "Bug: the graph is planar and 3-connected, \n"
       << "     (in fact, it's a cube with a triangular prism attached to one face),\n"
       << "but the faces of a planar embedding are not detected." 
       << "\n\n"
       << "Output that caused the bug report:\n" 
       << "New face: 1 0 visitor done. \n"
       << "New face: 3 2 5 6 visitor done. \n"
       << "New face: 4 visitor done. \n"
       << "New face: 7 visitor done. \n"
       << "New face: 8 visitor done. \n"
       << "New face: 9 visitor done.\n"
       << "\n\n" 
       << "Output calculated now:"
       << endl;
  
  planar_face_traversal(G, &embedding[0], f_vis);

  return 0;
}