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/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&) */
rcm_queue(DegreeMap deg)53       inline rcm_queue(DegreeMap deg)
54         : _size(0), Qsize(1), eccen(-1), degree(deg) { }
55 
pop()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 
front()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 
front() const78       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 
top()87       inline value_type& top() { return front(); }
top() const88       inline const value_type& top() const { return front(); }
89 
size() const90       inline size_type size() const { return base::size(); }
91 
eccentricity() const92       inline size_type eccentricity() const { return eccen; }
spouse() const93       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 
begin()112       inline iterator begin() { return this->c.begin(); }
rbegin()113       inline reverse_iterator rbegin() { return this->c.rbegin(); }
end()114       inline iterator end() { return this->c.end(); }
rend()115       inline reverse_iterator rend() { return this->c.rend(); }
operator [](int n)116       inline Tp &operator[](int n) { return this->c[n]; }
size()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 const& 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 (boost::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 const& 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;
out_degree_property_map(const Graph & g)182   out_degree_property_map(const Graph& g) : m_g(g) { }
operator [](const key_type & v) const183   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>
make_out_degree_map(const Graph & g)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
199