#include <queue>
#include <boost/assert.hpp>
-namespace boost { namespace graph {
-
-class BOOST_SYMBOL_VISIBLE 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)
+namespace boost
+{
+namespace graph
+{
+
+ class BOOST_SYMBOL_VISIBLE dimacs_exception : public std::exception
{
- 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() {
- BOOST_ASSERT( !read_edges.empty() );
- return read_edges.front();
- }
-
- inline edge_type* edge_ref() {
- BOOST_ASSERT( !read_edges.empty() );
- return &read_edges.front();
- }
-
- inline edge_weight_type edge_weight_deref() {
- BOOST_ASSERT( !read_edge_weights.empty() );
- return read_edge_weights.front();
- }
-
- inline dimacs_basic_reader incr( incr_mode mode ) {
- if( mode == edge ) {
- BOOST_ASSERT( !read_edges.empty() );
- read_edges.pop();
- }
- else if( mode == edge_weight ) {
- BOOST_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 );
- }
- }
- BOOST_ASSERT( read_edges.size() < 100 );
- BOOST_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)
+ };
+
+ class dimacs_basic_reader
{
- 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;
+ 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()
+ {
+ BOOST_ASSERT(!read_edges.empty());
+ return read_edges.front();
+ }
+
+ inline edge_type* edge_ref()
+ {
+ BOOST_ASSERT(!read_edges.empty());
+ return &read_edges.front();
+ }
+
+ inline edge_weight_type edge_weight_deref()
+ {
+ BOOST_ASSERT(!read_edge_weights.empty());
+ return read_edge_weights.front();
+ }
+
+ inline dimacs_basic_reader incr(incr_mode mode)
+ {
+ if (mode == edge)
+ {
+ BOOST_ASSERT(!read_edges.empty());
+ read_edges.pop();
+ }
+ else if (mode == edge_weight)
+ {
+ BOOST_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);
+ }
+ }
+ BOOST_ASSERT(read_edges.size() < 100);
+ BOOST_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++;
+ *tmp = '\0';
+ if (NULL == fs || NULL == ts)
+ return false;
+ from = atoi(fs);
+ to = atoi(ts);
+ weight = 0;
}
- *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;
+ else if ('a' == linebuf[0])
+ {
+ while (*tmp != '\n' && *tmp != '\0')
+ {
+ if (*tmp == ' ')
+ {
+ *tmp = '\0';
+ ts = ++tmp;
+ break;
+ }
+ tmp++;
}
- tmp++;
- }
- while (*tmp != '\n' && *tmp != '\0') {
- if (*tmp == ' ') {
- *tmp = '\0';
- ws = ++tmp;
- break;
+ while (*tmp != '\n' && *tmp != '\0')
+ {
+ if (*tmp == ' ')
+ {
+ *tmp = '\0';
+ ws = ++tmp;
+ break;
+ }
+ tmp++;
}
- 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;
}
- 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();
+ }
- } else {
+ // 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;
}
- 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
+ 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
projects / ceph.git / blobdiff