boost/graph/dimacs.hpp

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