1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/cuthill_mckee_ordering.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,190 @@
1.4 +//=======================================================================
1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.6 +// Copyright 2004, 2005 Trustees of Indiana University
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
1.8 +// Doug Gregor, D. Kevin McGrath
1.9 +//
1.10 +// Distributed under the Boost Software License, Version 1.0. (See
1.11 +// accompanying file LICENSE_1_0.txt or copy at
1.12 +// http://www.boost.org/LICENSE_1_0.txt)
1.13 +//=======================================================================
1.14 +#ifndef BOOST_GRAPH_CUTHILL_MCKEE_HPP
1.15 +#define BOOST_GRAPH_CUTHILL_MCKEE_HPP
1.16 +
1.17 +#include <boost/config.hpp>
1.18 +#include <boost/graph/detail/sparse_ordering.hpp>
1.19 +#include <algorithm>
1.20 +
1.21 +
1.22 +/*
1.23 + (Reverse) Cuthill-McKee Algorithm for matrix reordering
1.24 +*/
1.25 +
1.26 +namespace boost {
1.27 +
1.28 + namespace detail {
1.29 +
1.30 +
1.31 +
1.32 + template < typename OutputIterator, typename Buffer, typename DegreeMap >
1.33 + class bfs_rcm_visitor:public default_bfs_visitor
1.34 + {
1.35 + public:
1.36 + bfs_rcm_visitor(OutputIterator *iter, Buffer *b, DegreeMap deg):
1.37 + permutation(iter), Qptr(b), degree(deg) { }
1.38 + template <class Vertex, class Graph>
1.39 + void examine_vertex(Vertex u, Graph&) {
1.40 + *(*permutation)++ = u;
1.41 + index_begin = Qptr->size();
1.42 + }
1.43 + template <class Vertex, class Graph>
1.44 + void finish_vertex(Vertex, Graph&) {
1.45 + using std::sort;
1.46 +
1.47 + typedef typename property_traits<DegreeMap>::value_type ds_type;
1.48 +
1.49 + typedef indirect_cmp<DegreeMap, std::less<ds_type> > Compare;
1.50 + Compare comp(degree);
1.51 +
1.52 + sort(Qptr->begin()+index_begin, Qptr->end(), comp);
1.53 + }
1.54 + protected:
1.55 + OutputIterator *permutation;
1.56 + int index_begin;
1.57 + Buffer *Qptr;
1.58 + DegreeMap degree;
1.59 + };
1.60 +
1.61 + } // namespace detail
1.62 +
1.63 +
1.64 + // Reverse Cuthill-McKee algorithm with a given starting Vertex.
1.65 + //
1.66 + // If user provides a reverse iterator, this will be a reverse-cuthill-mckee
1.67 + // algorithm, otherwise it will be a standard CM algorithm
1.68 +
1.69 + template <class Graph, class OutputIterator,
1.70 + class ColorMap, class DegreeMap>
1.71 + OutputIterator
1.72 + cuthill_mckee_ordering(const Graph& g,
1.73 + std::deque< typename
1.74 + graph_traits<Graph>::vertex_descriptor > vertex_queue,
1.75 + OutputIterator permutation,
1.76 + ColorMap color, DegreeMap degree)
1.77 + {
1.78 +
1.79 + //create queue, visitor...don't forget namespaces!
1.80 + typedef typename property_traits<DegreeMap>::value_type ds_type;
1.81 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.82 + typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
1.83 + typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
1.84 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.85 + typedef color_traits<ColorValue> Color;
1.86 +
1.87 +
1.88 + queue Q;
1.89 +
1.90 + //create a bfs_rcm_visitor as defined above
1.91 + Visitor vis(&permutation, &Q, degree);
1.92 +
1.93 + typename graph_traits<Graph>::vertex_iterator ui, ui_end;
1.94 +
1.95 + // Copy degree to pseudo_degree
1.96 + // initialize the color map
1.97 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
1.98 + put(color, *ui, Color::white());
1.99 + }
1.100 +
1.101 +
1.102 + while( !vertex_queue.empty() ) {
1.103 + Vertex s = vertex_queue.front();
1.104 + vertex_queue.pop_front();
1.105 +
1.106 + //call BFS with visitor
1.107 + breadth_first_visit(g, s, Q, vis, color);
1.108 + }
1.109 + return permutation;
1.110 + }
1.111 +
1.112 +
1.113 + // This is the case where only a single starting vertex is supplied.
1.114 + template <class Graph, class OutputIterator,
1.115 + class ColorMap, class DegreeMap>
1.116 + OutputIterator
1.117 + cuthill_mckee_ordering(const Graph& g,
1.118 + typename graph_traits<Graph>::vertex_descriptor s,
1.119 + OutputIterator permutation,
1.120 + ColorMap color, DegreeMap degree)
1.121 + {
1.122 +
1.123 + std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
1.124 + vertex_queue.push_front( s );
1.125 +
1.126 + return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
1.127 +
1.128 + }
1.129 +
1.130 +
1.131 + // This is the version of CM which selects its own starting vertex
1.132 + template < class Graph, class OutputIterator,
1.133 + class ColorMap, class DegreeMap>
1.134 + OutputIterator
1.135 + cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
1.136 + ColorMap color, DegreeMap degree)
1.137 + {
1.138 + if (vertices(G).first == vertices(G).second)
1.139 + return permutation;
1.140 +
1.141 + typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
1.142 + typedef typename boost::graph_traits<Graph>::vertex_iterator VerIter;
1.143 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.144 + typedef color_traits<ColorValue> Color;
1.145 +
1.146 + std::deque<Vertex> vertex_queue;
1.147 +
1.148 + // Mark everything white
1.149 + BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
1.150 +
1.151 + // Find one vertex from each connected component
1.152 + BGL_FORALL_VERTICES_T(v, G, Graph) {
1.153 + if (get(color, v) == Color::white()) {
1.154 + depth_first_visit(G, v, dfs_visitor<>(), color);
1.155 + vertex_queue.push_back(v);
1.156 + }
1.157 + }
1.158 +
1.159 + // Find starting nodes for all vertices
1.160 + // TBD: How to do this with a directed graph?
1.161 + for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
1.162 + i != vertex_queue.end(); ++i)
1.163 + *i = find_starting_node(G, *i, color, degree);
1.164 +
1.165 + return cuthill_mckee_ordering(G, vertex_queue, permutation,
1.166 + color, degree);
1.167 + }
1.168 +
1.169 + template<typename Graph, typename OutputIterator, typename VertexIndexMap>
1.170 + OutputIterator
1.171 + cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
1.172 + VertexIndexMap index_map)
1.173 + {
1.174 + if (vertices(G).first == vertices(G).second)
1.175 + return permutation;
1.176 +
1.177 + typedef out_degree_property_map<Graph> DegreeMap;
1.178 + std::vector<default_color_type> colors(num_vertices(G));
1.179 + return cuthill_mckee_ordering(G, permutation,
1.180 + make_iterator_property_map(&colors[0],
1.181 + index_map,
1.182 + colors[0]),
1.183 + make_out_degree_map(G));
1.184 + }
1.185 +
1.186 + template<typename Graph, typename OutputIterator>
1.187 + inline OutputIterator
1.188 + cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)
1.189 + { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }
1.190 +} // namespace boost
1.191 +
1.192 +
1.193 +#endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP