1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/king_ordering.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,320 @@
1.4 +//=======================================================================
1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.6 +// Copyright 2004, 2005 Trustees of Indiana University
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
1.8 +// Doug Gregor, D. Kevin McGrath
1.9 +//
1.10 +// Distributed under the Boost Software License, Version 1.0. (See
1.11 +// accompanying file LICENSE_1_0.txt or copy at
1.12 +// http://www.boost.org/LICENSE_1_0.txt)
1.13 +//=======================================================================//
1.14 +#ifndef BOOST_GRAPH_KING_HPP
1.15 +#define BOOST_GRAPH_KING_HPP
1.16 +
1.17 +#include <boost/config.hpp>
1.18 +#include <boost/graph/detail/sparse_ordering.hpp>
1.19 +
1.20 +/*
1.21 + King Algorithm for matrix reordering
1.22 +*/
1.23 +
1.24 +namespace boost {
1.25 + namespace detail {
1.26 + template<typename OutputIterator, typename Buffer, typename Compare,
1.27 + typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap>
1.28 + class bfs_king_visitor:public default_bfs_visitor
1.29 + {
1.30 + public:
1.31 + bfs_king_visitor(OutputIterator *iter, Buffer *b, Compare compare,
1.32 + PseudoDegreeMap deg, std::vector<int> loc, VecMap color,
1.33 + VertexIndexMap vertices):
1.34 + permutation(iter), Qptr(b), degree(deg), comp(compare),
1.35 + Qlocation(loc), colors(color), vertex_map(vertices) { }
1.36 +
1.37 + template <typename Vertex, typename Graph>
1.38 + void finish_vertex(Vertex, Graph& g) {
1.39 + typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
1.40 + Vertex v, w;
1.41 +
1.42 + typedef typename std::deque<Vertex>::iterator iterator;
1.43 + typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
1.44 +
1.45 + reverse_iterator rend = Qptr->rend()-index_begin;
1.46 + reverse_iterator rbegin = Qptr->rbegin();
1.47 +
1.48 +
1.49 + //heap the vertices already there
1.50 + std::make_heap(rbegin, rend, boost::bind<bool>(comp, _2, _1));
1.51 +
1.52 + unsigned i = 0;
1.53 +
1.54 + for(i = index_begin; i != Qptr->size(); ++i){
1.55 + colors[get(vertex_map, (*Qptr)[i])] = 1;
1.56 + Qlocation[get(vertex_map, (*Qptr)[i])] = i;
1.57 + }
1.58 +
1.59 + i = 0;
1.60 +
1.61 + for( ; rbegin != rend; rend--){
1.62 + percolate_down<Vertex>(i);
1.63 + w = (*Qptr)[index_begin+i];
1.64 + for (tie(ei, ei_end) = out_edges(w, g); ei != ei_end; ++ei) {
1.65 + v = target(*ei, g);
1.66 + put(degree, v, get(degree, v) - 1);
1.67 +
1.68 + if (colors[get(vertex_map, v)] == 1) {
1.69 + percolate_up<Vertex>(get(vertex_map, v), i);
1.70 + }
1.71 + }
1.72 +
1.73 + colors[get(vertex_map, w)] = 0;
1.74 + i++;
1.75 + }
1.76 + }
1.77 +
1.78 + template <typename Vertex, typename Graph>
1.79 + void examine_vertex(Vertex u, const Graph&) {
1.80 +
1.81 + *(*permutation)++ = u;
1.82 + index_begin = Qptr->size();
1.83 +
1.84 + }
1.85 + protected:
1.86 +
1.87 +
1.88 + //this function replaces pop_heap, and tracks state information
1.89 + template <typename Vertex>
1.90 + void percolate_down(int offset){
1.91 + typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
1.92 +
1.93 + int heap_last = index_begin + offset;
1.94 + int heap_first = Qptr->size() - 1;
1.95 +
1.96 + //pop_heap functionality:
1.97 + //swap first, last
1.98 + std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);
1.99 +
1.100 + //swap in the location queue
1.101 + std::swap(Qlocation[heap_first], Qlocation[heap_last]);
1.102 +
1.103 + //set drifter, children
1.104 + int drifter = heap_first;
1.105 + int drifter_heap = Qptr->size() - drifter;
1.106 +
1.107 + int right_child_heap = drifter_heap * 2 + 1;
1.108 + int right_child = Qptr->size() - right_child_heap;
1.109 +
1.110 + int left_child_heap = drifter_heap * 2;
1.111 + int left_child = Qptr->size() - left_child_heap;
1.112 +
1.113 + //check that we are staying in the heap
1.114 + bool valid = (right_child < heap_last) ? false : true;
1.115 +
1.116 + //pick smallest child of drifter, and keep in mind there might only be left child
1.117 + int smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
1.118 + right_child : left_child;
1.119 +
1.120 + while(valid && smallest_child < heap_last && comp((*Qptr)[drifter], (*Qptr)[smallest_child])){
1.121 +
1.122 + //if smallest child smaller than drifter, swap them
1.123 + std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]);
1.124 + std::swap(Qlocation[drifter], Qlocation[smallest_child]);
1.125 +
1.126 + //update the values, run again, as necessary
1.127 + drifter = smallest_child;
1.128 + drifter_heap = Qptr->size() - drifter;
1.129 +
1.130 + right_child_heap = drifter_heap * 2 + 1;
1.131 + right_child = Qptr->size() - right_child_heap;
1.132 +
1.133 + left_child_heap = drifter_heap * 2;
1.134 + left_child = Qptr->size() - left_child_heap;
1.135 +
1.136 + valid = (right_child < heap_last) ? false : true;
1.137 +
1.138 + smallest_child = (valid && get(degree, (*Qptr)[left_child]) > get(degree,(*Qptr)[right_child])) ?
1.139 + right_child : left_child;
1.140 + }
1.141 +
1.142 + }
1.143 +
1.144 +
1.145 +
1.146 + // this is like percolate down, but we always compare against the
1.147 + // parent, as there is only a single choice
1.148 + template <typename Vertex>
1.149 + void percolate_up(int vertex, int offset){
1.150 +
1.151 + int child_location = Qlocation[vertex];
1.152 + int heap_child_location = Qptr->size() - child_location;
1.153 + int heap_parent_location = (int)(heap_child_location/2);
1.154 + unsigned parent_location = Qptr->size() - heap_parent_location;
1.155 +
1.156 + bool valid = (heap_parent_location != 0 && child_location > index_begin + offset &&
1.157 + parent_location < Qptr->size());
1.158 +
1.159 + while(valid && comp((*Qptr)[child_location], (*Qptr)[parent_location])){
1.160 +
1.161 + //swap in the heap
1.162 + std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);
1.163 +
1.164 + //swap in the location queue
1.165 + std::swap(Qlocation[child_location], Qlocation[parent_location]);
1.166 +
1.167 + child_location = parent_location;
1.168 + heap_child_location = heap_parent_location;
1.169 + heap_parent_location = (int)(heap_child_location/2);
1.170 + parent_location = Qptr->size() - heap_parent_location;
1.171 + valid = (heap_parent_location != 0 && child_location > index_begin + offset);
1.172 + }
1.173 + }
1.174 +
1.175 + OutputIterator *permutation;
1.176 + int index_begin;
1.177 + Buffer *Qptr;
1.178 + PseudoDegreeMap degree;
1.179 + Compare comp;
1.180 + std::vector<int> Qlocation;
1.181 + VecMap colors;
1.182 + VertexIndexMap vertex_map;
1.183 + };
1.184 +
1.185 +
1.186 + } // namespace detail
1.187 +
1.188 +
1.189 + template<class Graph, class OutputIterator, class ColorMap, class DegreeMap,
1.190 + typename VertexIndexMap>
1.191 + OutputIterator
1.192 + king_ordering(const Graph& g,
1.193 + std::deque< typename graph_traits<Graph>::vertex_descriptor >
1.194 + vertex_queue,
1.195 + OutputIterator permutation,
1.196 + ColorMap color, DegreeMap degree,
1.197 + VertexIndexMap index_map)
1.198 + {
1.199 + typedef typename property_traits<DegreeMap>::value_type ds_type;
1.200 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.201 + typedef color_traits<ColorValue> Color;
1.202 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.203 + typedef iterator_property_map<typename std::vector<ds_type>::iterator, VertexIndexMap, ds_type, ds_type&> PseudoDegreeMap;
1.204 + typedef indirect_cmp<PseudoDegreeMap, std::less<ds_type> > Compare;
1.205 + typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
1.206 + typedef typename detail::bfs_king_visitor<OutputIterator, queue, Compare,
1.207 + PseudoDegreeMap, std::vector<int>, VertexIndexMap > Visitor;
1.208 + typedef typename graph_traits<Graph>::vertices_size_type
1.209 + vertices_size_type;
1.210 + std::vector<ds_type> pseudo_degree_vec(num_vertices(g));
1.211 + PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);
1.212 +
1.213 + typename graph_traits<Graph>::vertex_iterator ui, ui_end;
1.214 + queue Q;
1.215 + // Copy degree to pseudo_degree
1.216 + // initialize the color map
1.217 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
1.218 + put(pseudo_degree, *ui, get(degree, *ui));
1.219 + put(color, *ui, Color::white());
1.220 + }
1.221 +
1.222 + Compare comp(pseudo_degree);
1.223 + std::vector<int> colors(num_vertices(g));
1.224 +
1.225 + for(vertices_size_type i = 0; i < num_vertices(g); i++)
1.226 + colors[i] = 0;
1.227 +
1.228 + std::vector<int> loc(num_vertices(g));
1.229 +
1.230 + //create the visitor
1.231 + Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);
1.232 +
1.233 + while( !vertex_queue.empty() ) {
1.234 + Vertex s = vertex_queue.front();
1.235 + vertex_queue.pop_front();
1.236 +
1.237 + //call BFS with visitor
1.238 + breadth_first_visit(g, s, Q, vis, color);
1.239 + }
1.240 +
1.241 + return permutation;
1.242 + }
1.243 +
1.244 +
1.245 + // This is the case where only a single starting vertex is supplied.
1.246 + template <class Graph, class OutputIterator,
1.247 + class ColorMap, class DegreeMap, typename VertexIndexMap>
1.248 + OutputIterator
1.249 + king_ordering(const Graph& g,
1.250 + typename graph_traits<Graph>::vertex_descriptor s,
1.251 + OutputIterator permutation,
1.252 + ColorMap color, DegreeMap degree, VertexIndexMap index_map)
1.253 + {
1.254 +
1.255 + std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
1.256 + vertex_queue.push_front( s );
1.257 + return king_ordering(g, vertex_queue, permutation, color, degree,
1.258 + index_map);
1.259 + }
1.260 +
1.261 +
1.262 + template < class Graph, class OutputIterator,
1.263 + class ColorMap, class DegreeMap, class VertexIndexMap>
1.264 + OutputIterator
1.265 + king_ordering(const Graph& G, OutputIterator permutation,
1.266 + ColorMap color, DegreeMap degree, VertexIndexMap index_map)
1.267 + {
1.268 + if (vertices(G).first == vertices(G).second)
1.269 + return permutation;
1.270 +
1.271 + typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
1.272 + typedef typename boost::graph_traits<Graph>::vertex_iterator VerIter;
1.273 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.274 + typedef color_traits<ColorValue> Color;
1.275 +
1.276 + std::deque<Vertex> vertex_queue;
1.277 +
1.278 + // Mark everything white
1.279 + BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
1.280 +
1.281 + // Find one vertex from each connected component
1.282 + BGL_FORALL_VERTICES_T(v, G, Graph) {
1.283 + if (get(color, v) == Color::white()) {
1.284 + depth_first_visit(G, v, dfs_visitor<>(), color);
1.285 + vertex_queue.push_back(v);
1.286 + }
1.287 + }
1.288 +
1.289 + // Find starting nodes for all vertices
1.290 + // TBD: How to do this with a directed graph?
1.291 + for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
1.292 + i != vertex_queue.end(); ++i)
1.293 + *i = find_starting_node(G, *i, color, degree);
1.294 +
1.295 + return king_ordering(G, vertex_queue, permutation, color, degree,
1.296 + index_map);
1.297 + }
1.298 +
1.299 + template<typename Graph, typename OutputIterator, typename VertexIndexMap>
1.300 + OutputIterator
1.301 + king_ordering(const Graph& G, OutputIterator permutation,
1.302 + VertexIndexMap index_map)
1.303 + {
1.304 + if (vertices(G).first == vertices(G).second)
1.305 + return permutation;
1.306 +
1.307 + typedef out_degree_property_map<Graph> DegreeMap;
1.308 + std::vector<default_color_type> colors(num_vertices(G));
1.309 + return king_ordering(G, permutation,
1.310 + make_iterator_property_map(&colors[0], index_map,
1.311 + colors[0]),
1.312 + make_out_degree_map(G), index_map);
1.313 + }
1.314 +
1.315 + template<typename Graph, typename OutputIterator>
1.316 + inline OutputIterator
1.317 + king_ordering(const Graph& G, OutputIterator permutation)
1.318 + { return king_ordering(G, permutation, get(vertex_index, G)); }
1.319 +
1.320 +} // namespace boost
1.321 +
1.322 +
1.323 +#endif // BOOST_GRAPH_KING_HPP