// Copyright (C) 2004-2008 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

// Example usage of breadth_first_search algorithm

// Enable PBGL interfaces to BGL algorithms
#include <boost/graph/use_mpi.hpp>

// Communicate via MPI
#include <boost/graph/distributed/mpi_process_group.hpp>

// Breadth-first search algorithm
#include <boost/graph/breadth_first_search.hpp>

// Distributed adjacency list
#include <boost/graph/distributed/adjacency_list.hpp>

// METIS Input
#include <boost/graph/metis.hpp>

// Graphviz Output
#include <boost/graph/distributed/graphviz.hpp>

// Standard Library includes
#include <fstream>
#include <string>
#include <boost/foreach.hpp>

#include <boost/graph/graph_utility.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>

#ifdef BOOST_NO_EXCEPTIONS
void
boost::throw_exception(std::exception const& ex)
{
    std::cout << ex.what() << std::endl;
    abort();
}
#endif

using namespace boost;
using boost::graph::distributed::mpi_process_group;


template<typename DistanceMap>
struct bfs_discovery_visitor : bfs_visitor<> 
{
  bfs_discovery_visitor(DistanceMap distance) : distance(distance) { }

  template<typename Edge, typename Graph>
  void tree_edge(Edge e, const Graph& g)
  {
    put(distance, target(e,g), get(distance, source(e,g)) + 1);
  }
  
private:
  DistanceMap distance;
};

int main(int argc, char* argv[])
{
  boost::mpi::environment env(argc,argv);

  typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, directedS,
    no_property, no_property>
  Graph;

  typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;


  // Construct graph
  int n = 6;
  typedef std::pair<int, int> E;
  E edge_array[] = { E(0, 1), E(0, 4), E(1, 2), E(2, 3), E(4, 3) };
  std::size_t num_edges = sizeof(edge_array) / sizeof(E);

  Graph g(edge_array, edge_array + num_edges, n);

  synchronize(g.process_group());

  // Define a distance map
  typedef property_map<Graph, vertex_index_t>::const_type VertexIndexMap;  
  typedef iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap> 
    DistanceMap;

  std::vector<size_t> distance_S(num_vertices(g), std::numeric_limits<size_t>::max());
  DistanceMap distance(distance_S.begin(), get(vertex_index, g));

  put(distance, vertex(0, g), 0);

  breadth_first_search(g, vertex(0, g), visitor(bfs_discovery_visitor<DistanceMap>(distance)));

  // Fetch final distances of targets of all local edges
  BGL_FORALL_EDGES(e, g, Graph) {
    request(distance, target(e,g));
  }
  synchronize(distance);

  BGL_FORALL_EDGES(e, g, Graph) {
    if (get(distance, target(e,g)) > get(distance, source(e,g)) + 1)
      std::cerr << process_id(process_group(g)) << ": distance of " << get(get(vertex_local, g), target(e, g))
		<< "@" << get(get(vertex_owner, g), target(e, g)) << " = " << get(distance, target(e, g))
		<< " (should be <= " << get(distance, source(e, g)) + 1 << ")\n";
//     assert(get(distance, target(e,g)) <= get(distance, source(e,g)) + 1);
  }

  if (process_id(process_group(g)) == 0)
    for (int i = 0; i < n; ++i)
      request(distance, vertex(i, g));

  synchronize(distance);

  if(process_id(process_group(g)) == 0) {
    std::cout << "Finished Parallel BFS " << std::endl;
    std::cout << "Node ID    :  Level " << std::endl;
    for (int i = 0; i < n; ++i) 
      std::cout << i << "  :  " << get(distance, vertex(i, g)) << " " <<std::endl;
  }

  return 0;
}