]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
24 | namespace 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 |