#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/planar_face_traversal.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 std::vector<edge_t> vec_t;


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( const std::string& filename )
{
  std::ifstream in( filename.c_str() );
  BOOST_REQUIRE( in );

  graph_t g;
  boost::dynamic_properties dp;
  dp.property( "label", boost::get( boost::vertex_name, g ) );
  BOOST_CHECK( boost::read_graphviz( in, g, dp, "label" ) );

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

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

  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
  }

  std::ofstream out( "side-graph-copy.dot" );
  boost::write_graphviz( out, g );
}

int test_main( int, char*[] )
{
  test_planar( "side-graph.dot" );

  return 0;
}