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