2 //=======================================================================
3 // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
4 // ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
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 //=======================================================================
12 #ifndef BOOST_GRAPH_SLOAN_HPP
13 #define BOOST_GRAPH_SLOAN_HPP
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
18 #include <boost/config.hpp>
23 #include <boost/pending/queue.hpp>
24 #include <boost/graph/graph_traits.hpp>
25 #include <boost/graph/breadth_first_search.hpp>
26 #include <boost/graph/properties.hpp>
27 #include <boost/pending/indirect_cmp.hpp>
28 #include <boost/property_map/property_map.hpp>
29 #include <boost/graph/visitors.hpp>
30 #include <boost/graph/adjacency_list.hpp>
31 #include <boost/graph/cuthill_mckee_ordering.hpp>
34 ////////////////////////////////////////////////////////////
36 //Sloan-Algorithm for graph reordering
37 //(optimzes profile and wavefront, not primiraly bandwidth
39 ////////////////////////////////////////////////////////////
43 /////////////////////////////////////////////////////////////////////////
44 // Function that returns the maximum depth of
45 // a rooted level strucutre (RLS)
47 /////////////////////////////////////////////////////////////////////////
48 template<class Distance>
49 typename Distance::value_type RLS_depth(Distance& d)
51 typename Distance::value_type h_s = 0;
52 typename Distance::iterator iter;
54 for (iter = d.begin(); iter != d.end(); ++iter)
67 /////////////////////////////////////////////////////////////////////////
68 // Function that returns the width of the largest level of
69 // a rooted level strucutre (RLS)
71 /////////////////////////////////////////////////////////////////////////
72 template<class Distance, class my_int>
73 typename Distance::value_type RLS_max_width(Distance& d, my_int depth)
76 typedef typename Distance::value_type Degree;
78 //Searching for the maximum width of a level
79 std::vector<Degree> dummy_width(depth+1, 0);
80 typename std::vector<Degree>::iterator my_it;
81 typename Distance::iterator iter;
84 for (iter = d.begin(); iter != d.end(); ++iter)
89 for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
91 if(*my_it > w_max) w_max = *my_it;
99 /////////////////////////////////////////////////////////////////////////
100 // Function for finding a good starting node for Sloan algorithm
102 // This is to find a good starting node. "good" is in the sense
103 // of the ordering generated.
104 /////////////////////////////////////////////////////////////////////////
105 template <class Graph, class ColorMap, class DegreeMap>
106 typename graph_traits<Graph>::vertex_descriptor
107 sloan_start_end_vertices(Graph& G,
108 typename graph_traits<Graph>::vertex_descriptor &s,
112 typedef typename property_traits<DegreeMap>::value_type Degree;
113 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
114 typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
115 typedef typename graph_traits<Graph>::vertices_size_type size_type;
117 typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
119 s = *(vertices(G).first);
122 Degree my_degree = get(degree, s );
123 Degree dummy, h_i, h_s, w_i, w_e;
124 bool new_start = true;
125 Degree maximum_degree = 0;
127 //Creating a std-vector for storing the distance from the start vertex in dist
128 std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);
130 //Wrap a property_map_iterator around the std::iterator
131 boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));
133 //Creating a property_map for the indices of a vertex
134 typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);
136 //Creating a priority queue
137 typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;
138 Compare comp(degree);
139 std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);
142 //Scan for the vertex with the smallest degree and the maximum degree
143 typename graph_traits<Graph>::vertex_iterator ui, ui_end;
144 for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
146 dummy = get(degree, *ui);
148 if(dummy < my_degree)
154 if(dummy > maximum_degree)
156 maximum_degree = dummy;
162 new_start = false; //Setting the loop repetition status to false
165 //initialize the the disance std-vector with 0
166 for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
168 //generating the RLS (rooted level structure)
172 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
179 //calculating the depth of the RLS
180 h_s = RLS_depth(dist);
183 //pushing one node of each degree in an ascending manner into degree_queue
184 std::vector<bool> shrink_trace(maximum_degree, false);
185 for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
187 dummy = get(degree, *ui);
189 if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )
191 degree_queue.push(*ui);
192 shrink_trace[ dummy ] = true;
201 w_e = (std::numeric_limits<Degree>::max)();
206 //Testing for termination
207 while( !degree_queue.empty() )
209 i = degree_queue.top(); //getting the node with the lowest degree from the degree queue
210 degree_queue.pop(); //ereasing the node with the lowest degree from the degree queue
213 for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
216 (G, i, boost::visitor
218 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
222 //Calculating depth and width of the rooted level
223 h_i = RLS_depth(dist);
224 w_i = RLS_max_width(dist, h_i);
226 //Testing for termination
227 if( (h_i > h_s) && (w_i < w_e) )
231 while(!degree_queue.empty()) degree_queue.pop();
247 //////////////////////////////////////////////////////////////////////////
248 // Sloan algorithm with a given starting Vertex.
250 // This algorithm requires user to provide a starting vertex to
251 // compute Sloan ordering.
252 //////////////////////////////////////////////////////////////////////////
253 template <class Graph, class OutputIterator,
254 class ColorMap, class DegreeMap,
255 class PriorityMap, class Weight>
257 sloan_ordering(Graph& g,
258 typename graph_traits<Graph>::vertex_descriptor s,
259 typename graph_traits<Graph>::vertex_descriptor e,
260 OutputIterator permutation,
263 PriorityMap priority,
267 //typedef typename property_traits<DegreeMap>::value_type Degree;
268 typedef typename property_traits<PriorityMap>::value_type Degree;
269 typedef typename property_traits<ColorMap>::value_type ColorValue;
270 typedef color_traits<ColorValue> Color;
271 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
272 typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
273 typedef typename graph_traits<Graph>::vertices_size_type size_type;
275 typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
278 //Creating a std-vector for storing the distance from the end vertex in it
279 typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
281 //Wrap a property_map_iterator around the std::iterator
282 boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g));
287 make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
291 //Creating a property_map for the indices of a vertex
292 typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
294 //Sets the color and priority to their initial status
296 typename graph_traits<Graph>::vertex_iterator ui, ui_end;
297 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
299 put(color, *ui, Color::white());
300 cdeg=get(degree, *ui)+1;
301 put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );
305 typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
306 Compare comp(priority);
307 std::list<Vertex> priority_list;
309 //Some more declarations
310 typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
313 put(color, s, Color::green()); //Sets the color of the starting vertex to gray
314 priority_list.push_front(s); //Puts s into the priority_list
316 while ( !priority_list.empty() )
318 priority_list.sort(comp); //Orders the elements in the priority list in an ascending manner
320 u = priority_list.front(); //Accesses the last element in the priority list
321 priority_list.pop_front(); //Removes the last element in the priority list
323 if(get(color, u) == Color::green() )
325 //for-loop over all out-edges of vertex u
326 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
330 put( priority, v, get(priority, v) + W2 ); //updates the priority
332 if (get(color, v) == Color::white() ) //test if the vertex is inactive
334 put(color, v, Color::green() ); //giving the vertex a preactive status
335 priority_list.push_front(v); //writing the vertex in the priority_queue
341 *permutation++ = u; //Puts u to the first position in the permutation-vector
342 put(color, u, Color::black() ); //Gives u an inactive status
344 //for loop over all the adjacent vertices of u
345 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
349 if (get(color, v) == Color::green() ) { //tests if the vertex is inactive
351 put(color, v, Color::red() ); //giving the vertex an active status
352 put(priority, v, get(priority, v)+W2); //updates the priority
354 //for loop over alll adjacent vertices of v
355 for (boost::tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
358 if(get(color, w) != Color::black() ) { //tests if vertex is postactive
360 put(priority, w, get(priority, w)+W2); //updates the priority
362 if(get(color, w) == Color::white() ){
364 put(color, w, Color::green() ); // gives the vertex a preactive status
365 priority_list.push_front(w); // puts the vertex into the priority queue
383 /////////////////////////////////////////////////////////////////////////////////////////
384 // Same algorithm as before, but without the weights given (taking default weights
385 template <class Graph, class OutputIterator,
386 class ColorMap, class DegreeMap,
389 sloan_ordering(Graph& g,
390 typename graph_traits<Graph>::vertex_descriptor s,
391 typename graph_traits<Graph>::vertex_descriptor e,
392 OutputIterator permutation,
395 PriorityMap priority)
397 return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
401 //////////////////////////////////////////////////////////////////////////
402 // Sloan algorithm without a given starting Vertex.
404 // This algorithm finds a good starting vertex itself to
405 // compute Sloan-ordering.
406 //////////////////////////////////////////////////////////////////////////
410 template < class Graph, class OutputIterator,
411 class Color, class Degree,
412 class Priority, class Weight>
413 inline OutputIterator
414 sloan_ordering(Graph& G,
415 OutputIterator permutation,
422 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
425 e = sloan_start_end_vertices(G, s, color, degree);
427 return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
430 /////////////////////////////////////////////////////////////////////////////////////////
431 // Same as before, but without given weights (default weights are taken instead)
432 template < class Graph, class OutputIterator,
433 class Color, class Degree,
435 inline OutputIterator
436 sloan_ordering(Graph& G,
437 OutputIterator permutation,
442 return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
449 #endif // BOOST_GRAPH_SLOAN_HPP