git.sesse.net Git - casparcg/blob - dependencies/boost/boost/graph/cuthill_mckee_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_CUTHILL_MCKEE_HPP
  12 #define BOOST_GRAPH_CUTHILL_MCKEE_HPP
  13
  14 #include <boost/config.hpp>
  15 #include <boost/graph/detail/sparse_ordering.hpp>
  16 #include <boost/graph/graph_utility.hpp>
  17 #include <algorithm>
  18
  19
  20 /*
  21   (Reverse) Cuthill-McKee Algorithm for matrix reordering
  22 */
  23
  24 namespace boost {
  25
  26   namespace detail {
  27
  28
  29
  30     template < typename OutputIterator, typename Buffer, typename DegreeMap >
  31     class bfs_rcm_visitor:public default_bfs_visitor
  32     {
  33     public:
  34       bfs_rcm_visitor(OutputIterator *iter, Buffer *b, DegreeMap deg):
  35         permutation(iter), Qptr(b), degree(deg) { }
  36       template <class Vertex, class Graph>
  37       void examine_vertex(Vertex u, Graph&) {
  38         *(*permutation)++ = u;
  39         index_begin = Qptr->size();
  40       }
  41       template <class Vertex, class Graph>
  42       void finish_vertex(Vertex, Graph&) {
  43         using std::sort;
  44
  45         typedef typename property_traits<DegreeMap>::value_type ds_type;
  46
  47         typedef indirect_cmp<DegreeMap, std::less<ds_type> > Compare;
  48         Compare comp(degree);
  49
  50         sort(Qptr->begin()+index_begin, Qptr->end(), comp);
  51       }
  52     protected:
  53       OutputIterator *permutation;
  54       int index_begin;
  55       Buffer *Qptr;
  56       DegreeMap degree;
  57     };
  58
  59   } // namespace detail
  60
  61
  62   // Reverse Cuthill-McKee algorithm with a given starting Vertex.
  63   //
  64   // If user provides a reverse iterator, this will be a reverse-cuthill-mckee
  65   // algorithm, otherwise it will be a standard CM algorithm
  66
  67   template <class Graph, class OutputIterator,
  68             class ColorMap, class DegreeMap>
  69   OutputIterator
  70   cuthill_mckee_ordering(const Graph& g,
  71                          std::deque< typename
  72                          graph_traits<Graph>::vertex_descriptor > vertex_queue,
  73                          OutputIterator permutation,
  74                          ColorMap color, DegreeMap degree)
  75   {
  76
  77     //create queue, visitor...don't forget namespaces!
  78     typedef typename property_traits<DegreeMap>::value_type ds_type;
  79     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  80     typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
  81     typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
  82     typedef typename property_traits<ColorMap>::value_type ColorValue;
  83     typedef color_traits<ColorValue> Color;
  84
  85
  86     queue Q;
  87
  88     //create a bfs_rcm_visitor as defined above
  89     Visitor     vis(&permutation, &Q, degree);
  90
  91     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
  92
  93     // Copy degree to pseudo_degree
  94     // initialize the color map
  95     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
  96       put(color, *ui, Color::white());
  97     }
  98
  99
 100     while( !vertex_queue.empty() ) {
 101       Vertex s = vertex_queue.front();
 102       vertex_queue.pop_front();
 103
 104       //call BFS with visitor
 105       breadth_first_visit(g, s, Q, vis, color);
 106     }
 107     return permutation;
 108   }
 109
 110
 111   // This is the case where only a single starting vertex is supplied.
 112   template <class Graph, class OutputIterator,
 113             class ColorMap, class DegreeMap>
 114   OutputIterator
 115   cuthill_mckee_ordering(const Graph& g,
 116                          typename graph_traits<Graph>::vertex_descriptor s,
 117                          OutputIterator permutation,
 118                          ColorMap color, DegreeMap degree)
 119   {
 120
 121     std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
 122     vertex_queue.push_front( s );
 123
 124     return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
 125
 126   }
 127
 128
 129   // This is the version of CM which selects its own starting vertex
 130   template < class Graph, class OutputIterator,
 131              class ColorMap, class DegreeMap>
 132   OutputIterator
 133   cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
 134                          ColorMap color, DegreeMap degree)
 135   {
 136     if (boost::graph::has_no_vertices(G))
 137       return permutation;
 138
 139     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
 140     typedef typename boost::graph_traits<Graph>::vertex_iterator   VerIter;
 141     typedef typename property_traits<ColorMap>::value_type ColorValue;
 142     typedef color_traits<ColorValue> Color;
 143
 144     std::deque<Vertex>      vertex_queue;
 145
 146     // Mark everything white
 147     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
 148
 149     // Find one vertex from each connected component
 150     BGL_FORALL_VERTICES_T(v, G, Graph) {
 151       if (get(color, v) == Color::white()) {
 152         depth_first_visit(G, v, dfs_visitor<>(), color);
 153         vertex_queue.push_back(v);
 154       }
 155     }
 156
 157     // Find starting nodes for all vertices
 158     // TBD: How to do this with a directed graph?
 159     for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
 160          i != vertex_queue.end(); ++i)
 161       *i = find_starting_node(G, *i, color, degree);
 162
 163     return cuthill_mckee_ordering(G, vertex_queue, permutation,
 164                                   color, degree);
 165   }
 166
 167   template<typename Graph, typename OutputIterator, typename VertexIndexMap>
 168   OutputIterator
 169   cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
 170                          VertexIndexMap index_map)
 171   {
 172     if (boost::graph::has_no_vertices(G))
 173       return permutation;
 174
 175     typedef out_degree_property_map<Graph> DegreeMap;
 176     std::vector<default_color_type> colors(num_vertices(G));
 177     return cuthill_mckee_ordering(G, permutation,
 178                                   make_iterator_property_map(&colors[0],
 179                                                              index_map,
 180                                                              colors[0]),
 181                                   make_out_degree_map(G));
 182   }
 183
 184   template<typename Graph, typename OutputIterator>
 185   inline OutputIterator
 186   cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)
 187   { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }
 188 } // namespace boost
 189
 190
 191 #endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP