Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / sloan_ordering.hpp
1 //
2 //=======================================================================
3 // Copyright 2002 Marc Wintermantel (wintermantel@imes.mavt.ethz.ch)
4 // ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
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
28 #ifndef BOOST_GRAPH_SLOAN_HPP
29 #define BOOST_GRAPH_SLOAN_HPP
30
31 #define WEIGHT1 1               //default weight for the distance in the Sloan algorithm
32 #define WEIGHT2 2               //default weight for the degree in the Sloan algorithm
33 #define MAXINT 2147483647       //Maximum value for a 32bit integer
34
35 #include <boost/config.hpp>
36 #include <vector>
37 #include <queue>
38 #include <boost/pending/queue.hpp>
39 #include <boost/graph/graph_traits.hpp>
40 #include <boost/graph/breadth_first_search.hpp>
41 #include <boost/graph/properties.hpp>
42 #include <boost/pending/indirect_cmp.hpp>
43 #include <boost/property_map.hpp>
44 #include <algorithm>
45 #include <utility>
46 #include <boost/graph/visitors.hpp>
47 #include <boost/graph/adjacency_list.hpp>
48 #include <boost/graph/cuthill_mckee_ordering.hpp>
49
50
51 ////////////////////////////////////////////////////////////
52 //
53 //Sloan-Algorithm for graph reordering
54 //(optimzes profile and wavefront, not primiraly bandwidth
55 //
56 ////////////////////////////////////////////////////////////
57
58 namespace boost {
59         
60   /////////////////////////////////////////////////////////////////////////
61   // Function that returns the maximum depth of 
62   // a rooted level strucutre (RLS)
63   //
64   /////////////////////////////////////////////////////////////////////////
65   template<class Distance>
66   unsigned RLS_depth(Distance& d)
67   {
68     unsigned h_s = 0;
69     typename Distance::iterator iter;
70     
71     for (iter = d.begin(); iter != d.end(); ++iter)
72       {
73         if(*iter > h_s)
74           {
75             h_s = *iter;
76           }
77       }
78     
79     return h_s;
80   }
81
82
83     
84   /////////////////////////////////////////////////////////////////////////
85   // Function that returns the width of the largest level of 
86   // a rooted level strucutre (RLS)
87   //
88   /////////////////////////////////////////////////////////////////////////
89   template<class Distance, class my_int>
90   unsigned RLS_max_width(Distance& d, my_int depth)
91   {
92     
93       //Searching for the maximum width of a level
94       std::vector<unsigned> dummy_width(depth+1, 0);
95       std::vector<unsigned>::iterator my_it;
96       typename Distance::iterator iter;
97       unsigned w_max = 0;
98       
99       for (iter = d.begin(); iter != d.end(); ++iter)
100       {
101           dummy_width[*iter]++;
102       }
103       
104       for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
105       {
106           if(*my_it > w_max) w_max = *my_it;
107       }
108       
109       return w_max;
110       
111   }
112     
113
114   /////////////////////////////////////////////////////////////////////////
115   // Function for finding a good starting node for Sloan algorithm
116   //
117   // This is to find a good starting node. "good" is in the sense
118   // of the ordering generated. 
119   /////////////////////////////////////////////////////////////////////////
120   template <class Graph, class ColorMap, class DegreeMap> 
121   typename graph_traits<Graph>::vertex_descriptor 
122   sloan_start_end_vertices(Graph& G, 
123                            typename graph_traits<Graph>::vertex_descriptor &s, 
124                            ColorMap color, 
125                            DegreeMap degree)
126   {
127     typedef typename property_traits<DegreeMap>::value_type Degree;
128     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
129     typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
130     typedef typename graph_traits<Graph>::vertices_size_type size_type;
131     
132     typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
133     
134     s = *(vertices(G).first);
135     Vertex e = s;
136     Vertex i;
137     unsigned my_degree = get(degree, s ); 
138     unsigned dummy, h_i, h_s, w_i, w_e;
139     bool new_start = true;
140     unsigned maximum_degree = 0;
141     
142     //Creating a std-vector for storing the distance from the start vertex in dist
143     std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);
144
145     //Wrap a property_map_iterator around the std::iterator
146     boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));
147     
148     //Creating a property_map for the indices of a vertex
149     typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);
150     
151     //Creating a priority queue
152     typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;
153     Compare comp(degree);
154     std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);
155     
156     //step 1
157     //Scan for the vertex with the smallest degree and the maximum degree
158     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
159     for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
160     {
161       dummy = get(degree, *ui);
162       
163       if(dummy < my_degree)
164       {
165         my_degree = dummy;
166         s = *ui;
167       }
168       
169       if(dummy > maximum_degree)
170       {
171         maximum_degree = dummy;
172       }
173     }
174     //end 1
175     
176     do{  
177       new_start = false;     //Setting the loop repetition status to false
178       
179       //step 2
180       //initialize the the disance std-vector with 0
181       for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
182       
183       //generating the RLS (rooted level structure)
184       breadth_first_search
185         (G, s, visitor
186          (
187            make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
188            )
189           );
190       
191       //end 2
192       
193       //step 3
194       //calculating the depth of the RLS
195       h_s = RLS_depth(dist);
196       
197       //step 4
198       //pushing one node of each degree in an ascending manner into degree_queue
199       std::vector<bool> shrink_trace(maximum_degree, false);
200       for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
201       {
202         dummy = get(degree, *ui);
203         
204         if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )
205         {
206           degree_queue.push(*ui);
207           shrink_trace[ dummy ] = true;
208         }
209       }
210       
211       //end 3 & 4
212
213       
214       //step 5
215       //Initializing w
216       w_e = MAXINT;
217       //end 5
218       
219       
220       //step 6
221       //Testing for termination
222       while( !degree_queue.empty() )
223       {
224         i = degree_queue.top();       //getting the node with the lowest degree from the degree queue
225         degree_queue.pop();           //ereasing the node with the lowest degree from the degree queue
226         
227         //generating a RLS          
228         for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
229         
230         breadth_first_search
231           (G, i, boost::visitor
232            (
233              make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
234              )
235             );
236         
237         //Calculating depth and width of the rooted level
238         h_i = RLS_depth(dist);
239         w_i = RLS_max_width(dist, h_i);
240         
241         //Testing for termination
242         if( (h_i > h_s) && (w_i < w_e) ) 
243         {
244           h_s = h_i;
245           s = i;
246           while(!degree_queue.empty()) degree_queue.pop();
247           new_start = true;         
248         }
249         else if(w_i < w_e)
250         { 
251           w_e = w_i;
252           e = i;
253         }
254       }
255       //end 6
256         
257     }while(new_start);
258     
259     return e;
260   }
261
262   //////////////////////////////////////////////////////////////////////////
263   // Sloan algorithm with a given starting Vertex.
264   //
265   // This algorithm requires user to provide a starting vertex to
266   // compute Sloan ordering.
267   //////////////////////////////////////////////////////////////////////////
268   template <class Graph, class OutputIterator,
269             class ColorMap, class DegreeMap,
270             class PriorityMap, class Weight>
271   OutputIterator
272   sloan_ordering(Graph& g,
273                  typename graph_traits<Graph>::vertex_descriptor s,
274                  typename graph_traits<Graph>::vertex_descriptor e,
275                  OutputIterator permutation, 
276                  ColorMap color, 
277                  DegreeMap degree, 
278                  PriorityMap priority, 
279                  Weight W1, 
280                  Weight W2)
281   {
282     //typedef typename property_traits<DegreeMap>::value_type Degree;
283     typedef typename property_traits<PriorityMap>::value_type Degree;
284     typedef typename property_traits<ColorMap>::value_type ColorValue;
285     typedef color_traits<ColorValue> Color;
286     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
287     typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
288     typedef typename graph_traits<Graph>::vertices_size_type size_type;
289
290     typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
291
292     
293     //Creating a std-vector for storing the distance from the end vertex in it
294     typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
295     
296     //Wrap a property_map_iterator around the std::iterator
297     boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); 
298     
299     breadth_first_search
300       (g, e, visitor
301        (
302            make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
303         )
304        );
305     
306     //Creating a property_map for the indices of a vertex
307     typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
308     
309     //Sets the color and priority to their initial status
310     unsigned cdeg;    
311     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
312     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
313     {
314         put(color, *ui, Color::white());
315         cdeg=get(degree, *ui)+1;
316         put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );  
317     }
318     
319     //Priority list
320     typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
321     Compare comp(priority);
322     std::list<Vertex> priority_list;
323
324     //Some more declarations
325     typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
326     Vertex u, v, w;
327
328     put(color, s, Color::green());      //Sets the color of the starting vertex to gray
329     priority_list.push_front(s);                 //Puts s into the priority_list
330     
331     while ( !priority_list.empty() ) 
332     {  
333       priority_list.sort(comp);         //Orders the elements in the priority list in an ascending manner
334       
335       u = priority_list.front();           //Accesses the last element in the priority list
336       priority_list.pop_front();               //Removes the last element in the priority list
337       
338       if(get(color, u) == Color::green() )
339       {
340         //for-loop over all out-edges of vertex u
341         for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) 
342         {
343           v = target(*ei, g);
344           
345           put( priority, v, get(priority, v) + W2 ); //updates the priority
346           
347           if (get(color, v) == Color::white() )      //test if the vertex is inactive
348           {
349             put(color, v, Color::green() );        //giving the vertex a preactive status
350             priority_list.push_front(v);                     //writing the vertex in the priority_queue
351           }           
352         }
353       }
354       
355       //Here starts step 8
356       *permutation++ = u;                      //Puts u to the first position in the permutation-vector
357       put(color, u, Color::black() );          //Gives u an inactive status
358       
359       //for loop over all the adjacent vertices of u
360       for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
361         
362         v = target(*ei, g);     
363         
364         if (get(color, v) == Color::green() ) {      //tests if the vertex is inactive
365           
366           put(color, v, Color::red() );        //giving the vertex an active status
367           put(priority, v, get(priority, v)+W2);  //updates the priority        
368           
369           //for loop over alll adjacent vertices of v
370           for (tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
371             w = target(*ei2, g);
372             
373             if(get(color, w) != Color::black() ) {     //tests if vertex is postactive
374               
375               put(priority, w, get(priority, w)+W2);  //updates the priority
376               
377               if(get(color, w) == Color::white() ){
378                 
379                 put(color, w, Color::green() );   // gives the vertex a preactive status
380                 priority_list.push_front(w);           // puts the vertex into the priority queue
381                 
382               } //end if
383               
384             } //end if
385             
386           } //end for
387           
388         } //end if
389         
390       } //end for
391       
392     } //end while
393     
394     
395     return permutation;
396   }  
397   
398   /////////////////////////////////////////////////////////////////////////////////////////
399   // Same algorithm as before, but without the weights given (taking default weights
400   template <class Graph, class OutputIterator,
401             class ColorMap, class DegreeMap,
402             class PriorityMap>
403   OutputIterator
404   sloan_ordering(Graph& g,
405                  typename graph_traits<Graph>::vertex_descriptor s,
406                  typename graph_traits<Graph>::vertex_descriptor e,
407                  OutputIterator permutation, 
408                  ColorMap color, 
409                  DegreeMap degree, 
410                  PriorityMap priority)
411   {
412     return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 
413   }
414
415
416   //////////////////////////////////////////////////////////////////////////
417   // Sloan algorithm without a given starting Vertex.
418   //
419   // This algorithm finds a good starting vertex itself to
420   // compute Sloan-ordering.
421   //////////////////////////////////////////////////////////////////////////
422  
423
424
425   template < class Graph, class OutputIterator, 
426              class Color, class Degree,
427              class Priority, class Weight>
428   inline OutputIterator
429   sloan_ordering(Graph& G, 
430                  OutputIterator permutation, 
431                  Color color, 
432                  Degree degree, 
433                  Priority priority, 
434                  Weight W1, 
435                  Weight W2 )
436   {
437     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
438     
439     Vertex s, e;
440     e = sloan_start_end_vertices(G, s, color, degree);
441     
442     return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
443   }
444
445   /////////////////////////////////////////////////////////////////////////////////////////
446   // Same as before, but without given weights (default weights are taken instead)
447   template < class Graph, class OutputIterator, 
448              class Color, class Degree,
449              class Priority >
450   inline OutputIterator
451   sloan_ordering(Graph& G, 
452                  OutputIterator permutation, 
453                  Color color, 
454                  Degree degree, 
455                  Priority priority)
456   { 
457     return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
458   }
459   
460   
461 } // namespace boost
462
463
464 #endif // BOOST_GRAPH_SLOAN_HPP