#include <iostream>

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

#include <boost/test/minimal.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                              boost::property<boost::vertex_name_t, int,
                                              boost::property<boost::vertex_index_t, int> >,
                              boost::property<boost::edge_index_t, int> > graph_t;

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

typedef boost::property_map<graph_t, boost::vertex_name_t>::type name_map_t;
typedef boost::property_map<graph_t, boost::vertex_index_t>::type vertex_index_map_t;
typedef boost::property_map<graph_t, boost::edge_index_t>::type edge_index_map_t;

typedef std::vector<edge_t> vec_t;

#define DEBUG

struct face_visitor : public boost::planar_face_traversal_visitor
{
  face_visitor( name_map_t name_map, std::vector<std::vector<int> > & cycles )
    : name_map_( name_map ),
      cycles_( cycles )
  {
  }

  void begin_face()
  {
    cycle.clear();
#ifdef DEBUG
    std::cout << "face: ";
#endif
  }

  void end_face()
  {
    cycles_.push_back( std::vector<int>() );
    std::swap( cycles_.back(), cycle );
#ifdef DEBUG
    std::cout << "\n";
#endif
  }

  template <typename Vertex>
  void next_vertex( Vertex v )
  {
    cycle.push_back( name_map_[v] );
#ifdef DEBUG
    std::cout << "v" << v << " ";
#endif
  }

  template <typename Edge>
  void next_edge( Edge e )
  {
#ifdef DEBUG
    std::cout << "e" << e << " ";
#endif
  }

  name_map_t name_map_;
  std::vector<int> cycle;
  std::vector<std::vector<int> > & cycles_;
};


void test_planar()
{
  graph_t g( 22 );

  boost::add_edge( 0, 12, g );
  boost::add_edge( 0, 16, g );

  boost::add_edge( 1, 13, g );
  boost::add_edge( 1, 15, g );

  boost::add_edge( 2, 3, g );
  boost::add_edge( 2, 4, g );
  boost::add_edge( 2, 20, g );

  boost::add_edge( 3, 5, g );
  boost::add_edge( 3, 21, g );

  boost::add_edge( 4, 5, g );
  boost::add_edge( 4, 6, g );

  boost::add_edge( 5, 7, g );

  boost::add_edge( 6, 7, g );
  boost::add_edge( 6, 8, g );

  boost::add_edge( 7, 9, g );

  boost::add_edge( 8, 9, g );
  boost::add_edge( 8, 10, g );

  boost::add_edge( 9, 11, g );

  boost::add_edge( 10, 11, g );
  boost::add_edge( 10, 13, g );

  boost::add_edge( 11, 14, g );

  boost::add_edge( 12, 17, g );

  boost::add_edge( 13, 14, g );

  boost::add_edge( 14, 15, g );

  boost::add_edge( 16, 17, g );
  boost::add_edge( 16, 18, g );

  boost::add_edge( 17, 19, g );

  boost::add_edge( 18, 19, g );
  boost::add_edge( 18, 20, g );

  boost::add_edge( 19, 21, g );

  boost::add_edge( 20, 21, g );

  name_map_t name_map = boost::get( boost::vertex_name, g );
  vertex_index_map_t index_map = boost::get( boost::vertex_index, g );

  boost::graph_traits<graph_t>::vertices_size_type vertex_count = 0;
  boost::graph_traits<graph_t>::vertex_iterator vi, vi_end;
  for ( boost::tie( vi, vi_end ) = boost::vertices( g ); vi != vi_end; ++vi )
    boost::put( name_map, *vi, vertex_count++ );

#ifdef DEBUG
  boost::print_graph( g, index_map );
#endif

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

  std::vector<vec_t> embedding( boost::num_vertices( g ) );
  bool planar = boost::boyer_myrvold_planarity_test( boost::boyer_myrvold_params::graph = g,
                                                     boost::boyer_myrvold_params::embedding = &embedding[0] );
  BOOST_CHECK( planar );

#ifdef DEBUG
  for ( std::vector<vec_t>::iterator i=embedding.begin(); i!=embedding.end(); ++i )
  {
    vec_t & e = *i;
    std::copy( e.begin(), e.end(), std::ostream_iterator<edge_t>( std::cout, " " ) );
    std::cout << "\n";
  }
#endif

  std::vector<std::vector<int> > cycles;

  face_visitor vis( name_map, cycles );
  boost::planar_face_traversal( g, &embedding[0], vis );

  BOOST_CHECK( cycles.size() == 11 );

  for ( std::vector<std::vector<int> >::iterator i=cycles.begin(); i!=cycles.end(); ++i )
  {
    std::vector<int> & c = *i;
    BOOST_CHECK( c.size() == 4 or c.size() == 22 );
#ifdef DEBUG
    std::copy( c.begin(), c.end(), std::ostream_iterator<int>( std::cout, " " ) );
    std::cout << "\n";
#endif
  }
}

int test_main( int, char*[] )
{
  test_planar();

  return 0;
}