boost/graph/king_ordering.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Copyright 2004, 2005 Trustees of Indiana University
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
0005 //          Doug Gregor, D. Kevin McGrath
0006 //
0007 // Distributed under the Boost Software License, Version 1.0. (See
0008 // accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //=======================================================================//
0011 #ifndef BOOST_GRAPH_KING_HPP
0012 #define BOOST_GRAPH_KING_HPP
0013
0014 #include <deque>
0015 #include <vector>
0016 #include <algorithm>
0017 #include <boost/config.hpp>
0018 #include <boost/bind/bind.hpp>
0019 #include <boost/tuple/tuple.hpp>
0020 #include <boost/graph/detail/sparse_ordering.hpp>
0021 #include <boost/graph/graph_utility.hpp>
0022
0023 /*
0024   King Algorithm for matrix reordering
0025 */
0026
0027 namespace boost
0028 {
0029 namespace detail
0030 {
0031     template < typename OutputIterator, typename Buffer, typename Compare,
0032         typename PseudoDegreeMap, typename VecMap, typename VertexIndexMap >
0033     class bfs_king_visitor : public default_bfs_visitor
0034     {
0035     public:
0036         bfs_king_visitor(OutputIterator* iter, Buffer* b, Compare compare,
0037             PseudoDegreeMap deg, std::vector< int > loc, VecMap color,
0038             VertexIndexMap vertices)
0039         : permutation(iter)
0040         , Qptr(b)
0041         , degree(deg)
0042         , comp(compare)
0043         , Qlocation(loc)
0044         , colors(color)
0045         , vertex_map(vertices)
0046         {
0047         }
0048
0049         template < typename Vertex, typename Graph >
0050         void finish_vertex(Vertex, Graph& g)
0051         {
0052             using namespace boost::placeholders;
0053
0054             typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
0055             Vertex v, w;
0056
0057             typedef typename std::deque< Vertex >::reverse_iterator
0058                 reverse_iterator;
0059
0060             reverse_iterator rend = Qptr->rend() - index_begin;
0061             reverse_iterator rbegin = Qptr->rbegin();
0062
0063             // heap the vertices already there
0064             std::make_heap(rbegin, rend, boost::bind< bool >(comp, _2, _1));
0065
0066             unsigned i = 0;
0067
0068             for (i = index_begin; i != Qptr->size(); ++i)
0069             {
0070                 colors[get(vertex_map, (*Qptr)[i])] = 1;
0071                 Qlocation[get(vertex_map, (*Qptr)[i])] = i;
0072             }
0073
0074             i = 0;
0075
0076             for (; rbegin != rend; rend--)
0077             {
0078                 percolate_down< Vertex >(i);
0079                 w = (*Qptr)[index_begin + i];
0080                 for (boost::tie(ei, ei_end) = out_edges(w, g); ei != ei_end;
0081                      ++ei)
0082                 {
0083                     v = target(*ei, g);
0084                     put(degree, v, get(degree, v) - 1);
0085
0086                     if (colors[get(vertex_map, v)] == 1)
0087                     {
0088                         percolate_up< Vertex >(get(vertex_map, v), i);
0089                     }
0090                 }
0091
0092                 colors[get(vertex_map, w)] = 0;
0093                 i++;
0094             }
0095         }
0096
0097         template < typename Vertex, typename Graph >
0098         void examine_vertex(Vertex u, const Graph&)
0099         {
0100
0101             *(*permutation)++ = u;
0102             index_begin = Qptr->size();
0103         }
0104
0105     protected:
0106         // this function replaces pop_heap, and tracks state information
0107         template < typename Vertex > void percolate_down(int offset)
0108         {
0109             int heap_last = index_begin + offset;
0110             int heap_first = Qptr->size() - 1;
0111
0112             // pop_heap functionality:
0113             // swap first, last
0114             std::swap((*Qptr)[heap_last], (*Qptr)[heap_first]);
0115
0116             // swap in the location queue
0117             std::swap(Qlocation[heap_first], Qlocation[heap_last]);
0118
0119             // set drifter, children
0120             int drifter = heap_first;
0121             int drifter_heap = Qptr->size() - drifter;
0122
0123             int right_child_heap = drifter_heap * 2 + 1;
0124             int right_child = Qptr->size() - right_child_heap;
0125
0126             int left_child_heap = drifter_heap * 2;
0127             int left_child = Qptr->size() - left_child_heap;
0128
0129             // check that we are staying in the heap
0130             bool valid = (right_child < heap_last) ? false : true;
0131
0132             // pick smallest child of drifter, and keep in mind there might only
0133             // be left child
0134             int smallest_child = (valid
0135                                      && get(degree, (*Qptr)[left_child])
0136                                          > get(degree, (*Qptr)[right_child]))
0137                 ? right_child
0138                 : left_child;
0139
0140             while (valid && smallest_child < heap_last
0141                 && comp((*Qptr)[drifter], (*Qptr)[smallest_child]))
0142             {
0143
0144                 // if smallest child smaller than drifter, swap them
0145                 std::swap((*Qptr)[smallest_child], (*Qptr)[drifter]);
0146                 std::swap(Qlocation[drifter], Qlocation[smallest_child]);
0147
0148                 // update the values, run again, as necessary
0149                 drifter = smallest_child;
0150                 drifter_heap = Qptr->size() - drifter;
0151
0152                 right_child_heap = drifter_heap * 2 + 1;
0153                 right_child = Qptr->size() - right_child_heap;
0154
0155                 left_child_heap = drifter_heap * 2;
0156                 left_child = Qptr->size() - left_child_heap;
0157
0158                 valid = (right_child < heap_last) ? false : true;
0159
0160                 smallest_child = (valid
0161                                      && get(degree, (*Qptr)[left_child])
0162                                          > get(degree, (*Qptr)[right_child]))
0163                     ? right_child
0164                     : left_child;
0165             }
0166         }
0167
0168         // this is like percolate down, but we always compare against the
0169         // parent, as there is only a single choice
0170         template < typename Vertex > void percolate_up(int vertex, int offset)
0171         {
0172
0173             int child_location = Qlocation[vertex];
0174             int heap_child_location = Qptr->size() - child_location;
0175             int heap_parent_location = (int)(heap_child_location / 2);
0176             unsigned parent_location = Qptr->size() - heap_parent_location;
0177
0178             bool valid = (heap_parent_location != 0
0179                 && child_location > index_begin + offset
0180                 && parent_location < Qptr->size());
0181
0182             while (valid
0183                 && comp((*Qptr)[child_location], (*Qptr)[parent_location]))
0184             {
0185
0186                 // swap in the heap
0187                 std::swap((*Qptr)[child_location], (*Qptr)[parent_location]);
0188
0189                 // swap in the location queue
0190                 std::swap(
0191                     Qlocation[child_location], Qlocation[parent_location]);
0192
0193                 child_location = parent_location;
0194                 heap_child_location = heap_parent_location;
0195                 heap_parent_location = (int)(heap_child_location / 2);
0196                 parent_location = Qptr->size() - heap_parent_location;
0197                 valid = (heap_parent_location != 0
0198                     && child_location > index_begin + offset);
0199             }
0200         }
0201
0202         OutputIterator* permutation;
0203         int index_begin;
0204         Buffer* Qptr;
0205         PseudoDegreeMap degree;
0206         Compare comp;
0207         std::vector< int > Qlocation;
0208         VecMap colors;
0209         VertexIndexMap vertex_map;
0210     };
0211
0212 } // namespace detail
0213
0214 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
0215     typename VertexIndexMap >
0216 OutputIterator king_ordering(const Graph& g,
0217     std::deque< typename graph_traits< Graph >::vertex_descriptor >
0218         vertex_queue,
0219     OutputIterator permutation, ColorMap color, DegreeMap degree,
0220     VertexIndexMap index_map)
0221 {
0222     typedef typename property_traits< DegreeMap >::value_type ds_type;
0223     typedef typename property_traits< ColorMap >::value_type ColorValue;
0224     typedef color_traits< ColorValue > Color;
0225     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0226     typedef iterator_property_map< typename std::vector< ds_type >::iterator,
0227         VertexIndexMap, ds_type, ds_type& >
0228         PseudoDegreeMap;
0229     typedef indirect_cmp< PseudoDegreeMap, std::less< ds_type > > Compare;
0230     typedef typename boost::sparse::sparse_ordering_queue< Vertex > queue;
0231     typedef typename detail::bfs_king_visitor< OutputIterator, queue, Compare,
0232         PseudoDegreeMap, std::vector< int >, VertexIndexMap >
0233         Visitor;
0234     typedef
0235         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0236     std::vector< ds_type > pseudo_degree_vec(num_vertices(g));
0237     PseudoDegreeMap pseudo_degree(pseudo_degree_vec.begin(), index_map);
0238
0239     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0240     queue Q;
0241     // Copy degree to pseudo_degree
0242     // initialize the color map
0243     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0244     {
0245         put(pseudo_degree, *ui, get(degree, *ui));
0246         put(color, *ui, Color::white());
0247     }
0248
0249     Compare comp(pseudo_degree);
0250     std::vector< int > colors(num_vertices(g));
0251
0252     for (vertices_size_type i = 0; i < num_vertices(g); i++)
0253         colors[i] = 0;
0254
0255     std::vector< int > loc(num_vertices(g));
0256
0257     // create the visitor
0258     Visitor vis(&permutation, &Q, comp, pseudo_degree, loc, colors, index_map);
0259
0260     while (!vertex_queue.empty())
0261     {
0262         Vertex s = vertex_queue.front();
0263         vertex_queue.pop_front();
0264
0265         // call BFS with visitor
0266         breadth_first_visit(g, s, Q, vis, color);
0267     }
0268
0269     return permutation;
0270 }
0271
0272 // This is the case where only a single starting vertex is supplied.
0273 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
0274     typename VertexIndexMap >
0275 OutputIterator king_ordering(const Graph& g,
0276     typename graph_traits< Graph >::vertex_descriptor s,
0277     OutputIterator permutation, ColorMap color, DegreeMap degree,
0278     VertexIndexMap index_map)
0279 {
0280
0281     std::deque< typename graph_traits< Graph >::vertex_descriptor >
0282         vertex_queue;
0283     vertex_queue.push_front(s);
0284     return king_ordering(
0285         g, vertex_queue, permutation, color, degree, index_map);
0286 }
0287
0288 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap,
0289     class VertexIndexMap >
0290 OutputIterator king_ordering(const Graph& G, OutputIterator permutation,
0291     ColorMap color, DegreeMap degree, VertexIndexMap index_map)
0292 {
0293     if (has_no_vertices(G))
0294         return permutation;
0295
0296     typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
0297     typedef typename property_traits< ColorMap >::value_type ColorValue;
0298     typedef color_traits< ColorValue > Color;
0299
0300     std::deque< Vertex > vertex_queue;
0301
0302     // Mark everything white
0303     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
0304
0305     // Find one vertex from each connected component
0306     BGL_FORALL_VERTICES_T(v, G, Graph)
0307     {
0308         if (get(color, v) == Color::white())
0309         {
0310             depth_first_visit(G, v, dfs_visitor<>(), color);
0311             vertex_queue.push_back(v);
0312         }
0313     }
0314
0315     // Find starting nodes for all vertices
0316     // TBD: How to do this with a directed graph?
0317     for (typename std::deque< Vertex >::iterator i = vertex_queue.begin();
0318          i != vertex_queue.end(); ++i)
0319         *i = find_starting_node(G, *i, color, degree);
0320
0321     return king_ordering(
0322         G, vertex_queue, permutation, color, degree, index_map);
0323 }
0324
0325 template < typename Graph, typename OutputIterator, typename VertexIndexMap >
0326 OutputIterator king_ordering(
0327     const Graph& G, OutputIterator permutation, VertexIndexMap index_map)
0328 {
0329     if (has_no_vertices(G))
0330         return permutation;
0331
0332     std::vector< default_color_type > colors(num_vertices(G));
0333     return king_ordering(G, permutation,
0334         make_iterator_property_map(&colors[0], index_map, colors[0]),
0335         make_out_degree_map(G), index_map);
0336 }
0337
0338 template < typename Graph, typename OutputIterator >
0339 inline OutputIterator king_ordering(const Graph& G, OutputIterator permutation)
0340 {
0341     return king_ordering(G, permutation, get(vertex_index, G));
0342 }
0343
0344 } // namespace boost
0345
0346 #endif // BOOST_GRAPH_KING_HPP