//=======================================================================

// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

// Copyright 2004, 2005 Trustees of Indiana University

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,

//          Doug Gregor, D. Kevin McGrath

//

// 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)

//=======================================================================

#ifndef BOOST_GRAPH_CUTHILL_MCKEE_HPP

#define BOOST_GRAPH_CUTHILL_MCKEE_HPP

#include <boost/config.hpp>

#include <boost/graph/detail/sparse_ordering.hpp>

#include <algorithm>

/*

  (Reverse) Cuthill-McKee Algorithm for matrix reordering

*/

namespace boost {

  namespace detail {

    template < typename OutputIterator, typename Buffer, typename DegreeMap > 

    class bfs_rcm_visitor:public default_bfs_visitor

    {

    public:

      bfs_rcm_visitor(OutputIterator *iter, Buffer *b, DegreeMap deg): 

        permutation(iter), Qptr(b), degree(deg) { }

      template <class Vertex, class Graph>

      void examine_vertex(Vertex u, Graph&) {

        *(*permutation)++ = u;

        index_begin = Qptr->size();

      }

      template <class Vertex, class Graph>

      void finish_vertex(Vertex, Graph&) {

        using std::sort;

        typedef typename property_traits<DegreeMap>::value_type ds_type;

        typedef indirect_cmp<DegreeMap, std::less<ds_type> > Compare;

        Compare comp(degree);

        sort(Qptr->begin()+index_begin, Qptr->end(), comp);

      }

    protected:

      OutputIterator *permutation;

      int index_begin;

      Buffer *Qptr;

      DegreeMap degree;

    };

  } // namespace detail  

  // Reverse Cuthill-McKee algorithm with a given starting Vertex.

  //

  // If user provides a reverse iterator, this will be a reverse-cuthill-mckee

  // algorithm, otherwise it will be a standard CM algorithm

  template <class Graph, class OutputIterator,

            class ColorMap, class DegreeMap>

  OutputIterator

  cuthill_mckee_ordering(const Graph& g,

                         std::deque< typename

                         graph_traits<Graph>::vertex_descriptor > vertex_queue,

                         OutputIterator permutation, 

                         ColorMap color, DegreeMap degree)

  {

    //create queue, visitor...don't forget namespaces!

    typedef typename property_traits<DegreeMap>::value_type ds_type;

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;

    typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;

    typedef typename property_traits<ColorMap>::value_type ColorValue;

    typedef color_traits<ColorValue> Color;

    queue Q;

    //create a bfs_rcm_visitor as defined above

    Visitor     vis(&permutation, &Q, degree);

    typename graph_traits<Graph>::vertex_iterator ui, ui_end;    

    // Copy degree to pseudo_degree

    // initialize the color map

    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){

      put(color, *ui, Color::white());

    }

    while( !vertex_queue.empty() ) {

      Vertex s = vertex_queue.front();

      vertex_queue.pop_front();

      //call BFS with visitor

      breadth_first_visit(g, s, Q, vis, color);

    }

    return permutation;

  }

  // This is the case where only a single starting vertex is supplied.

  template <class Graph, class OutputIterator,

            class ColorMap, class DegreeMap>

  OutputIterator

  cuthill_mckee_ordering(const Graph& g,

                         typename graph_traits<Graph>::vertex_descriptor s,

                         OutputIterator permutation, 

                         ColorMap color, DegreeMap degree)

  {

    std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;

    vertex_queue.push_front( s );

    return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);

  }

  // This is the version of CM which selects its own starting vertex

  template < class Graph, class OutputIterator, 

             class ColorMap, class DegreeMap>

  OutputIterator 

  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation, 

                         ColorMap color, DegreeMap degree)

  {

    if (vertices(G).first == vertices(G).second)

      return permutation;

    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;

    typedef typename property_traits<ColorMap>::value_type ColorValue;

    typedef color_traits<ColorValue> Color;

    std::deque<Vertex>      vertex_queue;

    // Mark everything white

    BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());

    // Find one vertex from each connected component 

    BGL_FORALL_VERTICES_T(v, G, Graph) {

      if (get(color, v) == Color::white()) {

        depth_first_visit(G, v, dfs_visitor<>(), color);

        vertex_queue.push_back(v);

      }

    }

    // Find starting nodes for all vertices

    // TBD: How to do this with a directed graph?

    for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();

         i != vertex_queue.end(); ++i)

      *i = find_starting_node(G, *i, color, degree);

    return cuthill_mckee_ordering(G, vertex_queue, permutation,

                                  color, degree);

  }

  template<typename Graph, typename OutputIterator, typename VertexIndexMap>

  OutputIterator 

  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation, 

                         VertexIndexMap index_map)

  {

    if (vertices(G).first == vertices(G).second)

      return permutation;

    typedef out_degree_property_map<Graph> DegreeMap;

    std::vector<default_color_type> colors(num_vertices(G));

    return cuthill_mckee_ordering(G, permutation, 

                                  make_iterator_property_map(&colors[0], 

                                                             index_map,

                                                             colors[0]),

                                  make_out_degree_map(G));

  }

  template<typename Graph, typename OutputIterator>

  inline OutputIterator 

  cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)

  { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }

} // namespace boost

#endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP