//Copyright Leandro T. C. Melo

#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/vector_property_map.hpp>

//There're additional members to GTAD's graph_traits structure. 
//One should use the following define for compliance with BGL's graph_traits.
#define BGL_GRAPH_TRAITS_COMPLIANCE

//As opposed to the BGL, by default the GTAD doesn't guarantee, for an undirected graph,
//that a call to source(e, g) of an edge obtained via an out_edge_iterator will return 
//the vertex v used in the call out_edges(v, g). 
//The analogous behavior regarding an in_edge_iterator is not guaranteed either.
//In the GTAD, the auxiliary function opposite(e, v, g) is used for such purpose.
//However, for compliance with the BGL the following define can be used.
#define BGL_INCIDENT_EDGES_COMPLIANCE

//Category tags from the BGL are similar to the category tags from the STL.
//However, until now I have not found an actual situation where a tag dispatching 
//mechanism based on the graph/property map categories would really be necessary
//or make a significant difference. Therefore, the GTAD doesn't require such types.
//Still, for BGL compliance the following defines can be used.
#define BGL_GRAPH_CATEGORY_COMPLIANCE
#define BGL_PROPERTY_MAP_CATEGORY_COMPLIANCE

#include <GTAD/adjacency_list.h>
#include <GTAD/graph_traits.h>
#include <GTAD/bfs.h>
#include <GTAD/dfs.h>
#include <GTAD/vector_map.h>
#include <GTAD/property_map_util.h>

//Some dummy visitors for BGL.
struct bfs_bgl_visitor : public boost::default_bfs_visitor 
{
  template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
  {
    std::cout << "\nVertex: " << u;
  }  
};

struct dfs_bgl_visitor : public boost::default_dfs_visitor
{
  template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
  {
    std::cout << "\nVertex: " << u;
  }  
};

//Some dummy visitors for GTAD.
struct bfs_gtad_visitor : public gtad::null_bfs_visitor
{
  template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
  {
    std::cout << "\nVertex: " << u;
  } 
};

struct dfs_gtad_visitor : public gtad::null_dfs_visitor
{
  template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
  {
    std::cout << "\nVertex: " << u;
  } 
};


void gtad_adj_list_in_bgl_algorithm()
{
  using namespace boost;

  //Using GTAD's adjacency list in BGL's algorithms.
  typedef gtad::adjacency_list<gtad::no_parallel_edges, gtad::directed> Graph;
  typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
  typedef graph_traits<Graph>::vertices_size_type vertices_size_type;

  Graph g;//NOTE: In the GTAD, you'll get better performance initializing the 
    //graph with approximate number of vertices and edges. Ex.: Graph g(10, 50).
  vertex_descriptor v0 = add_vertex(g);
  vertex_descriptor v1 = add_vertex(g);
  vertex_descriptor v2 = add_vertex(g);
  edge_descriptor e01 = add_edge(v0, v1, g).first;
  edge_descriptor e12 = add_edge(v1, v2, g).first;
  edge_descriptor e20 = add_edge(v2, v0, g).first;

  typedef gtad::vector_map<vertex_descriptor, vertices_size_type> index_map;
  index_map im;
  gtad::make_index_map(g, im);

  vector_property_map<boost::default_color_type, index_map> cm(im);
  
  std::cout << "\nRunning BFS...";
  breadth_first_search(g, v0, visitor(bfs_bgl_visitor()).color_map(cm));

  std::cout << "\nRunning DFS...";
  depth_first_search(g, visitor(dfs_bgl_visitor()).color_map(cm));
}

void blg_adj_list_in_gtad_algorithm()
{
  using namespace gtad;

  //Using BGL's adjacency list in GTAD's algorithm.
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;
  typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
  typedef graph_traits<Graph>::vertices_size_type vertices_size_type;

  Graph g;
  vertex_descriptor v0 = add_vertex(g);
  vertex_descriptor v1 = add_vertex(g);
  vertex_descriptor v2 = add_vertex(g);
  edge_descriptor e01 = add_edge(v0, v1, g).first;
  edge_descriptor e12 = add_edge(v1, v2, g).first;
  edge_descriptor e20 = add_edge(v2, v0, g).first;

  typedef boost::vector_property_map<vertex_descriptor> ordermap;
  typedef boost::vector_property_map<vertex_descriptor> pmap;
  typedef boost::vector_property_map<vertices_size_type> dmap;
  typedef boost::vector_property_map<edge_descriptor> spmap;
  
  
  std::cout << "\nRunning BFS...";    
  typedef define_bfs<Graph, //Using named parameter's.
                     parent_map, pmap,
                     shortest_path_map, spmap,
                     simple_distance_map, dmap,
                     vertex_order_map, ordermap,
                     bfs_visitor, bfs_gtad_visitor>::type BFS;
  BFS bfs_search;
  bfs_search.set_start(v0);
  bfs_search.execute(g);

  //All propery maps are instantiated in GTAD algorithms with default_map<MapType>::value().
  //The default implementation just returns a default constructed map.
  //If other behaviour is necessary, one can specialize this class template.
  //Also, it's possible to set a semantically consistent map instance via setter methods
  //of the algorithm. For example: 
  //    bfs_search.set_parent_map(parent_map_instance);
  //    bfs_search.set_vertex_order_map(order_map_instance);

  
  std::cout << "\nRunning DFS...";
  typedef define_dfs<Graph, //Using named parameter's.
                     vertex_order_map, ordermap,
                     dfs_visitor, dfs_gtad_visitor,
                     parent_map, pmap>::type DFS;
  DFS dfs_search;
  dfs_search.execute(g);
}

int main(int argc, char* argv[])
{
  std::cout << "\nUsing GTAD's list in BGL's algorithms.";
  gtad_adj_list_in_bgl_algorithm();

  std::cout << "\n\nUsing BGL's list in GTAD's algorithms.";
  blg_adj_list_in_gtad_algorithm();

  std::cout << std::endl;
  return 0;
}