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

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

 #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP

 #include <boost/config.hpp>

 #include <vector>

 #include <queue>

 #include <boost/pending/queue.hpp>

 #include <boost/pending/mutable_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 <boost/bind.hpp>

 #include <boost/graph/iteration_macros.hpp>

 #include <boost/graph/depth_first_search.hpp>

 namespace boost {

   namespace sparse {

     // rcm_queue

     //

     // This is a custom queue type used in the

     // *_ordering algorithms.

     // In addition to the normal queue operations, the

     // rcm_queue provides:

     // 

     //   int eccentricity() const;

     //   value_type spouse() const;

     // 

     // yes, it's a bad name...but it works, so use it

     template < class Vertex, class DegreeMap,

                class Container = std::deque<Vertex> >

     class rcm_queue : public std::queue<Vertex, Container> {

       typedef std::queue<Vertex> base;

     public:

       typedef typename base::value_type value_type;

       typedef typename base::size_type size_type;

       /* SGI queue has not had a contructor queue(const Container&) */

       inline rcm_queue(DegreeMap deg)

         : _size(0), Qsize(1), eccen(-1), degree(deg) { }

       inline void pop() {

         if ( !_size ) 

           Qsize = base::size();

         base::pop();

         if ( _size == Qsize-1 ) {

           _size = 0;

           ++eccen;

         } else 

           ++_size;

       }

       inline value_type& front() {

         value_type& u =  base::front();

         if ( _size == 0 ) 

           w = u;

         else if (get(degree,u) < get(degree,w) )

           w = u;

         return u;

       }

       inline const value_type& front() const {

         const value_type& u =  base::front();

         if ( _size == 0 ) 

           w = u;

         else if (get(degree,u) < get(degree,w) )

           w = u;

         return u;

       }

       inline value_type& top() { return front(); }

       inline const value_type& top() const { return front(); }

       inline size_type size() const { return base::size(); }

       inline size_type eccentricity() const { return eccen; }

       inline value_type spouse() const { return w; }

     protected:

       size_type _size;

       size_type Qsize;

       int eccen;

       mutable value_type w;

       DegreeMap degree;

     };

     template <typename Tp, typename Sequence = std::deque<Tp> >

     class sparse_ordering_queue : public boost::queue<Tp, Sequence>{

     public:      

       typedef typename Sequence::iterator iterator;

       typedef typename Sequence::reverse_iterator reverse_iterator;

       typedef queue<Tp,Sequence> base;

       typedef typename Sequence::size_type size_type;

       inline iterator begin() { return this->c.begin(); }

       inline reverse_iterator rbegin() { return this->c.rbegin(); }

       inline iterator end() { return this->c.end(); }

       inline reverse_iterator rend() { return this->c.rend(); }

       inline Tp &operator[](int n) { return this->c[n]; }

       inline size_type size() {return this->c.size(); }

     protected:

       //nothing

     };

   } // namespace sparse 

   // Compute Pseudo peripheral

   //

   // To compute an approximated peripheral for a given vertex. 

   // Used in <tt>king_ordering</tt> algorithm.

   //

   template <class Graph, class Vertex, class ColorMap, class DegreeMap>

   Vertex 

   pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,

                          ColorMap color, DegreeMap degree)

   {

     typedef typename property_traits<ColorMap>::value_type ColorValue;

     typedef color_traits<ColorValue> Color;

     sparse::rcm_queue<Vertex, DegreeMap> Q(degree);

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

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

       if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());

     breadth_first_visit(G, u, buffer(Q).color_map(color));

     ecc = Q.eccentricity(); 

     return Q.spouse();

   }

   // Find a good starting node

   //

   // This is to find a good starting node for the

   // king_ordering algorithm. "good" is in the sense

   // of the ordering generated by RCM.

   //

   template <class Graph, class Vertex, class Color, class Degree> 

   Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)

   {

     Vertex x, y;

     int eccen_r, eccen_x;

     x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);

     y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);

     while (eccen_x > eccen_r) {

       r = x;

       eccen_r = eccen_x;

       x = y;

       y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);

     }

     return x;

   }

 template <typename Graph>

 class out_degree_property_map 

   : public put_get_helper<typename graph_traits<Graph>::degree_size_type,

                           out_degree_property_map<Graph> >                  

 {

 public:

   typedef typename graph_traits<Graph>::vertex_descriptor key_type;

   typedef typename graph_traits<Graph>::degree_size_type value_type;

   typedef value_type reference;

   typedef readable_property_map_tag category;

   out_degree_property_map(const Graph& g) : m_g(g) { }

   value_type operator[](const key_type& v) const {

     return out_degree(v, m_g);

   }

 private:

   const Graph& m_g;

 };

 template <typename Graph>

 inline out_degree_property_map<Graph>

 make_out_degree_map(const Graph& g) {

   return out_degree_property_map<Graph>(g);

 }

 } // namespace boost

 #endif // BOOST_GRAPH_KING_HPP