Chris@16: // Copyright 2005 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Alex Breuer
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_DIMACS_HPP
Chris@16: #define BOOST_GRAPH_DIMACS_HPP
Chris@16: 
Chris@16: #include <string>
Chris@16: #include <sstream>
Chris@16: #include <iostream>
Chris@16: #include <fstream>
Chris@16: #include <iterator>
Chris@16: #include <exception>
Chris@16: #include <vector>
Chris@16: #include <queue>
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@16: namespace boost { namespace graph {
Chris@16: 
Chris@16: class dimacs_exception : public std::exception {};
Chris@16: 
Chris@16: class dimacs_basic_reader {
Chris@16: public:
Chris@16:   typedef std::size_t vertices_size_type;
Chris@16:   typedef std::size_t edges_size_type;
Chris@16:   typedef double vertex_weight_type;
Chris@16:   typedef double edge_weight_type;
Chris@16:   typedef std::pair<vertices_size_type,
Chris@16:                     vertices_size_type> edge_type;
Chris@16:   enum incr_mode {edge, edge_weight};
Chris@16: 
Chris@16:   dimacs_basic_reader( std::istream& in, bool want_weights = true ) : 
Chris@16:       inpt( in ), seen_edges( 0 ), want_weights(want_weights)
Chris@16:     {
Chris@16:     while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
Chris@16:     
Chris@16:     if( buf[0] != 'p' ) {
Chris@16:         boost::throw_exception(dimacs_exception());
Chris@16:     }
Chris@16:     
Chris@16:     std::stringstream instr( buf );
Chris@16:     std::string junk;
Chris@16: 
Chris@16:     instr >> junk >> junk >> num_vertices >> num_edges;
Chris@16:     read_edge_weights.push( -1 );
Chris@16:     incr( edge_weight );
Chris@16:   }
Chris@16: 
Chris@16:   //for a past the end iterator
Chris@16:   dimacs_basic_reader() : inpt( std::cin ), num_vertices( 0 ), 
Chris@16:                           num_edges( 0 ), seen_edges( 0 ), want_weights(false) {}
Chris@16: 
Chris@16:   edge_type edge_deref() {
Chris@16:     BOOST_ASSERT( !read_edges.empty() );
Chris@16:     return read_edges.front();
Chris@16:    }
Chris@16: 
Chris@16:   inline edge_type* edge_ref() {
Chris@16:     BOOST_ASSERT( !read_edges.empty() );
Chris@16:     return &read_edges.front();
Chris@16:   }
Chris@16: 
Chris@16:   inline edge_weight_type edge_weight_deref() {
Chris@16:     BOOST_ASSERT( !read_edge_weights.empty() );
Chris@16:     return read_edge_weights.front();
Chris@16:   }
Chris@16: 
Chris@16:   inline dimacs_basic_reader incr( incr_mode mode ) {
Chris@16:     if( mode == edge ) {
Chris@16:       BOOST_ASSERT( !read_edges.empty() );
Chris@16:       read_edges.pop();
Chris@16:     }
Chris@16:     else if( mode == edge_weight ) {
Chris@16:       BOOST_ASSERT( !read_edge_weights.empty() );
Chris@16:       read_edge_weights.pop();
Chris@16:     }
Chris@16: 
Chris@16:     if( (mode == edge && read_edges.empty()) ||
Chris@16:         (mode == edge_weight && read_edge_weights.empty() )) {
Chris@16: 
Chris@16:       if( seen_edges > num_edges ) {
Chris@16:           boost::throw_exception(dimacs_exception());
Chris@16:       }
Chris@16: 
Chris@16:       while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
Chris@16:       
Chris@16:       if( !inpt.eof() ) {
Chris@16:           int source, dest, weight;
Chris@16:           read_edge_line((char*) buf.c_str(), source, dest, weight);
Chris@16: 
Chris@16:           seen_edges++;
Chris@16:           source--;
Chris@16:           dest--;
Chris@16:         
Chris@16:           read_edges.push( edge_type( source, dest ) );
Chris@16:           if (want_weights) {
Chris@16:               read_edge_weights.push( weight );
Chris@16:           }
Chris@16:       }
Chris@16:       BOOST_ASSERT( read_edges.size() < 100 );
Chris@16:       BOOST_ASSERT( read_edge_weights.size() < 100 );
Chris@16:     }
Chris@16: 
Chris@16:     // the 1000000 just happens to be about how many edges can be read in 
Chris@16:     // 10s
Chris@16: //     if( !(seen_edges % 1000000) && !process_id( pg ) && mode == edge ) {
Chris@16: //       std::cout << "read " << seen_edges << " edges" << std::endl;
Chris@16: //     }
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   inline bool done_edges() {
Chris@16:     return inpt.eof() && read_edges.size() == 0;
Chris@16:   }
Chris@16: 
Chris@16:   inline bool done_edge_weights() {
Chris@16:     return inpt.eof() && read_edge_weights.size() == 0;
Chris@16:   }
Chris@16: 
Chris@16:   inline vertices_size_type n_vertices() {
Chris@16:     return num_vertices;
Chris@16:   }
Chris@16:   
Chris@16:   inline vertices_size_type processed_edges() {
Chris@16:     return seen_edges - read_edges.size();
Chris@16:   }
Chris@16: 
Chris@16:   inline vertices_size_type processed_edge_weights() {
Chris@16:     return seen_edges - read_edge_weights.size();
Chris@16:   }
Chris@16: 
Chris@16:   inline vertices_size_type n_edges() {
Chris@16:     return num_edges;
Chris@16:   }
Chris@16: 
Chris@16: protected:
Chris@16:     bool read_edge_line(char *linebuf, int &from, int &to, int &weight)
Chris@16:     {
Chris@16:         char *fs = NULL, *ts = NULL, *ws = NULL;
Chris@16:         char *tmp = linebuf + 2;
Chris@16: 
Chris@16:         fs = tmp;
Chris@16:         if ('e' == linebuf[0]) {
Chris@16:             while (*tmp != '\n' && *tmp != '\0') {
Chris@16:                 if (*tmp == ' ') { 
Chris@16:                     *tmp = '\0';
Chris@16:                     ts = ++tmp;
Chris@16:                     break;
Chris@16:                 }
Chris@16:                 tmp++;
Chris@16:             }
Chris@16:             *tmp = '\0';
Chris@16:             if (NULL == fs || NULL == ts) return false;
Chris@16:             from = atoi(fs); to = atoi(ts); weight = 0;
Chris@16: 
Chris@16:         } else if ('a' == linebuf[0]) {
Chris@16:             while (*tmp != '\n' && *tmp != '\0') {
Chris@16:                 if (*tmp == ' ') { 
Chris@16:                     *tmp = '\0';
Chris@16:                     ts = ++tmp;
Chris@16:                     break;
Chris@16:                 }
Chris@16:                 tmp++;
Chris@16:             } 
Chris@16:             while (*tmp != '\n' && *tmp != '\0') {
Chris@16:                 if (*tmp == ' ') { 
Chris@16:                     *tmp = '\0';
Chris@16:                     ws = ++tmp;
Chris@16:                     break;
Chris@16:                 }
Chris@16:                 tmp++;
Chris@16:             }
Chris@16:             while (*tmp != '\n' && *tmp != '\0') tmp++;
Chris@16:             *tmp = '\0';
Chris@16:             if (fs == NULL || ts == NULL || ws == NULL) return false;
Chris@16:             from = atoi(fs); to = atoi(ts) ; 
Chris@16:             if (want_weights) weight = atoi(ws); else weight = 0;
Chris@16: 
Chris@16:         } else {
Chris@16:             return false;
Chris@16:         }
Chris@16: 
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:   std::queue<edge_type> read_edges;
Chris@16:   std::queue<edge_weight_type> read_edge_weights;
Chris@16: 
Chris@16:   std::istream& inpt;
Chris@16:   std::string buf;
Chris@16:   vertices_size_type num_vertices, num_edges, seen_edges;
Chris@16:   bool want_weights;
Chris@16: };
Chris@16: 
Chris@16: template<typename T>
Chris@16: class dimacs_edge_iterator {
Chris@16: public:
Chris@16:   typedef dimacs_basic_reader::edge_type edge_type;
Chris@16:   typedef dimacs_basic_reader::incr_mode incr_mode;
Chris@16: 
Chris@16:   typedef std::input_iterator_tag iterator_category;
Chris@16:   typedef edge_type               value_type;
Chris@16:   typedef value_type              reference;
Chris@16:   typedef edge_type*              pointer;
Chris@16:   typedef std::ptrdiff_t          difference_type;
Chris@16: 
Chris@16:   dimacs_edge_iterator( T& reader ) :
Chris@16:     reader( reader ) {}
Chris@16: 
Chris@16:   inline dimacs_edge_iterator& operator++() {
Chris@16:     reader.incr( dimacs_basic_reader::edge );
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   inline edge_type operator*() {
Chris@16:     return reader.edge_deref();
Chris@16:   }
Chris@16: 
Chris@16:   inline edge_type* operator->() {
Chris@16:     return reader.edge_ref();
Chris@16:   }
Chris@16: 
Chris@16:   // don't expect this to do the right thing if you're not comparing against a
Chris@16:   // general past-the-end-iterator made with the default constructor for 
Chris@16:   // dimacs_basic_reader
Chris@16:   inline bool operator==( dimacs_edge_iterator arg ) {
Chris@16:     if( reader.n_vertices() == 0 ) {
Chris@16:       return arg.reader.done_edges();
Chris@16:     }
Chris@16:     else if( arg.reader.n_vertices() == 0 ) {
Chris@16:       return reader.done_edges();
Chris@16:     }
Chris@16:     else {
Chris@16:       return false;
Chris@16:     }
Chris@16:     return false;
Chris@16:   }
Chris@16: 
Chris@16:   inline bool operator!=( dimacs_edge_iterator arg ) {
Chris@16:     if( reader.n_vertices() == 0 ) {
Chris@16:       return !arg.reader.done_edges();
Chris@16:     }
Chris@16:     else if( arg.reader.n_vertices() == 0 ) {
Chris@16:       return !reader.done_edges();
Chris@16:     }
Chris@16:     else {
Chris@16:       return true;
Chris@16:     }
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   T& reader;
Chris@16: };
Chris@16: 
Chris@16: template<typename T>
Chris@16: class dimacs_edge_weight_iterator {
Chris@16: public:
Chris@16:   typedef dimacs_basic_reader::edge_weight_type edge_weight_type;
Chris@16:   typedef dimacs_basic_reader::incr_mode incr_mode;
Chris@16: 
Chris@16:   dimacs_edge_weight_iterator( T& reader ) : reader( reader ) {}
Chris@16: 
Chris@16:   inline dimacs_edge_weight_iterator& operator++() {
Chris@16:     reader.incr( dimacs_basic_reader::edge_weight );
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   inline edge_weight_type operator*() {
Chris@16:     return reader.edge_weight_deref();
Chris@16:   }
Chris@16: 
Chris@16:   // don't expect this to do the right thing if you're not comparing against a
Chris@16:   // general past-the-end-iterator made with the default constructor for 
Chris@16:   // dimacs_basic_reader
Chris@16:   inline bool operator==( dimacs_edge_weight_iterator arg ) {
Chris@16:     if( reader.n_vertices() == 0 ) {
Chris@16:       return arg.reader.done_edge_weights();
Chris@16:     }
Chris@16:     else if( arg.reader.n_vertices() == 0 ) {
Chris@16:       return reader.done_edge_weights();
Chris@16:     }
Chris@16:     else {
Chris@16:       return false;
Chris@16:     }
Chris@16:     return false;
Chris@16:   }
Chris@16: 
Chris@16:   inline bool operator!=( dimacs_edge_weight_iterator arg ) {
Chris@16:     if( reader.n_vertices() == 0 ) {
Chris@16:       return !arg.reader.done_edge_weights();
Chris@16:     }
Chris@16:     else if( arg.reader.n_vertices() == 0 ) {
Chris@16:       return !reader.done_edge_weights();
Chris@16:     }
Chris@16:     else {
Chris@16:       return true;
Chris@16:     }
Chris@16:     return true;
Chris@16:   }
Chris@16: private:
Chris@16:   T& reader;
Chris@16: };
Chris@16: 
Chris@16: } } // end namespace boost::graph
Chris@16: #endif