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