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
24namespace 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 graph_traits<Graph>::vertex_descriptor Vertex;
79 typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
80 typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
81 typedef typename property_traits<ColorMap>::value_type ColorValue;
82 typedef color_traits<ColorValue> Color;
83
84
85 queue Q;
86
87 //create a bfs_rcm_visitor as defined above
88 Visitor vis(&permutation, &Q, degree);
89
90 typename graph_traits<Graph>::vertex_iterator ui, ui_end;
91
92 // Copy degree to pseudo_degree
93 // initialize the color map
94 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui){
95 put(color, *ui, Color::white());
96 }
97
98
99 while( !vertex_queue.empty() ) {
100 Vertex s = vertex_queue.front();
101 vertex_queue.pop_front();
102
103 //call BFS with visitor
104 breadth_first_visit(g, s, Q, vis, color);
105 }
106 return permutation;
107 }
108
109
110 // This is the case where only a single starting vertex is supplied.
111 template <class Graph, class OutputIterator,
112 class ColorMap, class DegreeMap>
113 OutputIterator
114 cuthill_mckee_ordering(const Graph& g,
115 typename graph_traits<Graph>::vertex_descriptor s,
116 OutputIterator permutation,
117 ColorMap color, DegreeMap degree)
118 {
119
120 std::deque< typename graph_traits<Graph>::vertex_descriptor > vertex_queue;
121 vertex_queue.push_front( s );
122
123 return cuthill_mckee_ordering(g, vertex_queue, permutation, color, degree);
124
125 }
126
127
128 // This is the version of CM which selects its own starting vertex
129 template < class Graph, class OutputIterator,
130 class ColorMap, class DegreeMap>
131 OutputIterator
132 cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
133 ColorMap color, DegreeMap degree)
134 {
135 if (boost::graph::has_no_vertices(G))
136 return permutation;
137
138 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
139 typedef typename property_traits<ColorMap>::value_type ColorValue;
140 typedef color_traits<ColorValue> Color;
141
142 std::deque<Vertex> vertex_queue;
143
144 // Mark everything white
145 BGL_FORALL_VERTICES_T(v, G, Graph) put(color, v, Color::white());
146
147 // Find one vertex from each connected component
148 BGL_FORALL_VERTICES_T(v, G, Graph) {
149 if (get(color, v) == Color::white()) {
150 depth_first_visit(G, v, dfs_visitor<>(), color);
151 vertex_queue.push_back(v);
152 }
153 }
154
155 // Find starting nodes for all vertices
156 // TBD: How to do this with a directed graph?
157 for (typename std::deque<Vertex>::iterator i = vertex_queue.begin();
158 i != vertex_queue.end(); ++i)
159 *i = find_starting_node(G, *i, color, degree);
160
161 return cuthill_mckee_ordering(G, vertex_queue, permutation,
162 color, degree);
163 }
164
165 template<typename Graph, typename OutputIterator, typename VertexIndexMap>
166 OutputIterator
167 cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
168 VertexIndexMap index_map)
169 {
170 if (boost::graph::has_no_vertices(G))
171 return permutation;
172
173 std::vector<default_color_type> colors(num_vertices(G));
174 return cuthill_mckee_ordering(G, permutation,
175 make_iterator_property_map(&colors[0],
176 index_map,
177 colors[0]),
178 make_out_degree_map(G));
179 }
180
181 template<typename Graph, typename OutputIterator>
182 inline OutputIterator
183 cuthill_mckee_ordering(const Graph& G, OutputIterator permutation)
184 { return cuthill_mckee_ordering(G, permutation, get(vertex_index, G)); }
185} // namespace boost
186
187
188#endif // BOOST_GRAPH_CUTHILL_MCKEE_HPP
189

source code of boost/boost/graph/cuthill_mckee_ordering.hpp