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 23 { 24 namespace graph 25 { 26 27 class BOOST_SYMBOL_VISIBLE dimacs_exception : public std::exception 28 { 29 }; 30 31 class dimacs_basic_reader 32 { 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 dimacs_basic_reader(std::istream & in,bool want_weights=true)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 dimacs_basic_reader()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 edge_deref()74 edge_type edge_deref() 75 { 76 BOOST_ASSERT(!read_edges.empty()); 77 return read_edges.front(); 78 } 79 edge_ref()80 inline edge_type* edge_ref() 81 { 82 BOOST_ASSERT(!read_edges.empty()); 83 return &read_edges.front(); 84 } 85 edge_weight_deref()86 inline edge_weight_type edge_weight_deref() 87 { 88 BOOST_ASSERT(!read_edge_weights.empty()); 89 return read_edge_weights.front(); 90 } 91 incr(incr_mode mode)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 done_edges()146 inline bool done_edges() 147 { 148 return inpt.eof() && read_edges.size() == 0; 149 } 150 done_edge_weights()151 inline bool done_edge_weights() 152 { 153 return inpt.eof() && read_edge_weights.size() == 0; 154 } 155 n_vertices()156 inline vertices_size_type n_vertices() { return num_vertices; } 157 processed_edges()158 inline vertices_size_type processed_edges() 159 { 160 return seen_edges - read_edges.size(); 161 } 162 processed_edge_weights()163 inline vertices_size_type processed_edge_weights() 164 { 165 return seen_edges - read_edge_weights.size(); 166 } 167 n_edges()168 inline vertices_size_type n_edges() { return num_edges; } 169 170 protected: read_edge_line(char * linebuf,int & from,int & to,int & weight)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++; 188 } 189 *tmp = '\0'; 190 if (NULL == fs || NULL == ts) 191 return false; 192 from = atoi(fs); 193 to = atoi(ts); 194 weight = 0; 195 } 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++; 207 } 208 while (*tmp != '\n' && *tmp != '\0') 209 { 210 if (*tmp == ' ') 211 { 212 *tmp = '\0'; 213 ws = ++tmp; 214 break; 215 } 216 tmp++; 217 } 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; 229 } 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 dimacs_edge_iterator(T & reader)259 dimacs_edge_iterator(T& reader) : reader(reader) {} 260 operator ++()261 inline dimacs_edge_iterator& operator++() 262 { 263 reader.incr(dimacs_basic_reader::edge); 264 return *this; 265 } 266 operator *()267 inline edge_type operator*() { return reader.edge_deref(); } 268 operator ->()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 operator ==(dimacs_edge_iterator arg)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 operator !=(dimacs_edge_iterator arg)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 dimacs_edge_weight_iterator(T & reader)318 dimacs_edge_weight_iterator(T& reader) : reader(reader) {} 319 operator ++()320 inline dimacs_edge_weight_iterator& operator++() 321 { 322 reader.incr(dimacs_basic_reader::edge_weight); 323 return *this; 324 } 325 operator *()326 inline edge_weight_type operator*() 327 { 328 return reader.edge_weight_deref(); 329 } 330 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 operator ==(dimacs_edge_weight_iterator arg)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 } 348 return false; 349 } 350 operator !=(dimacs_edge_weight_iterator arg)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 374 #endif 375