epoc32/include/stdapis/boost/graph/king_ordering.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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