]>
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: Alex Breuer | |
8 | // Andrew Lumsdaine | |
9 | #ifndef BOOST_GRAPH_DIMACS_HPP | |
10 | #define BOOST_GRAPH_DIMACS_HPP | |
11 | ||
12 | #include <string> | |
13 | #include <sstream> | |
14 | #include <iostream> | |
15 | #include <fstream> | |
16 | #include <iterator> | |
17 | #include <exception> | |
18 | #include <vector> | |
19 | #include <queue> | |
20 | #include <boost/assert.hpp> | |
21 | ||
f67539c2 TL |
22 | namespace boost |
23 | { | |
24 | namespace graph | |
25 | { | |
26 | ||
27 | class BOOST_SYMBOL_VISIBLE dimacs_exception : public std::exception | |
7c673cae | 28 | { |
f67539c2 TL |
29 | }; |
30 | ||
31 | class dimacs_basic_reader | |
7c673cae | 32 | { |
f67539c2 TL |
33 | public: |
34 | typedef std::size_t vertices_size_type; | |
35 | typedef std::size_t edges_size_type; | |
36 | typedef double vertex_weight_type; | |
37 | typedef double edge_weight_type; | |
38 | typedef std::pair< vertices_size_type, vertices_size_type > edge_type; | |
39 | enum incr_mode | |
40 | { | |
41 | edge, | |
42 | edge_weight | |
43 | }; | |
44 | ||
45 | dimacs_basic_reader(std::istream& in, bool want_weights = true) | |
46 | : inpt(in), seen_edges(0), want_weights(want_weights) | |
47 | { | |
48 | while (getline(inpt, buf) && !buf.empty() && buf[0] == 'c') | |
49 | ; | |
50 | ||
51 | if (buf[0] != 'p') | |
52 | { | |
53 | boost::throw_exception(dimacs_exception()); | |
54 | } | |
55 | ||
56 | std::stringstream instr(buf); | |
57 | std::string junk; | |
58 | ||
59 | instr >> junk >> junk >> num_vertices >> num_edges; | |
60 | read_edge_weights.push(-1); | |
61 | incr(edge_weight); | |
62 | } | |
63 | ||
64 | // for a past the end iterator | |
65 | dimacs_basic_reader() | |
66 | : inpt(std::cin) | |
67 | , num_vertices(0) | |
68 | , num_edges(0) | |
69 | , seen_edges(0) | |
70 | , want_weights(false) | |
71 | { | |
72 | } | |
73 | ||
74 | edge_type edge_deref() | |
75 | { | |
76 | BOOST_ASSERT(!read_edges.empty()); | |
77 | return read_edges.front(); | |
78 | } | |
79 | ||
80 | inline edge_type* edge_ref() | |
81 | { | |
82 | BOOST_ASSERT(!read_edges.empty()); | |
83 | return &read_edges.front(); | |
84 | } | |
85 | ||
86 | inline edge_weight_type edge_weight_deref() | |
87 | { | |
88 | BOOST_ASSERT(!read_edge_weights.empty()); | |
89 | return read_edge_weights.front(); | |
90 | } | |
91 | ||
92 | inline dimacs_basic_reader incr(incr_mode mode) | |
93 | { | |
94 | if (mode == edge) | |
95 | { | |
96 | BOOST_ASSERT(!read_edges.empty()); | |
97 | read_edges.pop(); | |
98 | } | |
99 | else if (mode == edge_weight) | |
100 | { | |
101 | BOOST_ASSERT(!read_edge_weights.empty()); | |
102 | read_edge_weights.pop(); | |
103 | } | |
104 | ||
105 | if ((mode == edge && read_edges.empty()) | |
106 | || (mode == edge_weight && read_edge_weights.empty())) | |
107 | { | |
108 | ||
109 | if (seen_edges > num_edges) | |
110 | { | |
111 | boost::throw_exception(dimacs_exception()); | |
112 | } | |
113 | ||
114 | while (getline(inpt, buf) && !buf.empty() && buf[0] == 'c') | |
115 | ; | |
116 | ||
117 | if (!inpt.eof()) | |
118 | { | |
119 | int source, dest, weight; | |
120 | read_edge_line((char*)buf.c_str(), source, dest, weight); | |
121 | ||
122 | seen_edges++; | |
123 | source--; | |
124 | dest--; | |
125 | ||
126 | read_edges.push(edge_type(source, dest)); | |
127 | if (want_weights) | |
128 | { | |
129 | read_edge_weights.push(weight); | |
130 | } | |
131 | } | |
132 | BOOST_ASSERT(read_edges.size() < 100); | |
133 | BOOST_ASSERT(read_edge_weights.size() < 100); | |
134 | } | |
135 | ||
136 | // the 1000000 just happens to be about how many edges can be read | |
137 | // in 10s | |
138 | // if( !(seen_edges % 1000000) && !process_id( pg ) && mode == | |
139 | // edge ) { | |
140 | // std::cout << "read " << seen_edges << " edges" << | |
141 | // std::endl; | |
142 | // } | |
143 | return *this; | |
144 | } | |
145 | ||
146 | inline bool done_edges() | |
147 | { | |
148 | return inpt.eof() && read_edges.size() == 0; | |
149 | } | |
150 | ||
151 | inline bool done_edge_weights() | |
152 | { | |
153 | return inpt.eof() && read_edge_weights.size() == 0; | |
154 | } | |
155 | ||
156 | inline vertices_size_type n_vertices() { return num_vertices; } | |
157 | ||
158 | inline vertices_size_type processed_edges() | |
159 | { | |
160 | return seen_edges - read_edges.size(); | |
161 | } | |
162 | ||
163 | inline vertices_size_type processed_edge_weights() | |
164 | { | |
165 | return seen_edges - read_edge_weights.size(); | |
166 | } | |
167 | ||
168 | inline vertices_size_type n_edges() { return num_edges; } | |
169 | ||
170 | protected: | |
171 | bool read_edge_line(char* linebuf, int& from, int& to, int& weight) | |
172 | { | |
173 | char *fs = NULL, *ts = NULL, *ws = NULL; | |
174 | char* tmp = linebuf + 2; | |
175 | ||
176 | fs = tmp; | |
177 | if ('e' == linebuf[0]) | |
178 | { | |
179 | while (*tmp != '\n' && *tmp != '\0') | |
180 | { | |
181 | if (*tmp == ' ') | |
182 | { | |
183 | *tmp = '\0'; | |
184 | ts = ++tmp; | |
185 | break; | |
186 | } | |
187 | tmp++; | |
7c673cae | 188 | } |
f67539c2 TL |
189 | *tmp = '\0'; |
190 | if (NULL == fs || NULL == ts) | |
191 | return false; | |
192 | from = atoi(fs); | |
193 | to = atoi(ts); | |
194 | weight = 0; | |
7c673cae | 195 | } |
f67539c2 TL |
196 | else if ('a' == linebuf[0]) |
197 | { | |
198 | while (*tmp != '\n' && *tmp != '\0') | |
199 | { | |
200 | if (*tmp == ' ') | |
201 | { | |
202 | *tmp = '\0'; | |
203 | ts = ++tmp; | |
204 | break; | |
205 | } | |
206 | tmp++; | |
7c673cae | 207 | } |
f67539c2 TL |
208 | while (*tmp != '\n' && *tmp != '\0') |
209 | { | |
210 | if (*tmp == ' ') | |
211 | { | |
212 | *tmp = '\0'; | |
213 | ws = ++tmp; | |
214 | break; | |
215 | } | |
216 | tmp++; | |
7c673cae | 217 | } |
f67539c2 TL |
218 | while (*tmp != '\n' && *tmp != '\0') |
219 | tmp++; | |
220 | *tmp = '\0'; | |
221 | if (fs == NULL || ts == NULL || ws == NULL) | |
222 | return false; | |
223 | from = atoi(fs); | |
224 | to = atoi(ts); | |
225 | if (want_weights) | |
226 | weight = atoi(ws); | |
227 | else | |
228 | weight = 0; | |
7c673cae | 229 | } |
f67539c2 TL |
230 | else |
231 | { | |
232 | return false; | |
233 | } | |
234 | ||
235 | return true; | |
236 | } | |
237 | ||
238 | std::queue< edge_type > read_edges; | |
239 | std::queue< edge_weight_type > read_edge_weights; | |
240 | ||
241 | std::istream& inpt; | |
242 | std::string buf; | |
243 | vertices_size_type num_vertices, num_edges, seen_edges; | |
244 | bool want_weights; | |
245 | }; | |
246 | ||
247 | template < typename T > class dimacs_edge_iterator | |
248 | { | |
249 | public: | |
250 | typedef dimacs_basic_reader::edge_type edge_type; | |
251 | typedef dimacs_basic_reader::incr_mode incr_mode; | |
252 | ||
253 | typedef std::input_iterator_tag iterator_category; | |
254 | typedef edge_type value_type; | |
255 | typedef value_type reference; | |
256 | typedef edge_type* pointer; | |
257 | typedef std::ptrdiff_t difference_type; | |
258 | ||
259 | dimacs_edge_iterator(T& reader) : reader(reader) {} | |
260 | ||
261 | inline dimacs_edge_iterator& operator++() | |
262 | { | |
263 | reader.incr(dimacs_basic_reader::edge); | |
264 | return *this; | |
265 | } | |
266 | ||
267 | inline edge_type operator*() { return reader.edge_deref(); } | |
268 | ||
269 | inline edge_type* operator->() { return reader.edge_ref(); } | |
270 | ||
271 | // don't expect this to do the right thing if you're not comparing | |
272 | // against a general past-the-end-iterator made with the default | |
273 | // constructor for dimacs_basic_reader | |
274 | inline bool operator==(dimacs_edge_iterator arg) | |
275 | { | |
276 | if (reader.n_vertices() == 0) | |
277 | { | |
278 | return arg.reader.done_edges(); | |
279 | } | |
280 | else if (arg.reader.n_vertices() == 0) | |
281 | { | |
282 | return reader.done_edges(); | |
283 | } | |
284 | else | |
285 | { | |
286 | return false; | |
287 | } | |
288 | return false; | |
289 | } | |
290 | ||
291 | inline bool operator!=(dimacs_edge_iterator arg) | |
292 | { | |
293 | if (reader.n_vertices() == 0) | |
294 | { | |
295 | return !arg.reader.done_edges(); | |
296 | } | |
297 | else if (arg.reader.n_vertices() == 0) | |
298 | { | |
299 | return !reader.done_edges(); | |
300 | } | |
301 | else | |
302 | { | |
303 | return true; | |
304 | } | |
305 | return true; | |
306 | } | |
307 | ||
308 | private: | |
309 | T& reader; | |
310 | }; | |
311 | ||
312 | template < typename T > class dimacs_edge_weight_iterator | |
313 | { | |
314 | public: | |
315 | typedef dimacs_basic_reader::edge_weight_type edge_weight_type; | |
316 | typedef dimacs_basic_reader::incr_mode incr_mode; | |
317 | ||
318 | dimacs_edge_weight_iterator(T& reader) : reader(reader) {} | |
319 | ||
320 | inline dimacs_edge_weight_iterator& operator++() | |
321 | { | |
322 | reader.incr(dimacs_basic_reader::edge_weight); | |
323 | return *this; | |
324 | } | |
325 | ||
326 | inline edge_weight_type operator*() | |
327 | { | |
328 | return reader.edge_weight_deref(); | |
329 | } | |
7c673cae | 330 | |
f67539c2 TL |
331 | // don't expect this to do the right thing if you're not comparing |
332 | // against a general past-the-end-iterator made with the default | |
333 | // constructor for dimacs_basic_reader | |
334 | inline bool operator==(dimacs_edge_weight_iterator arg) | |
335 | { | |
336 | if (reader.n_vertices() == 0) | |
337 | { | |
338 | return arg.reader.done_edge_weights(); | |
339 | } | |
340 | else if (arg.reader.n_vertices() == 0) | |
341 | { | |
342 | return reader.done_edge_weights(); | |
343 | } | |
344 | else | |
345 | { | |
346 | return false; | |
347 | } | |
7c673cae FG |
348 | return false; |
349 | } | |
350 | ||
f67539c2 TL |
351 | inline bool operator!=(dimacs_edge_weight_iterator arg) |
352 | { | |
353 | if (reader.n_vertices() == 0) | |
354 | { | |
355 | return !arg.reader.done_edge_weights(); | |
356 | } | |
357 | else if (arg.reader.n_vertices() == 0) | |
358 | { | |
359 | return !reader.done_edge_weights(); | |
360 | } | |
361 | else | |
362 | { | |
363 | return true; | |
364 | } | |
365 | return true; | |
366 | } | |
367 | ||
368 | private: | |
369 | T& reader; | |
370 | }; | |
371 | ||
372 | } | |
373 | } // end namespace boost::graph | |
7c673cae | 374 | #endif |