]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2005 The Trustees of Indiana University. |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | #ifndef BOOST_GRAPH_METIS_HPP | |
10 | #define BOOST_GRAPH_METIS_HPP | |
11 | ||
12 | #ifdef BOOST_GRAPH_METIS_NO_INLINE | |
13 | # define BOOST_GRAPH_METIS_INLINE_KEYWORD | |
14 | #else | |
15 | # define BOOST_GRAPH_METIS_INLINE_KEYWORD inline | |
16 | #endif | |
17 | ||
18 | #include <string> | |
19 | #include <iostream> | |
20 | #include <iterator> | |
21 | #include <utility> | |
22 | #include <sstream> | |
23 | #include <exception> | |
24 | #include <vector> | |
25 | #include <algorithm> | |
26 | ||
27 | namespace boost { namespace graph { | |
28 | ||
29 | class metis_exception : public std::exception {}; | |
30 | class metis_input_exception : public metis_exception {}; | |
31 | ||
32 | class metis_reader | |
33 | { | |
34 | public: | |
35 | typedef std::size_t vertices_size_type; | |
36 | typedef std::size_t edges_size_type; | |
37 | typedef double vertex_weight_type; | |
38 | typedef double edge_weight_type; | |
39 | ||
40 | class edge_iterator | |
41 | { | |
42 | public: | |
43 | typedef std::input_iterator_tag iterator_category; | |
44 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
45 | typedef const value_type& reference; | |
46 | typedef const value_type* pointer; | |
47 | typedef std::ptrdiff_t difference_type; | |
48 | ||
49 | private: | |
50 | class postincrement_proxy | |
51 | { | |
52 | postincrement_proxy(const value_type& value) : value(value) { } | |
53 | ||
54 | public: | |
55 | reference operator*() const { return value; } | |
56 | ||
57 | private: | |
58 | value_type value; | |
59 | friend class edge_iterator; | |
60 | }; | |
61 | ||
62 | public: | |
63 | edge_iterator& operator++(); | |
64 | postincrement_proxy operator++(int); | |
65 | ||
66 | reference operator*() const { return self->edge; } | |
67 | pointer operator->() const { return &self->edge; } | |
68 | ||
69 | // Default copy constructor and assignment operator are okay | |
70 | ||
71 | private: | |
72 | edge_iterator(metis_reader* self); | |
73 | void advance(bool skip_initial_read); | |
74 | ||
75 | metis_reader* self; | |
76 | ||
77 | friend class metis_reader; | |
78 | friend bool operator==(edge_iterator, edge_iterator); | |
79 | friend bool operator!=(edge_iterator, edge_iterator); | |
80 | }; | |
81 | friend class edge_iterator; | |
82 | ||
83 | class edge_weight_iterator | |
84 | { | |
85 | public: | |
86 | typedef std::input_iterator_tag iterator_category; | |
87 | typedef edge_weight_type value_type; | |
88 | typedef const value_type& reference; | |
89 | typedef const value_type* pointer; | |
90 | ||
91 | // Default copy constructor and assignment operator are okay | |
92 | ||
93 | reference operator*() const { return self->edge_weight; } | |
94 | pointer operator->() const { return &self->edge_weight; } | |
95 | ||
96 | edge_weight_iterator& operator++() { return *this; } | |
97 | edge_weight_iterator operator++(int) { return *this; } | |
98 | ||
99 | private: | |
100 | edge_weight_iterator(metis_reader* self) : self(self) { } | |
101 | ||
102 | metis_reader* self; | |
103 | ||
104 | friend class metis_reader; | |
105 | }; | |
106 | ||
107 | metis_reader(std::istream& in) : in(in), edge_weight(1.0) { start(); } | |
108 | ||
109 | edge_iterator begin(); | |
110 | edge_iterator end(); | |
111 | edge_weight_iterator weight_begin(); | |
112 | ||
113 | vertices_size_type num_vertices() const { return n_vertices; } | |
114 | edges_size_type num_edges() const { return n_edges; } | |
115 | ||
116 | std::size_t num_vertex_weights() const { return n_vertex_weights; } | |
117 | ||
118 | vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n) | |
119 | { return vertex_weights[v*num_vertex_weights() + n]; } | |
120 | ||
121 | bool has_edge_weights() const { return edge_weights; } | |
122 | ||
123 | private: | |
124 | void start(); | |
125 | ||
126 | // Configuration information | |
127 | std::istream& in; | |
128 | ||
129 | // Information about the current METIS file | |
130 | vertices_size_type n_vertices; | |
131 | edges_size_type n_edges; | |
132 | std::size_t n_vertex_weights; | |
133 | bool edge_weights; | |
134 | ||
135 | // Information about the current edge/vertex | |
136 | std::istringstream line_in; | |
137 | std::pair<vertices_size_type, vertices_size_type> edge; | |
138 | std::vector<vertex_weight_type> vertex_weights; | |
139 | edge_weight_type edge_weight; | |
140 | ||
141 | friend bool operator==(edge_iterator, edge_iterator); | |
142 | friend bool operator!=(edge_iterator, edge_iterator); | |
143 | }; | |
144 | ||
145 | class metis_distribution | |
146 | { | |
147 | public: | |
148 | typedef int process_id_type; | |
149 | typedef std::size_t size_type; | |
150 | typedef std::vector<process_id_type>::iterator iterator; | |
151 | ||
152 | metis_distribution(std::istream& in, process_id_type my_id); | |
153 | ||
154 | size_type block_size(process_id_type id, size_type) const; | |
155 | process_id_type operator()(size_type n) const { return vertices[n]; } | |
156 | size_type local(size_type n) const; | |
157 | size_type global(size_type n) const { return global(my_id, n); } | |
158 | size_type global(process_id_type id, size_type n) const; | |
159 | ||
160 | iterator begin() { return vertices.begin(); } | |
161 | iterator end() { return vertices.end(); } | |
162 | ||
163 | private: | |
164 | process_id_type my_id; | |
165 | std::vector<process_id_type> vertices; | |
166 | }; | |
167 | ||
168 | #if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE) | |
169 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
170 | bool operator==(metis_reader::edge_iterator x, metis_reader::edge_iterator y) | |
171 | { | |
172 | return (x.self == y.self | |
173 | || (x.self && x.self->edge.first == x.self->num_vertices()) | |
174 | || (y.self && y.self->edge.first == y.self->num_vertices())); | |
175 | } | |
176 | ||
177 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
178 | bool operator!=(metis_reader::edge_iterator x, metis_reader::edge_iterator y) | |
179 | { | |
180 | return !(x == y); | |
181 | } | |
182 | ||
183 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
184 | metis_reader::edge_iterator::edge_iterator(metis_reader* self) | |
185 | : self(self) | |
186 | { | |
187 | if (self) advance(true); | |
188 | } | |
189 | ||
190 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
191 | metis_reader::edge_iterator& metis_reader::edge_iterator::operator++() | |
192 | { | |
193 | advance(false); | |
194 | return *this; | |
195 | } | |
196 | ||
197 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
198 | void metis_reader::edge_iterator::advance(bool skip_initial_read) | |
199 | { | |
200 | do { | |
201 | ||
202 | if (!skip_initial_read) { | |
203 | // Try to read the next edge | |
204 | if (self->line_in >> std::ws >> self->edge.second) { | |
205 | --self->edge.second; | |
206 | if (self->has_edge_weights()) { | |
207 | if (!(self->line_in >> self->edge_weight)) | |
208 | boost::throw_exception(metis_input_exception()); | |
209 | } | |
210 | return; | |
211 | } | |
212 | ||
213 | // Check if we're done | |
214 | ++self->edge.first; | |
215 | if (self->edge.first == self->num_vertices()) | |
216 | return; | |
217 | } | |
218 | ||
219 | // Find the next line | |
220 | std::string line; | |
221 | while (getline(self->in, line) && !line.empty() && line[0] == '%') { | |
222 | /* Keep reading lines in the loop header... */ | |
223 | } | |
224 | if (!self->in) boost::throw_exception(metis_input_exception()); | |
225 | self->line_in.str(line); | |
226 | self->line_in.clear(); | |
227 | ||
228 | // Read the next line | |
229 | std::size_t weights_left = self->n_vertex_weights; | |
230 | vertex_weight_type weight; | |
231 | while (weights_left > 0) { | |
232 | if (self->line_in >> weight) self->vertex_weights.push_back(weight); | |
233 | else boost::throw_exception(metis_input_exception()); | |
234 | --weights_left; | |
235 | } | |
236 | ||
237 | // Successive iterations will pick up edges for this vertex. | |
238 | skip_initial_read = false; | |
239 | } while (true); | |
240 | } | |
241 | ||
242 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
243 | metis_reader::edge_iterator::postincrement_proxy | |
244 | metis_reader::edge_iterator::operator++(int) | |
245 | { | |
246 | postincrement_proxy result(**this); | |
247 | ++(*this); | |
248 | return result; | |
249 | } | |
250 | ||
251 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
252 | metis_reader::edge_iterator metis_reader::begin() | |
253 | { | |
254 | if (edge.first != 0) start(); | |
255 | return edge_iterator(this); | |
256 | } | |
257 | ||
258 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
259 | metis_reader::edge_iterator metis_reader::end() | |
260 | { | |
261 | return edge_iterator(0); | |
262 | } | |
263 | ||
264 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
265 | metis_reader::edge_weight_iterator metis_reader::weight_begin() | |
266 | { | |
267 | return edge_weight_iterator(this); | |
268 | } | |
269 | ||
270 | BOOST_GRAPH_METIS_INLINE_KEYWORD | |
271 | void metis_reader::start() | |
272 | { | |
273 | in.seekg(0, std::ios::beg); | |
274 | std::string line; | |
275 | while (getline(in, line) && !line.empty() && line[0] == '%') { | |
276 | /* Keep getting lines in loop header. */ | |
277 | } | |
278 | ||
279 | if (!in || line.empty()) boost::throw_exception(metis_input_exception()); | |
280 | ||
281 | // Determine number of vertices and edges in the graph | |
282 | line_in.str(line); | |
283 | if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(metis_input_exception()); | |
284 | ||
285 | // Determine whether vertex or edge weights are included in the graph | |
286 | int fmt = 0; | |
287 | line_in >> fmt; | |
288 | n_vertex_weights = fmt / 10; | |
289 | edge_weights = (fmt % 10 == 1); | |
290 | ||
291 | // Determine how many (if any!) vertex weights are included | |
292 | if (n_vertex_weights) line_in >> n_vertex_weights; | |
293 | ||
294 | // Setup the iteration data structures | |
295 | edge_weight = 1.0; | |
296 | edge.first = 0; | |
297 | edge.second = 0; | |
298 | vertex_weights.reserve(n_vertex_weights * num_vertices()); | |
299 | } | |
300 | ||
301 | metis_distribution::metis_distribution(std::istream& in, process_id_type my_id) | |
302 | : my_id(my_id), | |
303 | vertices(std::istream_iterator<process_id_type>(in), | |
304 | std::istream_iterator<process_id_type>()) | |
305 | { | |
306 | } | |
307 | ||
308 | ||
309 | metis_distribution::size_type | |
310 | metis_distribution::block_size(process_id_type id, size_type) const | |
311 | { | |
312 | return std::count(vertices.begin(), vertices.end(), id); | |
313 | } | |
314 | ||
315 | metis_distribution::size_type metis_distribution::local(size_type n) const | |
316 | { | |
317 | return std::count(vertices.begin(), vertices.begin() + n, vertices[n]); | |
318 | } | |
319 | ||
320 | metis_distribution::size_type | |
321 | metis_distribution::global(process_id_type id, size_type n) const | |
322 | { | |
323 | std::vector<process_id_type>::const_iterator i = vertices.begin(); | |
324 | while (*i != id) ++i; | |
325 | ||
326 | while (n > 0) { | |
327 | do { ++i; } while (*i != id); | |
328 | --n; | |
329 | } | |
330 | ||
331 | return i - vertices.begin(); | |
332 | } | |
333 | ||
334 | #endif | |
335 | ||
336 | } } // end namespace boost::graph | |
337 | ||
338 | #endif // BOOST_GRAPH_METIS_HPP |