Edit: /usr/include/boost/graph/dimacs.hpp (10448B)
// 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
#include
#include
#include
#include
#include
#include
#include
#include
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