1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/sloan_ordering.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,448 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
1.7 +// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +
1.15 +#ifndef BOOST_GRAPH_SLOAN_HPP
1.16 +#define BOOST_GRAPH_SLOAN_HPP
1.17 +
1.18 +#define WEIGHT1 1 //default weight for the distance in the Sloan algorithm
1.19 +#define WEIGHT2 2 //default weight for the degree in the Sloan algorithm
1.20 +#define MAXINT 2147483647 //Maximum value for a 32bit integer
1.21 +
1.22 +#include <boost/config.hpp>
1.23 +#include <vector>
1.24 +#include <queue>
1.25 +#include <boost/pending/queue.hpp>
1.26 +#include <boost/graph/graph_traits.hpp>
1.27 +#include <boost/graph/breadth_first_search.hpp>
1.28 +#include <boost/graph/properties.hpp>
1.29 +#include <boost/pending/indirect_cmp.hpp>
1.30 +#include <boost/property_map.hpp>
1.31 +#include <algorithm>
1.32 +#include <utility>
1.33 +#include <boost/graph/visitors.hpp>
1.34 +#include <boost/graph/adjacency_list.hpp>
1.35 +#include <boost/graph/cuthill_mckee_ordering.hpp>
1.36 +
1.37 +
1.38 +////////////////////////////////////////////////////////////
1.39 +//
1.40 +//Sloan-Algorithm for graph reordering
1.41 +//(optimzes profile and wavefront, not primiraly bandwidth
1.42 +//
1.43 +////////////////////////////////////////////////////////////
1.44 +
1.45 +namespace boost {
1.46 +
1.47 + /////////////////////////////////////////////////////////////////////////
1.48 + // Function that returns the maximum depth of
1.49 + // a rooted level strucutre (RLS)
1.50 + //
1.51 + /////////////////////////////////////////////////////////////////////////
1.52 + template<class Distance>
1.53 + unsigned RLS_depth(Distance& d)
1.54 + {
1.55 + unsigned h_s = 0;
1.56 + typename Distance::iterator iter;
1.57 +
1.58 + for (iter = d.begin(); iter != d.end(); ++iter)
1.59 + {
1.60 + if(*iter > h_s)
1.61 + {
1.62 + h_s = *iter;
1.63 + }
1.64 + }
1.65 +
1.66 + return h_s;
1.67 + }
1.68 +
1.69 +
1.70 +
1.71 + /////////////////////////////////////////////////////////////////////////
1.72 + // Function that returns the width of the largest level of
1.73 + // a rooted level strucutre (RLS)
1.74 + //
1.75 + /////////////////////////////////////////////////////////////////////////
1.76 + template<class Distance, class my_int>
1.77 + unsigned RLS_max_width(Distance& d, my_int depth)
1.78 + {
1.79 +
1.80 + //Searching for the maximum width of a level
1.81 + std::vector<unsigned> dummy_width(depth+1, 0);
1.82 + std::vector<unsigned>::iterator my_it;
1.83 + typename Distance::iterator iter;
1.84 + unsigned w_max = 0;
1.85 +
1.86 + for (iter = d.begin(); iter != d.end(); ++iter)
1.87 + {
1.88 + dummy_width[*iter]++;
1.89 + }
1.90 +
1.91 + for(my_it = dummy_width.begin(); my_it != dummy_width.end(); ++my_it)
1.92 + {
1.93 + if(*my_it > w_max) w_max = *my_it;
1.94 + }
1.95 +
1.96 + return w_max;
1.97 +
1.98 + }
1.99 +
1.100 +
1.101 + /////////////////////////////////////////////////////////////////////////
1.102 + // Function for finding a good starting node for Sloan algorithm
1.103 + //
1.104 + // This is to find a good starting node. "good" is in the sense
1.105 + // of the ordering generated.
1.106 + /////////////////////////////////////////////////////////////////////////
1.107 + template <class Graph, class ColorMap, class DegreeMap>
1.108 + typename graph_traits<Graph>::vertex_descriptor
1.109 + sloan_start_end_vertices(Graph& G,
1.110 + typename graph_traits<Graph>::vertex_descriptor &s,
1.111 + ColorMap color,
1.112 + DegreeMap degree)
1.113 + {
1.114 + typedef typename property_traits<DegreeMap>::value_type Degree;
1.115 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.116 + typedef typename std::vector< typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
1.117 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.118 +
1.119 + typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
1.120 +
1.121 + s = *(vertices(G).first);
1.122 + Vertex e = s;
1.123 + Vertex i;
1.124 + unsigned my_degree = get(degree, s );
1.125 + unsigned dummy, h_i, h_s, w_i, w_e;
1.126 + bool new_start = true;
1.127 + unsigned maximum_degree = 0;
1.128 +
1.129 + //Creating a std-vector for storing the distance from the start vertex in dist
1.130 + std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(G), 0);
1.131 +
1.132 + //Wrap a property_map_iterator around the std::iterator
1.133 + boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, G));
1.134 +
1.135 + //Creating a property_map for the indices of a vertex
1.136 + typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, G);
1.137 +
1.138 + //Creating a priority queue
1.139 + typedef indirect_cmp<DegreeMap, std::greater<Degree> > Compare;
1.140 + Compare comp(degree);
1.141 + std::priority_queue<Vertex, std::vector<Vertex>, Compare> degree_queue(comp);
1.142 +
1.143 + //step 1
1.144 + //Scan for the vertex with the smallest degree and the maximum degree
1.145 + typename graph_traits<Graph>::vertex_iterator ui, ui_end;
1.146 + for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
1.147 + {
1.148 + dummy = get(degree, *ui);
1.149 +
1.150 + if(dummy < my_degree)
1.151 + {
1.152 + my_degree = dummy;
1.153 + s = *ui;
1.154 + }
1.155 +
1.156 + if(dummy > maximum_degree)
1.157 + {
1.158 + maximum_degree = dummy;
1.159 + }
1.160 + }
1.161 + //end 1
1.162 +
1.163 + do{
1.164 + new_start = false; //Setting the loop repetition status to false
1.165 +
1.166 + //step 2
1.167 + //initialize the the disance std-vector with 0
1.168 + for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
1.169 +
1.170 + //generating the RLS (rooted level structure)
1.171 + breadth_first_search
1.172 + (G, s, visitor
1.173 + (
1.174 + make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
1.175 + )
1.176 + );
1.177 +
1.178 + //end 2
1.179 +
1.180 + //step 3
1.181 + //calculating the depth of the RLS
1.182 + h_s = RLS_depth(dist);
1.183 +
1.184 + //step 4
1.185 + //pushing one node of each degree in an ascending manner into degree_queue
1.186 + std::vector<bool> shrink_trace(maximum_degree, false);
1.187 + for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
1.188 + {
1.189 + dummy = get(degree, *ui);
1.190 +
1.191 + if( (dist[index_map[*ui]] == h_s ) && ( !shrink_trace[ dummy ] ) )
1.192 + {
1.193 + degree_queue.push(*ui);
1.194 + shrink_trace[ dummy ] = true;
1.195 + }
1.196 + }
1.197 +
1.198 + //end 3 & 4
1.199 +
1.200 +
1.201 + //step 5
1.202 + //Initializing w
1.203 + w_e = MAXINT;
1.204 + //end 5
1.205 +
1.206 +
1.207 + //step 6
1.208 + //Testing for termination
1.209 + while( !degree_queue.empty() )
1.210 + {
1.211 + i = degree_queue.top(); //getting the node with the lowest degree from the degree queue
1.212 + degree_queue.pop(); //ereasing the node with the lowest degree from the degree queue
1.213 +
1.214 + //generating a RLS
1.215 + for(typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator iter = dist.begin(); iter != dist.end(); ++iter) *iter = 0;
1.216 +
1.217 + breadth_first_search
1.218 + (G, i, boost::visitor
1.219 + (
1.220 + make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
1.221 + )
1.222 + );
1.223 +
1.224 + //Calculating depth and width of the rooted level
1.225 + h_i = RLS_depth(dist);
1.226 + w_i = RLS_max_width(dist, h_i);
1.227 +
1.228 + //Testing for termination
1.229 + if( (h_i > h_s) && (w_i < w_e) )
1.230 + {
1.231 + h_s = h_i;
1.232 + s = i;
1.233 + while(!degree_queue.empty()) degree_queue.pop();
1.234 + new_start = true;
1.235 + }
1.236 + else if(w_i < w_e)
1.237 + {
1.238 + w_e = w_i;
1.239 + e = i;
1.240 + }
1.241 + }
1.242 + //end 6
1.243 +
1.244 + }while(new_start);
1.245 +
1.246 + return e;
1.247 + }
1.248 +
1.249 + //////////////////////////////////////////////////////////////////////////
1.250 + // Sloan algorithm with a given starting Vertex.
1.251 + //
1.252 + // This algorithm requires user to provide a starting vertex to
1.253 + // compute Sloan ordering.
1.254 + //////////////////////////////////////////////////////////////////////////
1.255 + template <class Graph, class OutputIterator,
1.256 + class ColorMap, class DegreeMap,
1.257 + class PriorityMap, class Weight>
1.258 + OutputIterator
1.259 + sloan_ordering(Graph& g,
1.260 + typename graph_traits<Graph>::vertex_descriptor s,
1.261 + typename graph_traits<Graph>::vertex_descriptor e,
1.262 + OutputIterator permutation,
1.263 + ColorMap color,
1.264 + DegreeMap degree,
1.265 + PriorityMap priority,
1.266 + Weight W1,
1.267 + Weight W2)
1.268 + {
1.269 + //typedef typename property_traits<DegreeMap>::value_type Degree;
1.270 + typedef typename property_traits<PriorityMap>::value_type Degree;
1.271 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.272 + typedef color_traits<ColorValue> Color;
1.273 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.274 + typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
1.275 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.276 +
1.277 + typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;
1.278 +
1.279 +
1.280 + //Creating a std-vector for storing the distance from the end vertex in it
1.281 + typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
1.282 +
1.283 + //Wrap a property_map_iterator around the std::iterator
1.284 + boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g));
1.285 +
1.286 + breadth_first_search
1.287 + (g, e, visitor
1.288 + (
1.289 + make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
1.290 + )
1.291 + );
1.292 +
1.293 + //Creating a property_map for the indices of a vertex
1.294 + typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
1.295 +
1.296 + //Sets the color and priority to their initial status
1.297 + unsigned cdeg;
1.298 + typename graph_traits<Graph>::vertex_iterator ui, ui_end;
1.299 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
1.300 + {
1.301 + put(color, *ui, Color::white());
1.302 + cdeg=get(degree, *ui)+1;
1.303 + put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );
1.304 + }
1.305 +
1.306 + //Priority list
1.307 + typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
1.308 + Compare comp(priority);
1.309 + std::list<Vertex> priority_list;
1.310 +
1.311 + //Some more declarations
1.312 + typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
1.313 + Vertex u, v, w;
1.314 +
1.315 + put(color, s, Color::green()); //Sets the color of the starting vertex to gray
1.316 + priority_list.push_front(s); //Puts s into the priority_list
1.317 +
1.318 + while ( !priority_list.empty() )
1.319 + {
1.320 + priority_list.sort(comp); //Orders the elements in the priority list in an ascending manner
1.321 +
1.322 + u = priority_list.front(); //Accesses the last element in the priority list
1.323 + priority_list.pop_front(); //Removes the last element in the priority list
1.324 +
1.325 + if(get(color, u) == Color::green() )
1.326 + {
1.327 + //for-loop over all out-edges of vertex u
1.328 + for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
1.329 + {
1.330 + v = target(*ei, g);
1.331 +
1.332 + put( priority, v, get(priority, v) + W2 ); //updates the priority
1.333 +
1.334 + if (get(color, v) == Color::white() ) //test if the vertex is inactive
1.335 + {
1.336 + put(color, v, Color::green() ); //giving the vertex a preactive status
1.337 + priority_list.push_front(v); //writing the vertex in the priority_queue
1.338 + }
1.339 + }
1.340 + }
1.341 +
1.342 + //Here starts step 8
1.343 + *permutation++ = u; //Puts u to the first position in the permutation-vector
1.344 + put(color, u, Color::black() ); //Gives u an inactive status
1.345 +
1.346 + //for loop over all the adjacent vertices of u
1.347 + for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
1.348 +
1.349 + v = target(*ei, g);
1.350 +
1.351 + if (get(color, v) == Color::green() ) { //tests if the vertex is inactive
1.352 +
1.353 + put(color, v, Color::red() ); //giving the vertex an active status
1.354 + put(priority, v, get(priority, v)+W2); //updates the priority
1.355 +
1.356 + //for loop over alll adjacent vertices of v
1.357 + for (tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
1.358 + w = target(*ei2, g);
1.359 +
1.360 + if(get(color, w) != Color::black() ) { //tests if vertex is postactive
1.361 +
1.362 + put(priority, w, get(priority, w)+W2); //updates the priority
1.363 +
1.364 + if(get(color, w) == Color::white() ){
1.365 +
1.366 + put(color, w, Color::green() ); // gives the vertex a preactive status
1.367 + priority_list.push_front(w); // puts the vertex into the priority queue
1.368 +
1.369 + } //end if
1.370 +
1.371 + } //end if
1.372 +
1.373 + } //end for
1.374 +
1.375 + } //end if
1.376 +
1.377 + } //end for
1.378 +
1.379 + } //end while
1.380 +
1.381 +
1.382 + return permutation;
1.383 + }
1.384 +
1.385 + /////////////////////////////////////////////////////////////////////////////////////////
1.386 + // Same algorithm as before, but without the weights given (taking default weights
1.387 + template <class Graph, class OutputIterator,
1.388 + class ColorMap, class DegreeMap,
1.389 + class PriorityMap>
1.390 + OutputIterator
1.391 + sloan_ordering(Graph& g,
1.392 + typename graph_traits<Graph>::vertex_descriptor s,
1.393 + typename graph_traits<Graph>::vertex_descriptor e,
1.394 + OutputIterator permutation,
1.395 + ColorMap color,
1.396 + DegreeMap degree,
1.397 + PriorityMap priority)
1.398 + {
1.399 + return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
1.400 + }
1.401 +
1.402 +
1.403 + //////////////////////////////////////////////////////////////////////////
1.404 + // Sloan algorithm without a given starting Vertex.
1.405 + //
1.406 + // This algorithm finds a good starting vertex itself to
1.407 + // compute Sloan-ordering.
1.408 + //////////////////////////////////////////////////////////////////////////
1.409 +
1.410 +
1.411 +
1.412 + template < class Graph, class OutputIterator,
1.413 + class Color, class Degree,
1.414 + class Priority, class Weight>
1.415 + inline OutputIterator
1.416 + sloan_ordering(Graph& G,
1.417 + OutputIterator permutation,
1.418 + Color color,
1.419 + Degree degree,
1.420 + Priority priority,
1.421 + Weight W1,
1.422 + Weight W2 )
1.423 + {
1.424 + typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
1.425 +
1.426 + Vertex s, e;
1.427 + e = sloan_start_end_vertices(G, s, color, degree);
1.428 +
1.429 + return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
1.430 + }
1.431 +
1.432 + /////////////////////////////////////////////////////////////////////////////////////////
1.433 + // Same as before, but without given weights (default weights are taken instead)
1.434 + template < class Graph, class OutputIterator,
1.435 + class Color, class Degree,
1.436 + class Priority >
1.437 + inline OutputIterator
1.438 + sloan_ordering(Graph& G,
1.439 + OutputIterator permutation,
1.440 + Color color,
1.441 + Degree degree,
1.442 + Priority priority)
1.443 + {
1.444 + return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
1.445 + }
1.446 +
1.447 +
1.448 +} // namespace boost
1.449 +
1.450 +
1.451 +#endif // BOOST_GRAPH_SLOAN_HPP