graph/detail/sparse_ordering.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Copyright 2004, 2005 Trustees of Indiana University
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
0005 //          Doug Gregor, D. Kevin McGrath
0006 //
0007 // Distributed under the Boost Software License, Version 1.0. (See
0008 // accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //=======================================================================//
0011 #ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
0012 #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
0013
0014 #include <boost/config.hpp>
0015 #include <vector>
0016 #include <queue>
0017 #include <boost/pending/queue.hpp>
0018 #include <boost/pending/mutable_queue.hpp>
0019 #include <boost/graph/graph_traits.hpp>
0020 #include <boost/graph/breadth_first_search.hpp>
0021 #include <boost/graph/properties.hpp>
0022 #include <boost/pending/indirect_cmp.hpp>
0023 #include <boost/property_map/property_map.hpp>
0024 #include <boost/graph/iteration_macros.hpp>
0025 #include <boost/graph/depth_first_search.hpp>
0026
0027 namespace boost
0028 {
0029
0030 namespace sparse
0031 {
0032
0033     // rcm_queue
0034     //
0035     // This is a custom queue type used in the
0036     // *_ordering algorithms.
0037     // In addition to the normal queue operations, the
0038     // rcm_queue provides:
0039     //
0040     //   int eccentricity() const;
0041     //   value_type spouse() const;
0042     //
0043
0044     // yes, it's a bad name...but it works, so use it
0045     template < class Vertex, class DegreeMap,
0046         class Container = std::deque< Vertex > >
0047     class rcm_queue : public std::queue< Vertex, Container >
0048     {
0049         typedef std::queue< Vertex > base;
0050
0051     public:
0052         typedef typename base::value_type value_type;
0053         typedef typename base::size_type size_type;
0054
0055         /* SGI queue has not had a contructor queue(const Container&) */
0056         inline rcm_queue(DegreeMap deg)
0057         : _size(0), Qsize(1), eccen(-1), degree(deg)
0058         {
0059         }
0060
0061         inline void pop()
0062         {
0063             if (!_size)
0064                 Qsize = base::size();
0065
0066             base::pop();
0067             if (_size == Qsize - 1)
0068             {
0069                 _size = 0;
0070                 ++eccen;
0071             }
0072             else
0073                 ++_size;
0074         }
0075
0076         inline value_type& front()
0077         {
0078             value_type& u = base::front();
0079             if (_size == 0)
0080                 w = u;
0081             else if (get(degree, u) < get(degree, w))
0082                 w = u;
0083             return u;
0084         }
0085
0086         inline const value_type& front() const
0087         {
0088             const value_type& u = base::front();
0089             if (_size == 0)
0090                 w = u;
0091             else if (get(degree, u) < get(degree, w))
0092                 w = u;
0093             return u;
0094         }
0095
0096         inline value_type& top() { return front(); }
0097         inline const value_type& top() const { return front(); }
0098
0099         inline size_type size() const { return base::size(); }
0100
0101         inline size_type eccentricity() const { return eccen; }
0102         inline value_type spouse() const { return w; }
0103
0104     protected:
0105         size_type _size;
0106         size_type Qsize;
0107         int eccen;
0108         mutable value_type w;
0109         DegreeMap degree;
0110     };
0111
0112     template < typename Tp, typename Sequence = std::deque< Tp > >
0113     class sparse_ordering_queue : public boost::queue< Tp, Sequence >
0114     {
0115     public:
0116         typedef typename Sequence::iterator iterator;
0117         typedef typename Sequence::reverse_iterator reverse_iterator;
0118         typedef queue< Tp, Sequence > base;
0119         typedef typename Sequence::size_type size_type;
0120
0121         inline iterator begin() { return this->c.begin(); }
0122         inline reverse_iterator rbegin() { return this->c.rbegin(); }
0123         inline iterator end() { return this->c.end(); }
0124         inline reverse_iterator rend() { return this->c.rend(); }
0125         inline Tp& operator[](int n) { return this->c[n]; }
0126         inline size_type size() { return this->c.size(); }
0127
0128     protected:
0129         // nothing
0130     };
0131
0132 } // namespace sparse
0133
0134 // Compute Pseudo peripheral
0135 //
0136 // To compute an approximated peripheral for a given vertex.
0137 // Used in <tt>king_ordering</tt> algorithm.
0138 //
0139 template < class Graph, class Vertex, class ColorMap, class DegreeMap >
0140 Vertex pseudo_peripheral_pair(
0141     Graph const& G, const Vertex& u, int& ecc, ColorMap color, DegreeMap degree)
0142 {
0143     typedef typename property_traits< ColorMap >::value_type ColorValue;
0144     typedef color_traits< ColorValue > Color;
0145
0146     sparse::rcm_queue< Vertex, DegreeMap > Q(degree);
0147
0148     typename boost::graph_traits< Graph >::vertex_iterator ui, ui_end;
0149     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0150         if (get(color, *ui) != Color::red())
0151             put(color, *ui, Color::white());
0152     breadth_first_visit(G, u, buffer(Q).color_map(color));
0153
0154     ecc = Q.eccentricity();
0155     return Q.spouse();
0156 }
0157
0158 // Find a good starting node
0159 //
0160 // This is to find a good starting node for the
0161 // king_ordering algorithm. "good" is in the sense
0162 // of the ordering generated by RCM.
0163 //
0164 template < class Graph, class Vertex, class Color, class Degree >
0165 Vertex find_starting_node(Graph const& G, Vertex r, Color color, Degree degree)
0166 {
0167     Vertex x, y;
0168     int eccen_r, eccen_x;
0169
0170     x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
0171     y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
0172
0173     while (eccen_x > eccen_r)
0174     {
0175         r = x;
0176         eccen_r = eccen_x;
0177         x = y;
0178         y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
0179     }
0180     return x;
0181 }
0182
0183 template < typename Graph >
0184 class out_degree_property_map
0185 : public put_get_helper< typename graph_traits< Graph >::degree_size_type,
0186       out_degree_property_map< Graph > >
0187 {
0188 public:
0189     typedef typename graph_traits< Graph >::vertex_descriptor key_type;
0190     typedef typename graph_traits< Graph >::degree_size_type value_type;
0191     typedef value_type reference;
0192     typedef readable_property_map_tag category;
0193     out_degree_property_map(const Graph& g) : m_g(g) {}
0194     value_type operator[](const key_type& v) const
0195     {
0196         return out_degree(v, m_g);
0197     }
0198
0199 private:
0200     const Graph& m_g;
0201 };
0202 template < typename Graph >
0203 inline out_degree_property_map< Graph > make_out_degree_map(const Graph& g)
0204 {
0205     return out_degree_property_map< Graph >(g);
0206 }
0207
0208 } // namespace boost
0209
0210 #endif // BOOST_GRAPH_KING_HPP