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