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