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