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