boost/graph/dimacs.hpp

// 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