Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / king_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 //          Doug Gregor, D. Kevin McGrath
6 //
7 // This file is part of the Boost Graph Library
8 //
9 // You should have received a copy of the License Agreement for the
10 // Boost Graph Library along with the software; see the file LICENSE.
11 // If not, contact Office of Research, University of Notre Dame, Notre
12 // Dame, IN 46556.
13 //
14 // Permission to modify the code and to distribute modified code is
15 // granted, provided the text of this NOTICE is retained, a notice that
16 // the code was modified is included with the above COPYRIGHT NOTICE and
17 // with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
18 // file is distributed with the modified code.
19 //
20 // LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
21 // By way of example, but not limitation, Licensor MAKES NO
22 // REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
23 // PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
24 // OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
25 // OR OTHER RIGHTS.
26 //=======================================================================
27 //
28 #ifndef BOOST_GRAPH_KING_HPP
29 #define BOOST_GRAPH_KING_HPP
30
31 #include <boost/config.hpp>
32 #include <boost/graph/detail/sparse_ordering.hpp>
33
34 /*
35   King Algorithm for matrix reordering
36 */
37
38 namespace boost {
39   namespace detail {
40     template<typename OutputIterator, typename Buffer, typename Compare, 
41              typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap>
42     class bfs_king_visitor:public default_bfs_visitor
43     {
44     public:
45       bfs_king_visitor(OutputIterator *iter, Buffer *b, Compare compare, 
46                        PseudoDegreeMap deg, std::vector<int> loc, VecMap color, 
47                        VertexIndexMap vertices): 
48         permutation(iter), Qptr(b), degree(deg), comp(compare), 
49         Qlocation(loc), colors(color), vertex_map(vertices) { }
50       
51       template <typename Vertex, typename Graph>
52       void finish_vertex(Vertex, Graph& g) {
53         typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
54         Vertex v, w;
55
56         typedef typename std::deque<Vertex>::iterator iterator;
57         typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
58
59         reverse_iterator rend = Qptr->rend()-index_begin;
60         reverse_iterator rbegin = Qptr->rbegin();
61
62
63         //heap the vertices already there
64         std::make_heap(rbegin, rend, boost::bind<bool>(comp, _2, _1));
65
66         int i = 0;
67         
68         for(i = index_begin; i != Qptr->size(); ++i){
69           colors[get(vertex_map, (*Qptr)[i])] = 1;
70           Qlocation[get(vertex_map, (*Qptr)[i])] = i;
71         }
72
73         i = 0;
74
75         for( ; rbegin != rend; rend--){
76           percolate_down<Vertex>(i);
77           w = (*Qptr)[index_begin+i];
78           for (tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) {
79             v = target(*ei, g);
80             put(degree, v, get(degree, v) - 1);
81     
82             if (colors[get(vertex_map, v)] == 1) {
83               percolate_up<Vertex>(get(vertex_map, v), i);            
84             }
85           }
86           
87           colors[get(vertex_map, w)] = 0;
88           i++;
89         }
90       }
91     
92       template <typename Vertex, typename Graph>
93       void examine_vertex(Vertex u, const Graph&) {
94         
95         *(*permutation)++ = u;
96         index_begin = Qptr->size();
97         
98       }
99     protected:
100
101
102       //this function replaces pop_heap, and tracks state information
103       template <typename Vertex>
104       void percolate_down(int offset){
105         typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
106         
107         int heap_last = index_begin + offset;
108         int heap_first = Qptr->size() - 1;
109         
110         //pop_heap functionality:
111         //swap first, last
112         std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);
113         
114         //swap in the location queue
115         std::swap(Qlocation[heap_first], Qlocation[heap_last]);
116
117         //set drifter, children
118         int drifter = heap_first;
119         int drifter_heap = Qptr->size() - drifter;
120
121         int right_child_heap = drifter_heap * 2 + 1;
122         int right_child = Qptr->size() - right_child_heap;
123
124         int left_child_heap = drifter_heap * 2;
125         int left_child = Qptr->size() - left_child_heap;
126
127         //check that we are staying in the heap
128         bool valid = (right_child < heap_last) ? false : true;
129         
130         //pick smallest child of drifter, and keep in mind there might only be left child
131         int smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ? 
132           right_child : left_child;
133         
134         while(valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])){
135           
136           //if smallest child smaller than drifter, swap them
137           std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]);
138           std::swap(Qlocation[drifter], Qlocation[smallest_child]);
139
140           //update the values, run again, as necessary
141           drifter = smallest_child;
142           drifter_heap = Qptr->size() - drifter;
143
144           right_child_heap = drifter_heap * 2 + 1;
145           right_child = Qptr->size() - right_child_heap;
146
147           left_child_heap = drifter_heap * 2;
148           left_child = Qptr->size() - left_child_heap;
149
150           valid = (right_child < heap_last) ? false : true;
151
152           smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ? 
153             right_child : left_child;
154         }
155
156       }
157
158
159       
160       // this is like percolate down, but we always compare against the
161       // parent, as there is only a single choice
162       template <typename Vertex>
163       void percolate_up(int vertex, int offset){
164         
165         int child_location = Qlocation[vertex];
166         int heap_child_location = Qptr->size() - child_location;
167         int heap_parent_location = (int)(heap_child_location/2);
168         int parent_location = Qptr->size() - heap_parent_location; 
169
170         bool valid = (heap_parent_location != 0 && child_location > index_begin + offset && 
171                       parent_location < Qptr->size());
172
173         while(valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])){
174           
175           //swap in the heap
176           std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);
177           
178           //swap in the location queue
179           std::swap(Qlocation[child_location], Qlocation[parent_location]);
180
181           child_location = parent_location;
182           heap_child_location = heap_parent_location;
183           heap_parent_location = (int)(heap_child_location/2);
184           parent_location = Qptr->size() - heap_parent_location; 
185           valid = (heap_parent_location != 0 && child_location > index_begin + offset);
186         }
187       }
188       
189       OutputIterator *permutation;
190       int index_begin;
191       Buffer *Qptr;
192       PseudoDegreeMap degree;
193       Compare comp;
194       std::vector<int> Qlocation;
195       VecMap colors;
196       VertexIndexMap vertex_map;
197     };
198   
199
200   } // namespace detail  
201   
202
203   template<class Graph, class OutputIterator, class ColorMap, class DegreeMap,
204            typename VertexIndexMap> 
205   OutputIterator
206   king_ordering(const Graph& g,
207                 std::deque< typename graph_traits<Graph>::vertex_descriptor >
208                   vertex_queue,
209                 OutputIterator permutation, 
210                 ColorMap color, DegreeMap degree,
211                 VertexIndexMap index_map)
212   {
213     typedef typename property_traits<DegreeMap>::value_type DS;
214     typedef typename property_traits<ColorMap>::value_type ColorValue;
215     typedef color_traits<ColorValue> Color;
216     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
217     typedef iterator_property_map<typename std::vector<DS>::iterator, VertexIndexMap, DS, DS&> PseudoDegreeMap;
218     typedef indirect_cmp<PseudoDegreeMap, std::less<DS> > Compare;
219     typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
220     typedef typename detail::bfs_king_visitor<OutputIterator, queue, Compare,             
221       PseudoDegreeMap, std::vector<int>, VertexIndexMap > Visitor;
222     typedef typename graph_traits<Graph>::vertices_size_type
223       vertices_size_type;
224     std::vector<DS> pseudo_degree_vec(num_vertices(g));
225     PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);
226     
227     typename graph_traits<Graph>::vertex_iterator ui, ui_end;    
228     queue Q;
229     // Copy degree to pseudo_degree
230     // initialize the color map
231     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
232       put(pseudo_degree, *ui, get(degree, *ui));
233       put(color, *ui, Color::white());
234     }
235     
236     Compare comp(pseudo_degree);
237     std::vector<int> colors(num_vertices(g));
238
239     for(vertices_size_type i = 0; i < num_vertices(g); i++) 
240       colors[i] = 0;
241
242     std::vector<int> loc(num_vertices(g));
243
244     //create the visitor
245     Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);
246     
247     while( !vertex_queue.empty() ) {
248       Vertex s = vertex_queue.front();
249       vertex_queue.pop_front();
250       
251       //call BFS with visitor
252       breadth_first_visit(g, s, Q, vis, color);
253     }
254
255     return permutation;
256   }
257
258   
259   // This is the case where only a single starting vertex is supplied.
260   template <class Graph, class OutputIterator,
261             class ColorMap, class DegreeMap, typename VertexIndexMap>
262   OutputIterator
263   king_ordering(const Graph& g,
264                 typename graph_traits<Graph>::vertex_descriptor s,
265                 OutputIterator permutation, 
266                 ColorMap color, DegreeMap degree, VertexIndexMap index_map)
267   {
268
269     std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
270     vertex_queue.push_front( s );
271     return king_ordering(g, vertex_queue, permutation, color, degree,
272                          index_map);
273   }
274
275   
276   template < class Graph, class OutputIterator, 
277              class ColorMap, class DegreeMap, class VertexIndexMap>
278   OutputIterator 
279   king_ordering(const Graph& G, OutputIterator permutation, 
280                 ColorMap color, DegreeMap degree, VertexIndexMap index_map)
281   {
282     if (vertices(G).first == vertices(G).second)
283       return permutation;
284
285     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
286     typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;
287     typedef typename property_traits<ColorMap>::value_type ColorValue;
288     typedef color_traits<ColorValue> Color;
289
290     std::deque<Vertex>      vertex_queue;
291
292     // Mark everything white
293     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
294
295     // Find one vertex from each connected component 
296     BGL_FORALL_VERTICES_T(v, G, Graph) {
297       if (get(color, v) == Color::white()) {
298         depth_first_visit(G, v, dfs_visitor<>(), color);
299         vertex_queue.push_back(v);
300       }
301     }
302
303     // Find starting nodes for all vertices
304     // TBD: How to do this with a directed graph?
305     for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
306          i != vertex_queue.end(); ++i)
307       *i = find_starting_node(G, *i, color, degree);
308     
309     return king_ordering(G, vertex_queue, permutation, color, degree,
310                          index_map);
311   }
312
313   template<typename Graph, typename OutputIterator, typename VertexIndexMap>
314   OutputIterator 
315   king_ordering(const Graph& G, OutputIterator permutation, 
316                 VertexIndexMap index_map)
317   {
318     if (vertices(G).first == vertices(G).second)
319       return permutation;
320
321     typedef out_degree_property_map<Graph> DegreeMap;
322     std::vector<default_color_type> colors(num_vertices(G));
323     return king_ordering(G, permutation, 
324                          make_iterator_property_map(&colors[0], index_map,
325                                                     colors[0]),
326                          make_out_degree_map(G), index_map);
327   }
328
329   template<typename Graph, typename OutputIterator>
330   inline OutputIterator 
331   king_ordering(const Graph& G, OutputIterator permutation)
332   { return king_ordering(G, permutation, get(vertex_index, G)); }
333
334 } // namespace boost
335
336
337 #endif // BOOST_GRAPH_KING_HPP