// 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: Douglas Gregor | |
// Andrew Lumsdaine | |
#ifndef BOOST_GRAPH_METIS_HPP | |
#define BOOST_GRAPH_METIS_HPP | |
#ifdef BOOST_GRAPH_METIS_NO_INLINE | |
# define BOOST_GRAPH_METIS_INLINE_KEYWORD | |
#else | |
# define BOOST_GRAPH_METIS_INLINE_KEYWORD inline | |
#endif | |
#include <string> | |
#include <iostream> | |
#include <iterator> | |
#include <utility> | |
#include <sstream> | |
#include <exception> | |
#include <vector> | |
#include <algorithm> | |
namespace boost { namespace graph { | |
class metis_exception : public std::exception {}; | |
class metis_input_exception : public metis_exception {}; | |
class metis_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; | |
class edge_iterator | |
{ | |
public: | |
typedef std::input_iterator_tag iterator_category; | |
typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
typedef const value_type& reference; | |
typedef const value_type* pointer; | |
typedef std::ptrdiff_t difference_type; | |
private: | |
class postincrement_proxy | |
{ | |
postincrement_proxy(const value_type& value) : value(value) { } | |
public: | |
reference operator*() const { return value; } | |
private: | |
value_type value; | |
friend class edge_iterator; | |
}; | |
public: | |
edge_iterator& operator++(); | |
postincrement_proxy operator++(int); | |
reference operator*() const { return self->edge; } | |
pointer operator->() const { return &self->edge; } | |
// Default copy constructor and assignment operator are okay | |
private: | |
edge_iterator(metis_reader* self); | |
void advance(bool skip_initial_read); | |
metis_reader* self; | |
friend class metis_reader; | |
friend bool operator==(edge_iterator, edge_iterator); | |
friend bool operator!=(edge_iterator, edge_iterator); | |
}; | |
friend class edge_iterator; | |
class edge_weight_iterator | |
{ | |
public: | |
typedef std::input_iterator_tag iterator_category; | |
typedef edge_weight_type value_type; | |
typedef const value_type& reference; | |
typedef const value_type* pointer; | |
// Default copy constructor and assignment operator are okay | |
reference operator*() const { return self->edge_weight; } | |
pointer operator->() const { return &self->edge_weight; } | |
edge_weight_iterator& operator++() { return *this; } | |
edge_weight_iterator operator++(int) { return *this; } | |
private: | |
edge_weight_iterator(metis_reader* self) : self(self) { } | |
metis_reader* self; | |
friend class metis_reader; | |
}; | |
metis_reader(std::istream& in) : in(in), edge_weight(1.0) { start(); } | |
edge_iterator begin(); | |
edge_iterator end(); | |
edge_weight_iterator weight_begin(); | |
vertices_size_type num_vertices() const { return n_vertices; } | |
edges_size_type num_edges() const { return n_edges; } | |
std::size_t num_vertex_weights() const { return n_vertex_weights; } | |
vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n) | |
{ return vertex_weights[v*num_vertex_weights() + n]; } | |
bool has_edge_weights() const { return edge_weights; } | |
private: | |
void start(); | |
// Configuration information | |
std::istream& in; | |
// Information about the current METIS file | |
vertices_size_type n_vertices; | |
edges_size_type n_edges; | |
std::size_t n_vertex_weights; | |
bool edge_weights; | |
// Information about the current edge/vertex | |
std::istringstream line_in; | |
std::pair<vertices_size_type, vertices_size_type> edge; | |
std::vector<vertex_weight_type> vertex_weights; | |
edge_weight_type edge_weight; | |
friend bool operator==(edge_iterator, edge_iterator); | |
friend bool operator!=(edge_iterator, edge_iterator); | |
}; | |
class metis_distribution | |
{ | |
public: | |
typedef int process_id_type; | |
typedef std::size_t size_type; | |
typedef std::vector<process_id_type>::iterator iterator; | |
metis_distribution(std::istream& in, process_id_type my_id); | |
size_type block_size(process_id_type id, size_type) const; | |
process_id_type operator()(size_type n) const { return vertices[n]; } | |
size_type local(size_type n) const; | |
size_type global(size_type n) const { return global(my_id, n); } | |
size_type global(process_id_type id, size_type n) const; | |
iterator begin() { return vertices.begin(); } | |
iterator end() { return vertices.end(); } | |
private: | |
std::istream& in; | |
process_id_type my_id; | |
std::vector<process_id_type> vertices; | |
}; | |
#if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE) | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
bool operator==(metis_reader::edge_iterator x, metis_reader::edge_iterator y) | |
{ | |
return (x.self == y.self | |
|| (x.self && x.self->edge.first == x.self->num_vertices()) | |
|| (y.self && y.self->edge.first == y.self->num_vertices())); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
bool operator!=(metis_reader::edge_iterator x, metis_reader::edge_iterator y) | |
{ | |
return !(x == y); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
metis_reader::edge_iterator::edge_iterator(metis_reader* self) | |
: self(self) | |
{ | |
if (self) advance(true); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
metis_reader::edge_iterator& metis_reader::edge_iterator::operator++() | |
{ | |
advance(false); | |
return *this; | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
void metis_reader::edge_iterator::advance(bool skip_initial_read) | |
{ | |
do { | |
if (!skip_initial_read) { | |
// Try to read the next edge | |
if (self->line_in >> std::ws >> self->edge.second) { | |
--self->edge.second; | |
if (self->has_edge_weights()) { | |
if (!(self->line_in >> self->edge_weight)) | |
boost::throw_exception(metis_input_exception()); | |
} | |
return; | |
} | |
// Check if we're done | |
++self->edge.first; | |
if (self->edge.first == self->num_vertices()) | |
return; | |
} | |
// Find the next line | |
std::string line; | |
while (getline(self->in, line) && !line.empty() && line[0] == '%') { | |
/* Keep reading lines in the loop header... */ | |
} | |
if (!self->in) boost::throw_exception(metis_input_exception()); | |
self->line_in.str(line); | |
self->line_in.clear(); | |
// Read the next line | |
std::size_t weights_left = self->n_vertex_weights; | |
vertex_weight_type weight; | |
while (weights_left > 0) { | |
if (self->line_in >> weight) self->vertex_weights.push_back(weight); | |
else boost::throw_exception(metis_input_exception()); | |
--weights_left; | |
} | |
// Successive iterations will pick up edges for this vertex. | |
skip_initial_read = false; | |
} while (true); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
metis_reader::edge_iterator::postincrement_proxy | |
metis_reader::edge_iterator::operator++(int) | |
{ | |
postincrement_proxy result(**this); | |
++(*this); | |
return result; | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
metis_reader::edge_iterator metis_reader::begin() | |
{ | |
if (edge.first != 0) start(); | |
return edge_iterator(this); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
metis_reader::edge_iterator metis_reader::end() | |
{ | |
return edge_iterator(0); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
metis_reader::edge_weight_iterator metis_reader::weight_begin() | |
{ | |
return edge_weight_iterator(this); | |
} | |
BOOST_GRAPH_METIS_INLINE_KEYWORD | |
void metis_reader::start() | |
{ | |
in.seekg(0, std::ios::beg); | |
std::string line; | |
while (getline(in, line) && !line.empty() && line[0] == '%') { | |
/* Keep getting lines in loop header. */ | |
} | |
if (!in || line.empty()) boost::throw_exception(metis_input_exception()); | |
// Determine number of vertices and edges in the graph | |
line_in.str(line); | |
if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(metis_input_exception()); | |
// Determine whether vertex or edge weights are included in the graph | |
int fmt = 0; | |
line_in >> fmt; | |
n_vertex_weights = fmt / 10; | |
edge_weights = (fmt % 10 == 1); | |
// Determine how many (if any!) vertex weights are included | |
if (n_vertex_weights) line_in >> n_vertex_weights; | |
// Setup the iteration data structures | |
edge_weight = 1.0; | |
edge.first = 0; | |
edge.second = 0; | |
vertex_weights.reserve(n_vertex_weights * num_vertices()); | |
} | |
metis_distribution::metis_distribution(std::istream& in, process_id_type my_id) | |
: in(in), my_id(my_id), | |
vertices(std::istream_iterator<process_id_type>(in), | |
std::istream_iterator<process_id_type>()) | |
{ | |
} | |
metis_distribution::size_type | |
metis_distribution::block_size(process_id_type id, size_type) const | |
{ | |
return std::count(vertices.begin(), vertices.end(), id); | |
} | |
metis_distribution::size_type metis_distribution::local(size_type n) const | |
{ | |
return std::count(vertices.begin(), vertices.begin() + n, vertices[n]); | |
} | |
metis_distribution::size_type | |
metis_distribution::global(process_id_type id, size_type n) const | |
{ | |
std::vector<process_id_type>::const_iterator i = vertices.begin(); | |
while (*i != id) ++i; | |
while (n > 0) { | |
do { ++i; } while (*i != id); | |
--n; | |
} | |
return i - vertices.begin(); | |
} | |
#endif | |
} } // end namespace boost::graph | |
#endif // BOOST_GRAPH_METIS_HPP |