EIC code displayed by LXR master/​include/​boost/​graph/​dimacs.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:37:26

 // 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>
 #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)
         {
             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 = '\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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team