Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Copyright 2004, 2005 Trustees of Indiana University
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
Chris@16: //          Doug Gregor, D. Kevin McGrath
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: #ifndef BOOST_GRAPH_CUTHILL_MCKEE_HPP
Chris@16: #define BOOST_GRAPH_CUTHILL_MCKEE_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/graph/detail/sparse_ordering.hpp>
Chris@16: #include <boost/graph/graph_utility.hpp>
Chris@16: #include <algorithm>
Chris@16: 
Chris@16: 
Chris@16: /*
Chris@16:   (Reverse) Cuthill-McKee Algorithm for matrix reordering
Chris@16: */
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     template < typename OutputIterator, typename Buffer, typename DegreeMap > 
Chris@16:     class bfs_rcm_visitor:public default_bfs_visitor
Chris@16:     {
Chris@16:     public:
Chris@16:       bfs_rcm_visitor(OutputIterator *iter, Buffer *b, DegreeMap deg): 
Chris@16:         permutation(iter), Qptr(b), degree(deg) { }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void examine_vertex(Vertex u, Graph&) {
Chris@16:         *(*permutation)++ = u;
Chris@16:         index_begin = Qptr->size();
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void finish_vertex(Vertex, Graph&) {
Chris@16:         using std::sort;
Chris@16: 
Chris@16:         typedef typename property_traits<DegreeMap>::value_type ds_type;
Chris@16: 
Chris@16:         typedef indirect_cmp<DegreeMap, std::less<ds_type> > Compare;
Chris@16:         Compare comp(degree);
Chris@16:                 
Chris@16:         sort(Qptr->begin()+index_begin, Qptr->end(), comp);
Chris@16:       }
Chris@16:     protected:
Chris@16:       OutputIterator *permutation;
Chris@16:       int index_begin;
Chris@16:       Buffer *Qptr;
Chris@16:       DegreeMap degree;
Chris@16:     };
Chris@16: 
Chris@16:   } // namespace detail  
Chris@16: 
Chris@16: 
Chris@16:   // Reverse Cuthill-McKee algorithm with a given starting Vertex.
Chris@16:   //
Chris@16:   // If user provides a reverse iterator, this will be a reverse-cuthill-mckee
Chris@16:   // algorithm, otherwise it will be a standard CM algorithm
Chris@16: 
Chris@16:   template <class Graph, class OutputIterator,
Chris@16:             class ColorMap, class DegreeMap>
Chris@16:   OutputIterator
Chris@16:   cuthill_mckee_ordering(const Graph& g,
Chris@16:                          std::deque< typename
Chris@16:                          graph_traits<Graph>::vertex_descriptor > vertex_queue,
Chris@16:                          OutputIterator permutation, 
Chris@16:                          ColorMap color, DegreeMap degree)
Chris@16:   {
Chris@16: 
Chris@16:     //create queue, visitor...don't forget namespaces!
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
Chris@16:     typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
Chris@16:     typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:     typedef color_traits<ColorValue> Color;
Chris@16: 
Chris@16: 
Chris@16:     queue Q;
Chris@16: 
Chris@16:     //create a bfs_rcm_visitor as defined above
Chris@16:     Visitor     vis(&permutation, &Q, degree);
Chris@16: 
Chris@16:     typename graph_traits<Graph>::vertex_iterator ui, ui_end;    
Chris@16: 
Chris@16:     // Copy degree to pseudo_degree
Chris@16:     // initialize the color map
Chris@16:     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
Chris@16:       put(color, *ui, Color::white());
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     while( !vertex_queue.empty() ) {
Chris@16:       Vertex s = vertex_queue.front();
Chris@16:       vertex_queue.pop_front();
Chris@16:       
Chris@16:       //call BFS with visitor
Chris@16:       breadth_first_visit(g, s, Q, vis, color);
Chris@16:     }
Chris@16:     return permutation;
Chris@16:   }
Chris@16:     
Chris@16: 
Chris@16:   // This is the case where only a single starting vertex is supplied.
Chris@16:   template <class Graph, class OutputIterator,
Chris@16:             class ColorMap, class DegreeMap>
Chris@16:   OutputIterator
Chris@16:   cuthill_mckee_ordering(const Graph& g,
Chris@16:                          typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                          OutputIterator permutation, 
Chris@16:                          ColorMap color, DegreeMap degree)
Chris@16:   {
Chris@16: 
Chris@16:     std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
Chris@16:     vertex_queue.push_front( s );
Chris@16: 
Chris@16:     return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
Chris@16:   
Chris@16:   }
Chris@16:   
Chris@16: 
Chris@16:   // This is the version of CM which selects its own starting vertex
Chris@16:   template < class Graph, class OutputIterator, 
Chris@16:              class ColorMap, class DegreeMap>
Chris@16:   OutputIterator 
Chris@16:   cuthill_mckee_ordering(const Graph& G, OutputIterator permutation, 
Chris@16:                          ColorMap color, DegreeMap degree)
Chris@16:   {
Chris@16:     if (boost::graph::has_no_vertices(G))
Chris@16:       return permutation;
Chris@16: 
Chris@16:     typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:     typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16:     typedef color_traits<ColorValue> Color;
Chris@16: 
Chris@16:     std::deque<Vertex>      vertex_queue;
Chris@16: 
Chris@16:     // Mark everything white
Chris@16:     BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
Chris@16: 
Chris@16:     // Find one vertex from each connected component 
Chris@16:     BGL_FORALL_VERTICES_T(v, G, Graph) {
Chris@16:       if (get(color, v) == Color::white()) {
Chris@16:         depth_first_visit(G, v, dfs_visitor<>(), color);
Chris@16:         vertex_queue.push_back(v);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // Find starting nodes for all vertices
Chris@16:     // TBD: How to do this with a directed graph?
Chris@16:     for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
Chris@16:          i != vertex_queue.end(); ++i)
Chris@16:       *i = find_starting_node(G, *i, color, degree);
Chris@16:     
Chris@16:     return cuthill_mckee_ordering(G, vertex_queue, permutation,
Chris@16:                                   color, degree);
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename OutputIterator, typename VertexIndexMap>
Chris@16:   OutputIterator 
Chris@16:   cuthill_mckee_ordering(const Graph& G, OutputIterator permutation, 
Chris@16:                          VertexIndexMap index_map)
Chris@16:   {
Chris@16:     if (boost::graph::has_no_vertices(G))
Chris@16:       return permutation;
Chris@16:     
Chris@16:     std::vector<default_color_type> colors(num_vertices(G));
Chris@16:     return cuthill_mckee_ordering(G, permutation, 
Chris@16:                                   make_iterator_property_map(&colors[0], 
Chris@16:                                                              index_map,
Chris@16:                                                              colors[0]),
Chris@16:                                   make_out_degree_map(G));
Chris@16:   }
Chris@16: 
Chris@16:   template<typename Graph, typename OutputIterator>
Chris@16:   inline OutputIterator 
Chris@16:   cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)
Chris@16:   { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }
Chris@16: } // namespace boost
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP