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(id: 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 | std::istream& in; |
165 | process_id_type my_id; |
166 | std::vector<process_id_type> vertices; |
167 | }; |
168 | |
169 | #if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE) |
170 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
171 | bool operator==(metis_reader::edge_iterator x, metis_reader::edge_iterator y) |
172 | { |
173 | return (x.self == y.self |
174 | || (x.self && x.self->edge.first == x.self->num_vertices()) |
175 | || (y.self && y.self->edge.first == y.self->num_vertices())); |
176 | } |
177 | |
178 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
179 | bool operator!=(metis_reader::edge_iterator x, metis_reader::edge_iterator y) |
180 | { |
181 | return !(x == y); |
182 | } |
183 | |
184 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
185 | metis_reader::edge_iterator::edge_iterator(metis_reader* self) |
186 | : self(self) |
187 | { |
188 | if (self) advance(skip_initial_read: true); |
189 | } |
190 | |
191 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
192 | metis_reader::edge_iterator& metis_reader::edge_iterator::operator++() |
193 | { |
194 | advance(skip_initial_read: false); |
195 | return *this; |
196 | } |
197 | |
198 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
199 | void metis_reader::edge_iterator::advance(bool skip_initial_read) |
200 | { |
201 | do { |
202 | |
203 | if (!skip_initial_read) { |
204 | // Try to read the next edge |
205 | if (self->line_in >> std::ws >> self->edge.second) { |
206 | --self->edge.second; |
207 | if (self->has_edge_weights()) { |
208 | if (!(self->line_in >> self->edge_weight)) |
209 | boost::throw_exception(e: metis_input_exception()); |
210 | } |
211 | return; |
212 | } |
213 | |
214 | // Check if we're done |
215 | ++self->edge.first; |
216 | if (self->edge.first == self->num_vertices()) |
217 | return; |
218 | } |
219 | |
220 | // Find the next line |
221 | std::string line; |
222 | while (getline(is&: self->in, str&: line) && !line.empty() && line[0] == '%') { |
223 | /* Keep reading lines in the loop header... */ |
224 | } |
225 | if (!self->in) boost::throw_exception(e: metis_input_exception()); |
226 | self->line_in.str(s: line); |
227 | self->line_in.clear(); |
228 | |
229 | // Read the next line |
230 | std::size_t weights_left = self->n_vertex_weights; |
231 | vertex_weight_type weight; |
232 | while (weights_left > 0) { |
233 | if (self->line_in >> weight) self->vertex_weights.push_back(x: weight); |
234 | else boost::throw_exception(e: metis_input_exception()); |
235 | --weights_left; |
236 | } |
237 | |
238 | // Successive iterations will pick up edges for this vertex. |
239 | skip_initial_read = false; |
240 | } while (true); |
241 | } |
242 | |
243 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
244 | metis_reader::edge_iterator::postincrement_proxy |
245 | metis_reader::edge_iterator::operator++(int) |
246 | { |
247 | postincrement_proxy result(**this); |
248 | ++(*this); |
249 | return result; |
250 | } |
251 | |
252 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
253 | metis_reader::edge_iterator metis_reader::begin() |
254 | { |
255 | if (edge.first != 0) start(); |
256 | return edge_iterator(this); |
257 | } |
258 | |
259 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
260 | metis_reader::edge_iterator metis_reader::end() |
261 | { |
262 | return edge_iterator(0); |
263 | } |
264 | |
265 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
266 | metis_reader::edge_weight_iterator metis_reader::weight_begin() |
267 | { |
268 | return edge_weight_iterator(this); |
269 | } |
270 | |
271 | BOOST_GRAPH_METIS_INLINE_KEYWORD |
272 | void metis_reader::start() |
273 | { |
274 | in.seekg(0, std::ios::beg); |
275 | std::string line; |
276 | while (getline(is&: in, str&: line) && !line.empty() && line[0] == '%') { |
277 | /* Keep getting lines in loop header. */ |
278 | } |
279 | |
280 | if (!in || line.empty()) boost::throw_exception(e: metis_input_exception()); |
281 | |
282 | // Determine number of vertices and edges in the graph |
283 | line_in.str(s: line); |
284 | if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(e: metis_input_exception()); |
285 | |
286 | // Determine whether vertex or edge weights are included in the graph |
287 | int fmt = 0; |
288 | line_in >> fmt; |
289 | n_vertex_weights = fmt / 10; |
290 | edge_weights = (fmt % 10 == 1); |
291 | |
292 | // Determine how many (if any!) vertex weights are included |
293 | if (n_vertex_weights) line_in >> n_vertex_weights; |
294 | |
295 | // Setup the iteration data structures |
296 | edge_weight = 1.0; |
297 | edge.first = 0; |
298 | edge.second = 0; |
299 | vertex_weights.reserve(n: n_vertex_weights * num_vertices()); |
300 | } |
301 | |
302 | metis_distribution::metis_distribution(std::istream& in, process_id_type my_id) |
303 | : in(in), my_id(my_id), |
304 | vertices(std::istream_iterator<process_id_type>(in), |
305 | std::istream_iterator<process_id_type>()) |
306 | { |
307 | } |
308 | |
309 | |
310 | metis_distribution::size_type |
311 | metis_distribution::block_size(process_id_type id, size_type) const |
312 | { |
313 | return std::count(first: vertices.begin(), last: vertices.end(), value: id); |
314 | } |
315 | |
316 | metis_distribution::size_type metis_distribution::local(size_type n) const |
317 | { |
318 | return std::count(first: vertices.begin(), last: vertices.begin() + n, value: vertices[n]); |
319 | } |
320 | |
321 | metis_distribution::size_type |
322 | metis_distribution::global(process_id_type id, size_type n) const |
323 | { |
324 | std::vector<process_id_type>::const_iterator i = vertices.begin(); |
325 | while (*i != id) ++i; |
326 | |
327 | while (n > 0) { |
328 | do { ++i; } while (*i != id); |
329 | --n; |
330 | } |
331 | |
332 | return i - vertices.begin(); |
333 | } |
334 | |
335 | #endif |
336 | |
337 | } } // end namespace boost::graph |
338 | |
339 | #endif // BOOST_GRAPH_METIS_HPP |
340 | |