ceph/src/boost/boost/graph/king_ordering.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Copyright 2004, 2005 Trustees of Indiana University
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
   5 //          Doug Gregor, D. Kevin McGrath
   6 //
   7 // Distributed under the Boost Software License, Version 1.0. (See
   8 // accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10 //=======================================================================//
  11 #ifndef BOOST_GRAPH_KING_HPP
  12 #define BOOST_GRAPH_KING_HPP
  13
  14 #include <deque>
  15 #include <vector>
  16 #include <algorithm>
  17 #include <boost/config.hpp>
  18 #include <boost/bind/bind.hpp>
  19 #include <boost/tuple/tuple.hpp>
  20 #include <boost/graph/detail/sparse_ordering.hpp>
  21 #include <boost/graph/graph_utility.hpp>
  22
  23 /*
  24   King Algorithm for matrix reordering
  25 */
  26
  27 namespace boost
  28 {
  29 namespace detail
  30 {
  31     template < typename OutputIterator, typename Buffer, typename Compare,
  32         typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap >
  33     class bfs_king_visitor : public default_bfs_visitor
  34     {
  35     public:
  36         bfs_king_visitor(OutputIterator* iter, Buffer* b, Compare compare,
  37             PseudoDegreeMap deg, std::vector< int > loc, VecMap color,
  38             VertexIndexMap vertices)
  39         : permutation(iter)
  40         , Qptr(b)
  41         , degree(deg)
  42         , comp(compare)
  43         , Qlocation(loc)
  44         , colors(color)
  45         , vertex_map(vertices)
  46         {
  47         }
  48
  49         template < typename Vertex, typename Graph >
  50         void finish_vertex(Vertex, Graph& g)
  51         {
  52             using namespace boost::placeholders;
  53
  54             typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
  55             Vertex v, w;
  56
  57             typedef typename std::deque< Vertex >::reverse_iterator
  58                 reverse_iterator;
  59
  60             reverse_iterator rend = Qptr->rend() - index_begin;
  61             reverse_iterator rbegin = Qptr->rbegin();
  62
  63             // heap the vertices already there
  64             std::make_heap(rbegin, rend, boost::bind< bool >(comp, _2, _1));
  65
  66             unsigned i = 0;
  67
  68             for (i = index_begin; i != Qptr->size(); ++i)
  69             {
  70                 colors[get(vertex_map, (*Qptr)[i])] = 1;
  71                 Qlocation[get(vertex_map, (*Qptr)[i])] = i;
  72             }
  73
  74             i = 0;
  75
  76             for (; rbegin != rend; rend--)
  77             {
  78                 percolate_down< Vertex >(i);
  79                 w = (*Qptr)[index_begin + i];
  80                 for (boost::tie(ei, ei_end) = out_edges(w, g); ei != ei_end;
  81                      ++ei)
  82                 {
  83                     v = target(*ei, g);
  84                     put(degree, v, get(degree, v) - 1);
  85
  86                     if (colors[get(vertex_map, v)] == 1)
  87                     {
  88                         percolate_up< Vertex >(get(vertex_map, v), i);
  89                     }
  90                 }
  91
  92                 colors[get(vertex_map, w)] = 0;
  93                 i++;
  94             }
  95         }
  96
  97         template < typename Vertex, typename Graph >
  98         void examine_vertex(Vertex u, const Graph&)
  99         {
 100
 101             *(*permutation)++ = u;
 102             index_begin = Qptr->size();
 103         }
 104
 105     protected:
 106         // this function replaces pop_heap, and tracks state information
 107         template < typename Vertex > void percolate_down(int offset)
 108         {
 109             int heap_last = index_begin + offset;
 110             int heap_first = Qptr->size() - 1;
 111
 112             // pop_heap functionality:
 113             // swap first, last
 114             std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);
 115
 116             // swap in the location queue
 117             std::swap(Qlocation[heap_first], Qlocation[heap_last]);
 118
 119             // set drifter, children
 120             int drifter = heap_first;
 121             int drifter_heap = Qptr->size() - drifter;
 122
 123             int right_child_heap = drifter_heap * 2 + 1;
 124             int right_child = Qptr->size() - right_child_heap;
 125
 126             int left_child_heap = drifter_heap * 2;
 127             int left_child = Qptr->size() - left_child_heap;
 128
 129             // check that we are staying in the heap
 130             bool valid = (right_child < heap_last) ? false : true;
 131
 132             // pick smallest child of drifter, and keep in mind there might only
 133             // be left child
 134             int smallest_child = (valid
 135                                      && get(degree, (*Qptr)[left_child])
 136                                          > get(degree, (*Qptr)[right_child]))
 137                 ? right_child
 138                 : left_child;
 139
 140             while (valid && smallest_child < heap_last
 141                 && comp((*Qptr)[drifter], (*Qptr)[smallest_child]))
 142             {
 143
 144                 // if smallest child smaller than drifter, swap them
 145                 std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]);
 146                 std::swap(Qlocation[drifter], Qlocation[smallest_child]);
 147
 148                 // update the values, run again, as necessary
 149                 drifter = smallest_child;
 150                 drifter_heap = Qptr->size() - drifter;
 151
 152                 right_child_heap = drifter_heap * 2 + 1;
 153                 right_child = Qptr->size() - right_child_heap;
 154
 155                 left_child_heap = drifter_heap * 2;
 156                 left_child = Qptr->size() - left_child_heap;
 157
 158                 valid = (right_child < heap_last) ? false : true;
 159
 160                 smallest_child = (valid
 161                                      && get(degree, (*Qptr)[left_child])
 162                                          > get(degree, (*Qptr)[right_child]))
 163                     ? right_child
 164                     : left_child;
 165             }
 166         }
 167
 168         // this is like percolate down, but we always compare against the
 169         // parent, as there is only a single choice
 170         template < typename Vertex > void percolate_up(int vertex, int offset)
 171         {
 172
 173             int child_location = Qlocation[vertex];
 174             int heap_child_location = Qptr->size() - child_location;
 175             int heap_parent_location = (int)(heap_child_location / 2);
 176             unsigned parent_location = Qptr->size() - heap_parent_location;
 177
 178             bool valid = (heap_parent_location != 0
 179                 && child_location > index_begin + offset
 180                 && parent_location < Qptr->size());
 181
 182             while (valid
 183                 && comp((*Qptr)[child_location], (*Qptr)[parent_location]))
 184             {
 185
 186                 // swap in the heap
 187                 std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);
 188
 189                 // swap in the location queue
 190                 std::swap(
 191                     Qlocation[child_location], Qlocation[parent_location]);
 192
 193                 child_location = parent_location;
 194                 heap_child_location = heap_parent_location;
 195                 heap_parent_location = (int)(heap_child_location / 2);
 196                 parent_location = Qptr->size() - heap_parent_location;
 197                 valid = (heap_parent_location != 0
 198                     && child_location > index_begin + offset);
 199             }
 200         }
 201
 202         OutputIterator* permutation;
 203         int index_begin;
 204         Buffer* Qptr;
 205         PseudoDegreeMap degree;
 206         Compare comp;
 207         std::vector< int > Qlocation;
 208         VecMap colors;
 209         VertexIndexMap vertex_map;
 210     };
 211
 212 } // namespace detail
 213
 214 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
 215     typename VertexIndexMap >
 216 OutputIterator king_ordering(const Graph& g,
 217     std::deque< typename graph_traits< Graph >::vertex_descriptor >
 218         vertex_queue,
 219     OutputIterator permutation, ColorMap color, DegreeMap degree,
 220     VertexIndexMap index_map)
 221 {
 222     typedef typename property_traits< DegreeMap >::value_type ds_type;
 223     typedef typename property_traits< ColorMap >::value_type ColorValue;
 224     typedef color_traits< ColorValue > Color;
 225     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
 226     typedef iterator_property_map< typename std::vector< ds_type >::iterator,
 227         VertexIndexMap, ds_type, ds_type& >
 228         PseudoDegreeMap;
 229     typedef indirect_cmp< PseudoDegreeMap, std::less< ds_type > > Compare;
 230     typedef typename boost::sparse::sparse_ordering_queue< Vertex > queue;
 231     typedef typename detail::bfs_king_visitor< OutputIterator, queue, Compare,
 232         PseudoDegreeMap, std::vector< int >, VertexIndexMap >
 233         Visitor;
 234     typedef
 235         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
 236     std::vector< ds_type > pseudo_degree_vec(num_vertices(g));
 237     PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);
 238
 239     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
 240     queue Q;
 241     // Copy degree to pseudo_degree
 242     // initialize the color map
 243     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
 244     {
 245         put(pseudo_degree, *ui, get(degree, *ui));
 246         put(color, *ui, Color::white());
 247     }
 248
 249     Compare comp(pseudo_degree);
 250     std::vector< int > colors(num_vertices(g));
 251
 252     for (vertices_size_type i = 0; i < num_vertices(g); i++)
 253         colors[i] = 0;
 254
 255     std::vector< int > loc(num_vertices(g));
 256
 257     // create the visitor
 258     Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);
 259
 260     while (!vertex_queue.empty())
 261     {
 262         Vertex s = vertex_queue.front();
 263         vertex_queue.pop_front();
 264
 265         // call BFS with visitor
 266         breadth_first_visit(g, s, Q, vis, color);
 267     }
 268
 269     return permutation;
 270 }
 271
 272 // This is the case where only a single starting vertex is supplied.
 273 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
 274     typename VertexIndexMap >
 275 OutputIterator king_ordering(const Graph& g,
 276     typename graph_traits< Graph >::vertex_descriptor s,
 277     OutputIterator permutation, ColorMap color, DegreeMap degree,
 278     VertexIndexMap index_map)
 279 {
 280
 281     std::deque< typename graph_traits< Graph >::vertex_descriptor >
 282         vertex_queue;
 283     vertex_queue.push_front(s);
 284     return king_ordering(
 285         g, vertex_queue, permutation, color, degree, index_map);
 286 }
 287
 288 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
 289     class VertexIndexMap >
 290 OutputIterator king_ordering(const Graph& G, OutputIterator permutation,
 291     ColorMap color, DegreeMap degree, VertexIndexMap index_map)
 292 {
 293     if (has_no_vertices(G))
 294         return permutation;
 295
 296     typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
 297     typedef typename property_traits< ColorMap >::value_type ColorValue;
 298     typedef color_traits< ColorValue > Color;
 299
 300     std::deque< Vertex > vertex_queue;
 301
 302     // Mark everything white
 303     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
 304
 305     // Find one vertex from each connected component
 306     BGL_FORALL_VERTICES_T(v, G, Graph)
 307     {
 308         if (get(color, v) == Color::white())
 309         {
 310             depth_first_visit(G, v, dfs_visitor<>(), color);
 311             vertex_queue.push_back(v);
 312         }
 313     }
 314
 315     // Find starting nodes for all vertices
 316     // TBD: How to do this with a directed graph?
 317     for (typename std::deque< Vertex >::iterator i = vertex_queue.begin();
 318          i != vertex_queue.end(); ++i)
 319         *i = find_starting_node(G, *i, color, degree);
 320
 321     return king_ordering(
 322         G, vertex_queue, permutation, color, degree, index_map);
 323 }
 324
 325 template < typename Graph, typename OutputIterator, typename VertexIndexMap >
 326 OutputIterator king_ordering(
 327     const Graph& G, OutputIterator permutation, VertexIndexMap index_map)
 328 {
 329     if (has_no_vertices(G))
 330         return permutation;
 331
 332     std::vector< default_color_type > colors(num_vertices(G));
 333     return king_ordering(G, permutation,
 334         make_iterator_property_map(&colors[0], index_map, colors[0]),
 335         make_out_degree_map(G), index_map);
 336 }
 337
 338 template < typename Graph, typename OutputIterator >
 339 inline OutputIterator king_ordering(const Graph& G, OutputIterator permutation)
 340 {
 341     return king_ordering(G, permutation, get(vertex_index, G));
 342 }
 343
 344 } // namespace boost
 345
 346 #endif // BOOST_GRAPH_KING_HPP