//

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

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