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