//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
//
// Distributed under 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)
//=======================================================================

// changed by me :-)

#include <boost/config.hpp>

#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>

#include <boost/graph/visitors.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/copy.hpp>
#include "bfs_distmap_as_color_map.hpp"

using namespace boost;
int main(int , char* []) 
{
  typedef boost::adjacency_list< 
    boost::mapS, boost::vecS, boost::bidirectionalS,
    boost::property<boost::vertex_color_t, boost::default_color_type,
        boost::property<boost::vertex_degree_t, int,
          boost::property<boost::vertex_in_degree_t, int,
    boost::property<boost::vertex_out_degree_t, int> > > >
  > Graph;
  
  Graph G(5);
  boost::add_edge(0, 2, G);
  boost::add_edge(1, 1, G);
  boost::add_edge(1, 3, G);
  boost::add_edge(1, 4, G);
  boost::add_edge(2, 1, G);
  boost::add_edge(2, 3, G);
  boost::add_edge(2, 4, G);
  boost::add_edge(3, 1, G);
  boost::add_edge(3, 4, G);
  boost::add_edge(4, 0, G);
  boost::add_edge(4, 1, G);

  typedef Graph::vertex_descriptor Vertex;

  Graph G_copy(5);
  // Array to store predecessor (parent) of each vertex. This will be
  // used as a Decorator (actually, its iterator will be).
  std::vector<Vertex> p(boost::num_vertices(G));
  // VC++ version of std::vector has no ::pointer, so
  // I use ::value_type* instead.
  typedef std::vector<Vertex>::value_type* Piter;

  // Array to store distances from the source to each vertex .  We use
  // a built-in array here just for variety. This will also be used as
  // a Decorator.  
  boost::graph_traits<Graph>::vertices_size_type d[5];
  std::fill_n(d, 5, -1);

  // map
  MapAsColorMap<Graph, boost::graph_traits<Graph>::vertices_size_type[], int>
   colormap(d, -1);
  
  // The source vertex
  Vertex s = *(boost::vertices(G).first);
  d[s] = 0;
  p[s] = s;
  boost::breadth_first_search
    (G, s, 
     boost::visitor(boost::make_bfs_visitor
     (std::make_pair(boost::record_distances(d, boost::on_tree_edge()),
                     std::make_pair
                     (boost::record_predecessors(&p[0], 
                                                 boost::on_tree_edge()),
                      copy_graph(G_copy, boost::on_examine_edge())))) )
      .color_map(colormap)
                      );

  boost::print_graph(G);
  boost::print_graph(G_copy);

  if (boost::num_vertices(G) < 11) {
    std::cout << "distances: ";
#ifdef BOOST_OLD_STREAM_ITERATORS
    std::copy(d, d + 5, std::ostream_iterator<int, char>(std::cout, " "));
#else
    std::copy(d, d + 5, std::ostream_iterator<int>(std::cout, " "));
#endif
    std::cout << std::endl;

    std::for_each(boost::vertices(G).first, boost::vertices(G).second, 
                  print_parent<Piter>(&p[0]));
  }

  return 0;