williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Copyright 2004, 2005 Trustees of Indiana University
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
williamr@2: //          Doug Gregor, D. Kevin McGrath
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================//
williamr@2: #ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
williamr@2: #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
williamr@2: 
williamr@2: #include <boost/config.hpp>
williamr@2: #include <vector>
williamr@2: #include <queue>
williamr@2: #include <boost/pending/queue.hpp>
williamr@2: #include <boost/pending/mutable_queue.hpp>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/graph/breadth_first_search.hpp>
williamr@2: #include <boost/graph/properties.hpp>
williamr@2: #include <boost/pending/indirect_cmp.hpp>
williamr@2: #include <boost/property_map.hpp>
williamr@2: #include <boost/bind.hpp>
williamr@2: #include <boost/graph/iteration_macros.hpp>
williamr@2: #include <boost/graph/depth_first_search.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   namespace sparse {
williamr@2: 
williamr@2:     // rcm_queue
williamr@2:     //
williamr@2:     // This is a custom queue type used in the
williamr@2:     // *_ordering algorithms.
williamr@2:     // In addition to the normal queue operations, the
williamr@2:     // rcm_queue provides:
williamr@2:     // 
williamr@2:     //   int eccentricity() const;
williamr@2:     //   value_type spouse() const;
williamr@2:     // 
williamr@2: 
williamr@2:     // yes, it's a bad name...but it works, so use it
williamr@2:     template < class Vertex, class DegreeMap,
williamr@2:                class Container = std::deque<Vertex> >
williamr@2:     class rcm_queue : public std::queue<Vertex, Container> {
williamr@2:       typedef std::queue<Vertex> base;
williamr@2:     public:
williamr@2:       typedef typename base::value_type value_type;
williamr@2:       typedef typename base::size_type size_type;
williamr@2: 
williamr@2:       /* SGI queue has not had a contructor queue(const Container&) */
williamr@2:       inline rcm_queue(DegreeMap deg)
williamr@2:         : _size(0), Qsize(1), eccen(-1), degree(deg) { }
williamr@2: 
williamr@2:       inline void pop() {
williamr@2:         if ( !_size ) 
williamr@2:           Qsize = base::size();
williamr@2: 
williamr@2:         base::pop();
williamr@2:         if ( _size == Qsize-1 ) {
williamr@2:           _size = 0;
williamr@2:           ++eccen;
williamr@2:         } else 
williamr@2:           ++_size;
williamr@2: 
williamr@2:       }
williamr@2: 
williamr@2:       inline value_type& front() {
williamr@2:         value_type& u =  base::front();
williamr@2:         if ( _size == 0 ) 
williamr@2:           w = u;
williamr@2:         else if (get(degree,u) < get(degree,w) )
williamr@2:           w = u;
williamr@2:         return u;
williamr@2:       }
williamr@2: 
williamr@2:       inline const value_type& front() const {
williamr@2:         const value_type& u =  base::front();
williamr@2:         if ( _size == 0 ) 
williamr@2:           w = u;
williamr@2:         else if (get(degree,u) < get(degree,w) )
williamr@2:           w = u;
williamr@2:         return u;
williamr@2:       }
williamr@2: 
williamr@2:       inline value_type& top() { return front(); }
williamr@2:       inline const value_type& top() const { return front(); }
williamr@2: 
williamr@2:       inline size_type size() const { return base::size(); }
williamr@2: 
williamr@2:       inline size_type eccentricity() const { return eccen; }
williamr@2:       inline value_type spouse() const { return w; }
williamr@2: 
williamr@2:     protected:
williamr@2:       size_type _size;
williamr@2:       size_type Qsize;
williamr@2:       int eccen;
williamr@2:       mutable value_type w;
williamr@2:       DegreeMap degree;
williamr@2:     };
williamr@2: 
williamr@2: 
williamr@2:     template <typename Tp, typename Sequence = std::deque<Tp> >
williamr@2:     class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
williamr@2:     public:      
williamr@2:       typedef typename Sequence::iterator iterator;
williamr@2:       typedef typename Sequence::reverse_iterator reverse_iterator;
williamr@2:       typedef queue<Tp,Sequence> base;
williamr@2:       typedef typename Sequence::size_type size_type;
williamr@2: 
williamr@2:       inline iterator begin() { return this->c.begin(); }
williamr@2:       inline reverse_iterator rbegin() { return this->c.rbegin(); }
williamr@2:       inline iterator end() { return this->c.end(); }
williamr@2:       inline reverse_iterator rend() { return this->c.rend(); }
williamr@2:       inline Tp &operator[](int n) { return this->c[n]; }
williamr@2:       inline size_type size() {return this->c.size(); }
williamr@2:     protected:
williamr@2:       //nothing
williamr@2:     };
williamr@2:     
williamr@2:   } // namespace sparse 
williamr@2: 
williamr@2:   // Compute Pseudo peripheral
williamr@2:   //
williamr@2:   // To compute an approximated peripheral for a given vertex. 
williamr@2:   // Used in <tt>king_ordering</tt> algorithm.
williamr@2:   //
williamr@2:   template <class Graph, class Vertex, class ColorMap, class DegreeMap>
williamr@2:   Vertex 
williamr@2:   pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
williamr@2:                          ColorMap color, DegreeMap degree)
williamr@2:   {
williamr@2:     typedef typename property_traits<ColorMap>::value_type ColorValue;
williamr@2:     typedef color_traits<ColorValue> Color;
williamr@2:     
williamr@2:     sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
williamr@2: 
williamr@2:     typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
williamr@2:     for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
williamr@2:       if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
williamr@2:     breadth_first_visit(G, u, buffer(Q).color_map(color));
williamr@2: 
williamr@2:     ecc = Q.eccentricity(); 
williamr@2:     return Q.spouse();
williamr@2:   }
williamr@2: 
williamr@2:   // Find a good starting node
williamr@2:   //
williamr@2:   // This is to find a good starting node for the
williamr@2:   // king_ordering algorithm. "good" is in the sense
williamr@2:   // of the ordering generated by RCM.
williamr@2:   //
williamr@2:   template <class Graph, class Vertex, class Color, class Degree> 
williamr@2:   Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)
williamr@2:   {
williamr@2:     Vertex x, y;
williamr@2:     int eccen_r, eccen_x;
williamr@2: 
williamr@2:     x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
williamr@2:     y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
williamr@2: 
williamr@2:     while (eccen_x > eccen_r) {
williamr@2:       r = x;
williamr@2:       eccen_r = eccen_x;
williamr@2:       x = y;
williamr@2:       y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
williamr@2:     }
williamr@2:     return x;
williamr@2:   }
williamr@2: 
williamr@2: template <typename Graph>
williamr@2: class out_degree_property_map 
williamr@2:   : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
williamr@2:                           out_degree_property_map<Graph> >                  
williamr@2: {
williamr@2: public:
williamr@2:   typedef typename graph_traits<Graph>::vertex_descriptor key_type;
williamr@2:   typedef typename graph_traits<Graph>::degree_size_type value_type;
williamr@2:   typedef value_type reference;
williamr@2:   typedef readable_property_map_tag category;
williamr@2:   out_degree_property_map(const Graph& g) : m_g(g) { }
williamr@2:   value_type operator[](const key_type& v) const {
williamr@2:     return out_degree(v, m_g);
williamr@2:   }
williamr@2: private:
williamr@2:   const Graph& m_g;
williamr@2: };
williamr@2: template <typename Graph>
williamr@2: inline out_degree_property_map<Graph>
williamr@2: make_out_degree_map(const Graph& g) {
williamr@2:   return out_degree_property_map<Graph>(g);
williamr@2: }
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_KING_HPP