//

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

// Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)

// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)

//

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

#define BOOST_GRAPH_SLOAN_HPP

#define WEIGHT1 1               //default weight for the distance in the Sloan algorithm

#define WEIGHT2 2               //default weight for the degree in the Sloan algorithm

#define MAXINT 2147483647       //Maximum value for a 32bit integer

#include <boost/config.hpp>

#include <vector>

#include <queue>

#include <boost/pending/queue.hpp>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/breadth_first_search.hpp>

#include <boost/graph/properties.hpp>

#include <boost/pending/indirect_cmp.hpp>

#include <boost/property_map.hpp>

#include <algorithm>

#include <utility>

#include <boost/graph/visitors.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/cuthill_mckee_ordering.hpp>

////////////////////////////////////////////////////////////

//

//Sloan-Algorithm for graph reordering

//(optimzes profile and wavefront, not primiraly bandwidth

//

////////////////////////////////////////////////////////////

namespace boost {

  /////////////////////////////////////////////////////////////////////////

  // Function that returns the maximum depth of 

  // a rooted level strucutre (RLS)

  //

  /////////////////////////////////////////////////////////////////////////

  template<class Distance>

  unsigned RLS_depth(Distance& d)

  {

    unsigned h_s = 0;

    typename Distance::iterator iter;

    for (iter = d.begin(); iter != d.end(); ++iter)

      {

        if(*iter > h_s)

          {

            h_s = *iter;

          }

      }

    return h_s;

  }

  /////////////////////////////////////////////////////////////////////////

  // Function that returns the width of the largest level of 

  // a rooted level strucutre (RLS)

  //

  /////////////////////////////////////////////////////////////////////////

  template<class Distance, class my_int>

  unsigned RLS_max_width(Distance& d, my_int depth)

  {

      //Searching for the maximum width of a level

      std::vector<unsigned> dummy_width(depth+1, 0);

      std::vector<unsigned>::iterator my_it;

      typename Distance::iterator iter;

      unsigned w_max = 0;

      for (iter = d.begin(); iter != d.end(); ++iter)

      {

          dummy_width[*iter]++;

      }

      for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)

      {

          if(*my_it > w_max) w_max = *my_it;

      }

      return w_max;

  }

  /////////////////////////////////////////////////////////////////////////

  // Function for finding a good starting node for Sloan algorithm

  //

  // This is to find a good starting node. "good" is in the sense

  // of the ordering generated. 

  /////////////////////////////////////////////////////////////////////////

  template <class Graph, class ColorMap, class DegreeMap> 

  typename graph_traits<Graph>::vertex_descriptor 

  sloan_start_end_vertices(Graph& G, 

                           typename graph_traits<Graph>::vertex_descriptor &s, 

                           ColorMap color, 

                           DegreeMap degree)

  {

    typedef typename property_traits<DegreeMap>::value_type Degree;

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;

    typedef typename graph_traits<Graph>::vertices_size_type size_type;

    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;

    s = *(vertices(G).first);

    Vertex e = s;

    Vertex i;

    unsigned my_degree = get(degree, s ); 

    unsigned dummy, h_i, h_s, w_i, w_e;

    bool new_start = true;

    unsigned maximum_degree = 0;

    //Creating a std-vector for storing the distance from the start vertex in dist

    std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);

    //Wrap a property_map_iterator around the std::iterator

    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));

    //Creating a property_map for the indices of a vertex

    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);

    //Creating a priority queue

    typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;

    Compare comp(degree);

    std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);

    //step 1

    //Scan for the vertex with the smallest degree and the maximum degree

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

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

    {

      dummy = get(degree, *ui);

      if(dummy < my_degree)

      {

        my_degree = dummy;

        s = *ui;

      }

      if(dummy > maximum_degree)

      {

        maximum_degree = dummy;

      }

    }

    //end 1

    do{  

      new_start = false;     //Setting the loop repetition status to false

      //step 2

      //initialize the the disance std-vector with 0

      for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;

      //generating the RLS (rooted level structure)

      breadth_first_search

        (G, s, visitor

         (

           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )

           )

          );

      //end 2

      //step 3

      //calculating the depth of the RLS

      h_s = RLS_depth(dist);

      //step 4

      //pushing one node of each degree in an ascending manner into degree_queue

      std::vector<bool> shrink_trace(maximum_degree, false);

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

      {

        dummy = get(degree, *ui);

        if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )

        {

          degree_queue.push(*ui);

          shrink_trace[ dummy ] = true;

        }

      }

      //end 3 & 4

      //step 5

      //Initializing w

      w_e = MAXINT;

      //end 5

      //step 6

      //Testing for termination

      while( !degree_queue.empty() )

      {

        i = degree_queue.top();       //getting the node with the lowest degree from the degree queue

        degree_queue.pop();           //ereasing the node with the lowest degree from the degree queue

        //generating a RLS          

        for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;

        breadth_first_search

          (G, i, boost::visitor

           (

             make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )

             )

            );

        //Calculating depth and width of the rooted level

        h_i = RLS_depth(dist);

        w_i = RLS_max_width(dist, h_i);

        //Testing for termination

        if( (h_i > h_s) && (w_i < w_e) ) 

        {

          h_s = h_i;

          s = i;

          while(!degree_queue.empty()) degree_queue.pop();

          new_start = true;         

        }

        else if(w_i < w_e)

        { 

          w_e = w_i;

          e = i;

        }

      }

      //end 6

    }while(new_start);

    return e;

  }

  //////////////////////////////////////////////////////////////////////////

  // Sloan algorithm with a given starting Vertex.

  //

  // This algorithm requires user to provide a starting vertex to

  // compute Sloan ordering.

  //////////////////////////////////////////////////////////////////////////

  template <class Graph, class OutputIterator,

            class ColorMap, class DegreeMap,

            class PriorityMap, class Weight>

  OutputIterator

  sloan_ordering(Graph& g,

                 typename graph_traits<Graph>::vertex_descriptor s,

                 typename graph_traits<Graph>::vertex_descriptor e,

                 OutputIterator permutation, 

                 ColorMap color, 

                 DegreeMap degree, 

                 PriorityMap priority, 

                 Weight W1, 

                 Weight W2)

  {

    //typedef typename property_traits<DegreeMap>::value_type Degree;

    typedef typename property_traits<PriorityMap>::value_type Degree;

    typedef typename property_traits<ColorMap>::value_type ColorValue;

    typedef color_traits<ColorValue> Color;

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;

    typedef typename graph_traits<Graph>::vertices_size_type size_type;

    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;

    //Creating a std-vector for storing the distance from the end vertex in it

    typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);

    //Wrap a property_map_iterator around the std::iterator

    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); 

    breadth_first_search

      (g, e, visitor

       (

           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )

        )

       );

    //Creating a property_map for the indices of a vertex

    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);

    //Sets the color and priority to their initial status

    unsigned cdeg;    

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

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

    {

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

        cdeg=get(degree, *ui)+1;

        put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );  

    }

    //Priority list

    typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;

    Compare comp(priority);

    std::list<Vertex> priority_list;

    //Some more declarations

    typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;

    Vertex u, v, w;

    put(color, s, Color::green());      //Sets the color of the starting vertex to gray

    priority_list.push_front(s);                 //Puts s into the priority_list

    while ( !priority_list.empty() ) 

    {  

      priority_list.sort(comp);         //Orders the elements in the priority list in an ascending manner

      u = priority_list.front();           //Accesses the last element in the priority list

      priority_list.pop_front();               //Removes the last element in the priority list

      if(get(color, u) == Color::green() )

      {

        //for-loop over all out-edges of vertex u

        for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) 

        {

          v = target(*ei, g);

          put( priority, v, get(priority, v) + W2 ); //updates the priority

          if (get(color, v) == Color::white() )      //test if the vertex is inactive

          {

            put(color, v, Color::green() );        //giving the vertex a preactive status

            priority_list.push_front(v);                     //writing the vertex in the priority_queue

          }           

        }

      }

      //Here starts step 8

      *permutation++ = u;                      //Puts u to the first position in the permutation-vector

      put(color, u, Color::black() );          //Gives u an inactive status

      //for loop over all the adjacent vertices of u

      for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {

        v = target(*ei, g);     

        if (get(color, v) == Color::green() ) {      //tests if the vertex is inactive

          put(color, v, Color::red() );        //giving the vertex an active status

          put(priority, v, get(priority, v)+W2);  //updates the priority        

          //for loop over alll adjacent vertices of v

          for (tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {

            w = target(*ei2, g);

            if(get(color, w) != Color::black() ) {     //tests if vertex is postactive

              put(priority, w, get(priority, w)+W2);  //updates the priority

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

                put(color, w, Color::green() );   // gives the vertex a preactive status

                priority_list.push_front(w);           // puts the vertex into the priority queue

              } //end if

            } //end if

          } //end for

        } //end if

      } //end for

    } //end while

    return permutation;

  }  

  /////////////////////////////////////////////////////////////////////////////////////////

  // Same algorithm as before, but without the weights given (taking default weights

  template <class Graph, class OutputIterator,

            class ColorMap, class DegreeMap,

            class PriorityMap>

  OutputIterator

  sloan_ordering(Graph& g,

                 typename graph_traits<Graph>::vertex_descriptor s,

                 typename graph_traits<Graph>::vertex_descriptor e,

                 OutputIterator permutation, 

                 ColorMap color, 

                 DegreeMap degree, 

                 PriorityMap priority)

  {

    return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 

  }

  //////////////////////////////////////////////////////////////////////////

  // Sloan algorithm without a given starting Vertex.

  //

  // This algorithm finds a good starting vertex itself to

  // compute Sloan-ordering.

  //////////////////////////////////////////////////////////////////////////

  template < class Graph, class OutputIterator, 

             class Color, class Degree,

             class Priority, class Weight>

  inline OutputIterator

  sloan_ordering(Graph& G, 

                 OutputIterator permutation, 

                 Color color, 

                 Degree degree, 

                 Priority priority, 

                 Weight W1, 

                 Weight W2 )

  {

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

    Vertex s, e;

    e = sloan_start_end_vertices(G, s, color, degree);

    return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);

  }

  /////////////////////////////////////////////////////////////////////////////////////////

  // Same as before, but without given weights (default weights are taken instead)

  template < class Graph, class OutputIterator, 

             class Color, class Degree,

             class Priority >

  inline OutputIterator

  sloan_ordering(Graph& G, 

                 OutputIterator permutation, 

                 Color color, 

                 Degree degree, 

                 Priority priority)

  { 

    return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);

  }

} // namespace boost

#endif // BOOST_GRAPH_SLOAN_HPP