#include <iostream>
#include <map>
#include <limits>
#include <boost/concept_check.hpp>
#include <boost/type_traits.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;

// Example coloring function provided in BGL online documentation at
// http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/constructing_algorithms.html
template <class VertexListGraph, class Order, class Color>
typename graph_traits<VertexListGraph>::vertices_size_type
sequential_vertex_color_ting (const VertexListGraph& G,
                              Order order, const Color& color) {
  typedef graph_traits<VertexListGraph> GraphTraits;
  typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
  typedef typename GraphTraits::vertices_size_type size_type;
  typedef typename property_traits<Color>::value_type ColorType;
  typedef typename property_traits<Order>::value_type OrderType;

  function_requires< VertexListGraphConcept<VertexListGraph> >();
  function_requires< ReadWritePropertyMapConcept<Color,
vertex_descriptor> >();
  function_requires< IntegerConcept<ColorType> >();
  function_requires< ReadablePropertyMapConcept<Order, size_type> >();
  BOOST_STATIC_ASSERT((is_same<OrderType, vertex_descriptor>::value));

  size_type max_color = 0;
  const size_type V = num_vertices(G);
  std::vector<size_type> mark(V,
std::numeric_limits<size_type>::max());

  typename GraphTraits::vertex_iterator v, vend;
  for (tie(v, vend) = vertices(G); v != vend ; v++) {
    color[*v] = V-1; // which means "not colored"
  }

  for (size_type i = 0 ; i < V ; i++) {
    vertex_descriptor current = order[i];

    // mark all the colors of the adjacent vertices
    typename GraphTraits::adjacency_iterator ai, aend;
    for (tie(ai, aend) = adjacent_vertices(current, G) ; ai != aend ;
++ai) {
      mark[color[*ai]] = i;
    }

    // find the smallest color unused by the adjacent vertices
    size_type smallest_color = 0;
    while (smallest_color < max_color && mark[smallest_color] == i) {
      ++smallest_color;
    }

    // if all the colors are used up, increase the number of colors
    if (smallest_color == max_color) {
      ++max_color;
    }

    color[current] = smallest_color;
  }
  return max_color;
}

int main(int, char*[]) {
  // Create adjacency matrix for a star graph on 5 vertices
  int numberOfVertices = 5;
  int adjacencyMatrix[numberOfVertices][numberOfVertices];
  for (int i = 0 ; i < numberOfVertices ; i++) {
    for (int j = 0 ; j < numberOfVertices ; j++) {
      if ((i == 0)||(j == 0)&&(i != j)) {
        adjacencyMatrix[i][j] = 1;
      } else {
        adjacencyMatrix[i][j] = 0;
      }
    }
  }

  // Construct boost graph
  typedef adjacency_matrix<undirectedS> UGraph;
  typedef graph_traits<UGraph> GraphTraits;
  typedef GraphTraits::vertex_descriptor vertex_descriptor;
  typedef GraphTraits::vertex_iterator vertex_iterator;
  UGraph ug(numberOfVertices);
  for (int i = 0 ; i < numberOfVertices ; i++) {
    for (int j = i+1 ; j < numberOfVertices ; j++) {
      if (adjacencyMatrix[i][j] == 1) {
        add_edge(i,j,ug);
      }
    }
  }

  // Create order as an externally stored property
  vertex_descriptor order[numberOfVertices];
  std::pair<vertex_iterator, vertex_iterator> p = vertices(ug);
  for (int i = 0 ; i < numberOfVertices ; i++) {
      order[i] = *(p.first + i);
  }

  // Create color as an externally stored property
  std::map<vertex_descriptor, int> color;
  for (int i = 0 ; i < numberOfVertices ; i++) {

color.insert(std::make_pair(vertex_descriptor(*(p.first+i)),int(0)));
  }

  // Get the coloring
  sequential_vertex_color_ting(ug,order,make_assoc_property_map(color));

  // Display the coloring
  for (int i = 0 ; i < numberOfVertices ; i++) {
    std::cout << "Color of vertex " << i << " is " <<
color[*(p.first+i)] << std::endl;
  }

  return 0;
}