Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / detail / sparse_ordering.hpp
1 //
2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5 //
6 // This file is part of the Boost Graph Library
7 //
8 // You should have received a copy of the License Agreement for the
9 // Boost Graph Library along with the software; see the file LICENSE.
10 // If not, contact Office of Research, University of Notre Dame, Notre
11 // Dame, IN 46556.
12 //
13 // Permission to modify the code and to distribute modified code is
14 // granted, provided the text of this NOTICE is retained, a notice that
15 // the code was modified is included with the above COPYRIGHT NOTICE and
16 // with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
17 // file is distributed with the modified code.
18 //
19 // LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
20 // By way of example, but not limitation, Licensor MAKES NO
21 // REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
22 // PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
23 // OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
24 // OR OTHER RIGHTS.
25 //=======================================================================
26 //
27 #ifndef BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
28 #define BOOST_GRAPH_DETAIL_SPARSE_ORDERING_HPP
29
30 #include <boost/config.hpp>
31 #include <vector>
32 #include <queue>
33 #include <boost/pending/queue.hpp>
34 #include <boost/pending/mutable_queue.hpp>
35 #include <boost/graph/graph_traits.hpp>
36 #include <boost/graph/breadth_first_search.hpp>
37 #include <boost/graph/properties.hpp>
38 #include <boost/pending/indirect_cmp.hpp>
39 #include <boost/property_map.hpp>
40 #include <boost/bind.hpp>
41 #include <boost/graph/iteration_macros.hpp>
42 #include <boost/graph/depth_first_search.hpp>
43
44 namespace boost {
45
46   namespace sparse {
47
48     // rcm_queue
49     //
50     // This is a custom queue type used in the
51     // *_ordering algorithms.
52     // In addition to the normal queue operations, the
53     // rcm_queue provides:
54     // 
55     //   int eccentricity() const;
56     //   value_type spouse() const;
57     // 
58
59     // yes, it's a bad name...but it works, so use it
60     template < class Vertex, class DegreeMap,
61                class Container = std::deque<Vertex> >
62     class rcm_queue : public std::queue<Vertex, Container> {
63       typedef std::queue<Vertex> base;
64     public:
65       typedef typename base::value_type value_type;
66       typedef typename base::size_type size_type;
67
68       /* SGI queue has not had a contructor queue(const Container&) */
69       inline rcm_queue(DegreeMap deg)
70         : _size(0), Qsize(1), eccen(-1), degree(deg) { }
71
72       inline void pop() {
73         if ( !_size ) 
74           Qsize = base::size();
75
76         base::pop();
77         if ( _size == Qsize-1 ) {
78           _size = 0;
79           ++eccen;
80         } else 
81           ++_size;
82
83       }
84
85       inline value_type& front() {
86         value_type& u =  base::front();
87         if ( _size == 0 ) 
88           w = u;
89         else if (get(degree,u) < get(degree,w) )
90           w = u;
91         return u;
92       }
93
94       inline const value_type& front() const {
95         const value_type& u =  base::front();
96         if ( _size == 0 ) 
97           w = u;
98         else if (get(degree,u) < get(degree,w) )
99           w = u;
100         return u;
101       }
102
103       inline value_type& top() { return front(); }
104       inline const value_type& top() const { return front(); }
105
106       inline size_type size() const { return base::size(); }
107
108       inline size_type eccentricity() const { return eccen; }
109       inline value_type spouse() const { return w; }
110
111     protected:
112       size_type _size;
113       size_type Qsize;
114       int eccen;
115       mutable value_type w;
116       DegreeMap degree;
117     };
118
119
120     template <typename Tp, typename Sequence = std::deque<Tp> >
121     class sparse_ordering_queue : public boost::queue<Tp, Sequence>{
122     public:      
123       typedef typename Sequence::iterator iterator;
124       typedef typename Sequence::reverse_iterator reverse_iterator;
125       typedef queue<Tp,Sequence> queue;
126       typedef typename Sequence::size_type size_type;
127
128       inline iterator begin() { return this->c.begin(); }
129       inline reverse_iterator rbegin() { return this->c.rbegin(); }
130       inline iterator end() { return this->c.end(); }
131       inline reverse_iterator rend() { return this->c.rend(); }
132       inline Tp &operator[](int n) { return this->c[n]; }
133       inline size_type size() {return this->c.size(); }
134     protected:
135       //nothing
136     };
137     
138   } // namespace sparse 
139
140   // Compute Pseudo peripheral
141   //
142   // To compute an approximated peripheral for a given vertex. 
143   // Used in <tt>king_ordering</tt> algorithm.
144   //
145   template <class Graph, class Vertex, class ColorMap, class DegreeMap>
146   Vertex 
147   pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
148                          ColorMap color, DegreeMap degree)
149   {
150     typedef typename property_traits<ColorMap>::value_type ColorValue;
151     typedef color_traits<ColorValue> Color;
152     
153     sparse::rcm_queue<Vertex, DegreeMap> Q(degree);
154
155     typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
156     for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
157       if (get(color, *ui) != Color::red()) put(color, *ui, Color::white());
158     breadth_first_visit(G, u, buffer(Q).color_map(color));
159
160     ecc = Q.eccentricity(); 
161     return Q.spouse();
162   }
163
164   // Find a good starting node
165   //
166   // This is to find a good starting node for the
167   // king_ordering algorithm. "good" is in the sense
168   // of the ordering generated by RCM.
169   //
170   template <class Graph, class Vertex, class Color, class Degree> 
171   Vertex find_starting_node(Graph& G, Vertex r, Color color, Degree degree)
172   {
173     Vertex x, y;
174     int eccen_r, eccen_x;
175
176     x = pseudo_peripheral_pair(G, r, eccen_r, color, degree);
177     y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
178
179     while (eccen_x > eccen_r) {
180       r = x;
181       eccen_r = eccen_x;
182       x = y;
183       y = pseudo_peripheral_pair(G, x, eccen_x, color, degree);
184     }
185     return x;
186   }
187
188 template <typename Graph>
189 class out_degree_property_map 
190   : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
191                           out_degree_property_map<Graph> >                  
192 {
193 public:
194   typedef typename graph_traits<Graph>::vertex_descriptor key_type;
195   typedef typename graph_traits<Graph>::degree_size_type value_type;
196   typedef value_type reference;
197   typedef readable_property_map_tag category;
198   out_degree_property_map(const Graph& g) : m_g(g) { }
199   value_type operator[](const key_type& v) const {
200     return out_degree(v, m_g);
201   }
202 private:
203   const Graph& m_g;
204 };
205 template <typename Graph>
206 inline out_degree_property_map<Graph>
207 make_out_degree_map(const Graph& g) {
208   return out_degree_property_map<Graph>(g);
209 }
210
211 } // namespace boost
212
213
214 #endif // BOOST_GRAPH_KING_HPP