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