boost/graph/cuthill_mckee_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_CUTHILL_MCKEE_HPP
0012 #define BOOST_GRAPH_CUTHILL_MCKEE_HPP
0013
0014 #include <boost/config.hpp>
0015 #include <boost/graph/detail/sparse_ordering.hpp>
0016 #include <boost/graph/graph_utility.hpp>
0017 #include <algorithm>
0018
0019 /*
0020   (Reverse) Cuthill-McKee Algorithm for matrix reordering
0021 */
0022
0023 namespace boost
0024 {
0025
0026 namespace detail
0027 {
0028
0029     template < typename OutputIterator, typename Buffer, typename DegreeMap >
0030     class bfs_rcm_visitor : public default_bfs_visitor
0031     {
0032     public:
0033         bfs_rcm_visitor(OutputIterator* iter, Buffer* b, DegreeMap deg)
0034         : permutation(iter), Qptr(b), degree(deg)
0035         {
0036         }
0037         template < class Vertex, class Graph >
0038         void examine_vertex(Vertex u, Graph&)
0039         {
0040             *(*permutation)++ = u;
0041             index_begin = Qptr->size();
0042         }
0043         template < class Vertex, class Graph >
0044         void finish_vertex(Vertex, Graph&)
0045         {
0046             using std::sort;
0047
0048             typedef typename property_traits< DegreeMap >::value_type ds_type;
0049
0050             typedef indirect_cmp< DegreeMap, std::less< ds_type > > Compare;
0051             Compare comp(degree);
0052
0053             sort(Qptr->begin() + index_begin, Qptr->end(), comp);
0054         }
0055
0056     protected:
0057         OutputIterator* permutation;
0058         int index_begin;
0059         Buffer* Qptr;
0060         DegreeMap degree;
0061     };
0062
0063 } // namespace detail
0064
0065 // Reverse Cuthill-McKee algorithm with a given starting Vertex.
0066 //
0067 // If user provides a reverse iterator, this will be a reverse-cuthill-mckee
0068 // algorithm, otherwise it will be a standard CM algorithm
0069
0070 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap >
0071 OutputIterator cuthill_mckee_ordering(const Graph& g,
0072     std::deque< typename graph_traits< Graph >::vertex_descriptor >
0073         vertex_queue,
0074     OutputIterator permutation, ColorMap color, DegreeMap degree)
0075 {
0076
0077     // create queue, visitor...don't forget namespaces!
0078     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0079     typedef typename boost::sparse::sparse_ordering_queue< Vertex > queue;
0080     typedef typename detail::bfs_rcm_visitor< OutputIterator, queue, DegreeMap >
0081         Visitor;
0082     typedef typename property_traits< ColorMap >::value_type ColorValue;
0083     typedef color_traits< ColorValue > Color;
0084
0085     queue Q;
0086
0087     // create a bfs_rcm_visitor as defined above
0088     Visitor vis(&permutation, &Q, degree);
0089
0090     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0091
0092     // Copy degree to pseudo_degree
0093     // initialize the color map
0094     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0095     {
0096         put(color, *ui, Color::white());
0097     }
0098
0099     while (!vertex_queue.empty())
0100     {
0101         Vertex s = vertex_queue.front();
0102         vertex_queue.pop_front();
0103
0104         // call BFS with visitor
0105         breadth_first_visit(g, s, Q, vis, color);
0106     }
0107     return permutation;
0108 }
0109
0110 // This is the case where only a single starting vertex is supplied.
0111 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap >
0112 OutputIterator cuthill_mckee_ordering(const Graph& g,
0113     typename graph_traits< Graph >::vertex_descriptor s,
0114     OutputIterator permutation, ColorMap color, DegreeMap degree)
0115 {
0116
0117     std::deque< typename graph_traits< Graph >::vertex_descriptor >
0118         vertex_queue;
0119     vertex_queue.push_front(s);
0120
0121     return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
0122 }
0123
0124 // This is the version of CM which selects its own starting vertex
0125 template < class Graph, class OutputIterator, class ColorMap, class DegreeMap >
0126 OutputIterator cuthill_mckee_ordering(const Graph& G,
0127     OutputIterator permutation, ColorMap color, DegreeMap degree)
0128 {
0129     if (boost::graph::has_no_vertices(G))
0130         return permutation;
0131
0132     typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
0133     typedef typename property_traits< ColorMap >::value_type ColorValue;
0134     typedef color_traits< ColorValue > Color;
0135
0136     std::deque< Vertex > vertex_queue;
0137
0138     // Mark everything white
0139     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
0140
0141     // Find one vertex from each connected component
0142     BGL_FORALL_VERTICES_T(v, G, Graph)
0143     {
0144         if (get(color, v) == Color::white())
0145         {
0146             depth_first_visit(G, v, dfs_visitor<>(), color);
0147             vertex_queue.push_back(v);
0148         }
0149     }
0150
0151     // Find starting nodes for all vertices
0152     // TBD: How to do this with a directed graph?
0153     for (typename std::deque< Vertex >::iterator i = vertex_queue.begin();
0154          i != vertex_queue.end(); ++i)
0155         *i = find_starting_node(G, *i, color, degree);
0156
0157     return cuthill_mckee_ordering(G, vertex_queue, permutation, color, degree);
0158 }
0159
0160 template < typename Graph, typename OutputIterator, typename VertexIndexMap >
0161 OutputIterator cuthill_mckee_ordering(
0162     const Graph& G, OutputIterator permutation, VertexIndexMap index_map)
0163 {
0164     if (boost::graph::has_no_vertices(G))
0165         return permutation;
0166
0167     std::vector< default_color_type > colors(num_vertices(G));
0168     return cuthill_mckee_ordering(G, permutation,
0169         make_iterator_property_map(&colors[0], index_map, colors[0]),
0170         make_out_degree_map(G));
0171 }
0172
0173 template < typename Graph, typename OutputIterator >
0174 inline OutputIterator cuthill_mckee_ordering(
0175     const Graph& G, OutputIterator permutation)
0176 {
0177     return cuthill_mckee_ordering(G, permutation, get(vertex_index, G));
0178 }
0179 } // namespace boost
0180
0181 #endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP