epoc32/include/stdapis/boost/graph/detail/sparse_ordering.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     1 //=======================================================================
     2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     3 // Copyright 2004, 2005 Trustees of Indiana University
     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
     5 //          Doug Gregor, D. Kevin McGrath
     6 //
     7 // Distributed under the Boost Software License, Version 1.0. (See
     8 // accompanying file LICENSE_1_0.txt or copy at
     9 // http://www.boost.org/LICENSE_1_0.txt)
    10 //=======================================================================//
    11 #ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
    12 #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
    13 
    14 #include <boost/config.hpp>
    15 #include <vector>
    16 #include <queue>
    17 #include <boost/pending/queue.hpp>
    18 #include <boost/pending/mutable_queue.hpp>
    19 #include <boost/graph/graph_traits.hpp>
    20 #include <boost/graph/breadth_first_search.hpp>
    21 #include <boost/graph/properties.hpp>
    22 #include <boost/pending/indirect_cmp.hpp>
    23 #include <boost/property_map.hpp>
    24 #include <boost/bind.hpp>
    25 #include <boost/graph/iteration_macros.hpp>
    26 #include <boost/graph/depth_first_search.hpp>
    27 
    28 namespace boost {
    29 
    30   namespace sparse {
    31 
    32     // rcm_queue
    33     //
    34     // This is a custom queue type used in the
    35     // *_ordering algorithms.
    36     // In addition to the normal queue operations, the
    37     // rcm_queue provides:
    38     // 
    39     //   int eccentricity() const;
    40     //   value_type spouse() const;
    41     // 
    42 
    43     // yes, it's a bad name...but it works, so use it
    44     template < class Vertex, class DegreeMap,
    45                class Container = std::deque<Vertex> >
    46     class rcm_queue : public std::queue<Vertex, Container> {
    47       typedef std::queue<Vertex> base;
    48     public:
    49       typedef typename base::value_type value_type;
    50       typedef typename base::size_type size_type;
    51 
    52       /* SGI queue has not had a contructor queue(const Container&) */
    53       inline rcm_queue(DegreeMap deg)
    54         : _size(0), Qsize(1), eccen(-1), degree(deg) { }
    55 
    56       inline void pop() {
    57         if ( !_size ) 
    58           Qsize = base::size();
    59 
    60         base::pop();
    61         if ( _size == Qsize-1 ) {
    62           _size = 0;
    63           ++eccen;
    64         } else 
    65           ++_size;
    66 
    67       }
    68 
    69       inline value_type& front() {
    70         value_type& u =  base::front();
    71         if ( _size == 0 ) 
    72           w = u;
    73         else if (get(degree,u) < get(degree,w) )
    74           w = u;
    75         return u;
    76       }
    77 
    78       inline const value_type& front() const {
    79         const value_type& u =  base::front();
    80         if ( _size == 0 ) 
    81           w = u;
    82         else if (get(degree,u) < get(degree,w) )
    83           w = u;
    84         return u;
    85       }
    86 
    87       inline value_type& top() { return front(); }
    88       inline const value_type& top() const { return front(); }
    89 
    90       inline size_type size() const { return base::size(); }
    91 
    92       inline size_type eccentricity() const { return eccen; }
    93       inline value_type spouse() const { return w; }
    94 
    95     protected:
    96       size_type _size;
    97       size_type Qsize;
    98       int eccen;
    99       mutable value_type w;
   100       DegreeMap degree;
   101     };
   102 
   103 
   104     template <typename Tp, typename Sequence = std::deque<Tp> >
   105     class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
   106     public:      
   107       typedef typename Sequence::iterator iterator;
   108       typedef typename Sequence::reverse_iterator reverse_iterator;
   109       typedef queue<Tp,Sequence> base;
   110       typedef typename Sequence::size_type size_type;
   111 
   112       inline iterator begin() { return this->c.begin(); }
   113       inline reverse_iterator rbegin() { return this->c.rbegin(); }
   114       inline iterator end() { return this->c.end(); }
   115       inline reverse_iterator rend() { return this->c.rend(); }
   116       inline Tp &operator[](int n) { return this->c[n]; }
   117       inline size_type size() {return this->c.size(); }
   118     protected:
   119       //nothing
   120     };
   121     
   122   } // namespace sparse 
   123 
   124   // Compute Pseudo peripheral
   125   //
   126   // To compute an approximated peripheral for a given vertex. 
   127   // Used in <tt>king_ordering</tt> algorithm.
   128   //
   129   template <class Graph, class Vertex, class ColorMap, class DegreeMap>
   130   Vertex 
   131   pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
   132                          ColorMap color, DegreeMap degree)
   133   {
   134     typedef typename property_traits<ColorMap>::value_type ColorValue;
   135     typedef color_traits<ColorValue> Color;
   136     
   137     sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
   138 
   139     typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
   140     for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
   141       if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
   142     breadth_first_visit(G, u, buffer(Q).color_map(color));
   143 
   144     ecc = Q.eccentricity(); 
   145     return Q.spouse();
   146   }
   147 
   148   // Find a good starting node
   149   //
   150   // This is to find a good starting node for the
   151   // king_ordering algorithm. "good" is in the sense
   152   // of the ordering generated by RCM.
   153   //
   154   template <class Graph, class Vertex, class Color, class Degree> 
   155   Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)
   156   {
   157     Vertex x, y;
   158     int eccen_r, eccen_x;
   159 
   160     x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
   161     y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
   162 
   163     while (eccen_x > eccen_r) {
   164       r = x;
   165       eccen_r = eccen_x;
   166       x = y;
   167       y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
   168     }
   169     return x;
   170   }
   171 
   172 template <typename Graph>
   173 class out_degree_property_map 
   174   : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
   175                           out_degree_property_map<Graph> >                  
   176 {
   177 public:
   178   typedef typename graph_traits<Graph>::vertex_descriptor key_type;
   179   typedef typename graph_traits<Graph>::degree_size_type value_type;
   180   typedef value_type reference;
   181   typedef readable_property_map_tag category;
   182   out_degree_property_map(const Graph& g) : m_g(g) { }
   183   value_type operator[](const key_type& v) const {
   184     return out_degree(v, m_g);
   185   }
   186 private:
   187   const Graph& m_g;
   188 };
   189 template <typename Graph>
   190 inline out_degree_property_map<Graph>
   191 make_out_degree_map(const Graph& g) {
   192   return out_degree_property_map<Graph>(g);
   193 }
   194 
   195 } // namespace boost
   196 
   197 
   198 #endif // BOOST_GRAPH_KING_HPP