boost/graph/metis.hpp

   1 // Copyright 2005 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_GRAPH_METIS_HPP
  10 #define BOOST_GRAPH_METIS_HPP
  11
  12 #ifdef BOOST_GRAPH_METIS_NO_INLINE
  13 #  define BOOST_GRAPH_METIS_INLINE_KEYWORD
  14 #else
  15 #  define BOOST_GRAPH_METIS_INLINE_KEYWORD inline
  16 #endif
  17
  18 #include <string>
  19 #include <iostream>
  20 #include <iterator>
  21 #include <utility>
  22 #include <sstream>
  23 #include <exception>
  24 #include <vector>
  25 #include <algorithm>
  26
  27 namespace boost { namespace graph {
  28
  29 class metis_exception : public std::exception {};
  30 class metis_input_exception : public metis_exception {};
  31
  32 class metis_reader
  33 {
  34  public:
  35   typedef std::size_t vertices_size_type;
  36   typedef std::size_t edges_size_type;
  37   typedef double vertex_weight_type;
  38   typedef double edge_weight_type;
  39
  40   class edge_iterator
  41   {
  42   public:
  43     typedef std::input_iterator_tag iterator_category;
  44     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
  45     typedef const value_type& reference;
  46     typedef const value_type* pointer;
  47     typedef std::ptrdiff_t difference_type;
  48
  49   private:
  50     class postincrement_proxy
  51     {
  52       postincrement_proxy(const value_type& value) : value(value) { }
  53
  54     public:
  55       reference operator*() const { return value; }
  56
  57     private:
  58       value_type value;
  59       friend class edge_iterator;
  60     };
  61
  62   public:
  63     edge_iterator& operator++();
  64     postincrement_proxy operator++(int);
  65
  66     reference operator*() const { return self->edge; }
  67     pointer operator->() const { return &self->edge; }
  68
  69     // Default copy constructor and assignment operator are okay
  70
  71   private:
  72     edge_iterator(metis_reader* self);
  73     void advance(bool skip_initial_read);
  74
  75     metis_reader* self;
  76
  77     friend class metis_reader;
  78     friend bool operator==(edge_iterator, edge_iterator);
  79     friend bool operator!=(edge_iterator, edge_iterator);
  80   };
  81   friend class edge_iterator;
  82
  83   class edge_weight_iterator
  84   {
  85   public:
  86     typedef std::input_iterator_tag iterator_category;
  87     typedef edge_weight_type value_type;
  88     typedef const value_type& reference;
  89     typedef const value_type* pointer;
  90
  91     // Default copy constructor and assignment operator are okay
  92
  93     reference operator*() const { return self->edge_weight; }
  94     pointer operator->() const { return &self->edge_weight; }
  95
  96     edge_weight_iterator& operator++() { return *this; }
  97     edge_weight_iterator operator++(int) { return *this; }
  98
  99   private:
 100     edge_weight_iterator(metis_reader* self) : self(self) { }
 101
 102     metis_reader* self;
 103
 104     friend class metis_reader;
 105   };
 106
 107   metis_reader(std::istream& in) : in(in), edge_weight(1.0) { start(); }
 108
 109   edge_iterator begin();
 110   edge_iterator end();
 111   edge_weight_iterator weight_begin();
 112
 113   vertices_size_type num_vertices() const { return n_vertices; }
 114   edges_size_type num_edges() const { return n_edges; }
 115
 116   std::size_t num_vertex_weights() const { return n_vertex_weights; }
 117
 118   vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n)
 119   { return vertex_weights[v*num_vertex_weights() + n]; }
 120
 121   bool has_edge_weights() const { return edge_weights; }
 122
 123  private:
 124   void start();
 125
 126   // Configuration information
 127   std::istream& in;
 128
 129   // Information about the current METIS file
 130   vertices_size_type n_vertices;
 131   edges_size_type n_edges;
 132   std::size_t n_vertex_weights;
 133   bool edge_weights;
 134
 135   // Information about the current edge/vertex
 136   std::istringstream line_in;
 137   std::pair<vertices_size_type, vertices_size_type> edge;
 138   std::vector<vertex_weight_type> vertex_weights;
 139   edge_weight_type edge_weight;
 140
 141   friend bool operator==(edge_iterator, edge_iterator);
 142   friend bool operator!=(edge_iterator, edge_iterator);
 143 };
 144
 145 class metis_distribution
 146 {
 147  public:
 148   typedef int process_id_type;
 149   typedef std::size_t size_type;
 150   typedef std::vector<process_id_type>::iterator iterator;
 151
 152   metis_distribution(std::istream& in, process_id_type my_id);
 153
 154   size_type block_size(process_id_type id, size_type) const;
 155   process_id_type operator()(size_type n) const { return vertices[n]; }
 156   size_type local(size_type n) const;
 157   size_type global(size_type n) const { return global(my_id, n); }
 158   size_type global(process_id_type id, size_type n) const;
 159
 160   iterator begin() { return vertices.begin(); }
 161   iterator end()   { return vertices.end(); }
 162
 163  private:
 164   std::istream& in;
 165   process_id_type my_id;
 166   std::vector<process_id_type> vertices;
 167 };
 168
 169 #if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE)
 170 BOOST_GRAPH_METIS_INLINE_KEYWORD
 171 bool operator==(metis_reader::edge_iterator x, metis_reader::edge_iterator y)
 172 {
 173   return (x.self == y.self
 174           || (x.self && x.self->edge.first == x.self->num_vertices())
 175           || (y.self && y.self->edge.first == y.self->num_vertices()));
 176 }
 177
 178 BOOST_GRAPH_METIS_INLINE_KEYWORD
 179 bool operator!=(metis_reader::edge_iterator x, metis_reader::edge_iterator y)
 180 {
 181   return !(x == y);
 182 }
 183
 184 BOOST_GRAPH_METIS_INLINE_KEYWORD
 185 metis_reader::edge_iterator::edge_iterator(metis_reader* self)
 186   : self(self)
 187 {
 188   if (self) advance(true);
 189 }
 190
 191 BOOST_GRAPH_METIS_INLINE_KEYWORD
 192 metis_reader::edge_iterator& metis_reader::edge_iterator::operator++()
 193 {
 194   advance(false);
 195   return *this;
 196 }
 197
 198 BOOST_GRAPH_METIS_INLINE_KEYWORD
 199 void metis_reader::edge_iterator::advance(bool skip_initial_read)
 200 {
 201   do {
 202
 203     if (!skip_initial_read) {
 204       // Try to read the next edge
 205       if (self->line_in >> std::ws >> self->edge.second) {
 206         --self->edge.second;
 207         if (self->has_edge_weights()) {
 208           if (!(self->line_in >> self->edge_weight))
 209             boost::throw_exception(metis_input_exception());
 210         }
 211         return;
 212       }
 213
 214       // Check if we're done
 215       ++self->edge.first;
 216       if (self->edge.first == self->num_vertices())
 217         return;
 218     }
 219
 220     // Find the next line
 221     std::string line;
 222     while (getline(self->in, line) && !line.empty() && line[0] == '%') {
 223       /* Keep reading lines in the loop header... */
 224     }
 225     if (!self->in) boost::throw_exception(metis_input_exception());
 226     self->line_in.str(line);
 227     self->line_in.clear();
 228
 229     // Read the next line
 230     std::size_t weights_left = self->n_vertex_weights;
 231     vertex_weight_type weight;
 232     while (weights_left > 0) {
 233       if (self->line_in >> weight) self->vertex_weights.push_back(weight);
 234       else boost::throw_exception(metis_input_exception());
 235       --weights_left;
 236     }
 237
 238     // Successive iterations will pick up edges for this vertex.
 239     skip_initial_read = false;
 240   } while (true);
 241 }
 242
 243 BOOST_GRAPH_METIS_INLINE_KEYWORD
 244 metis_reader::edge_iterator::postincrement_proxy
 245 metis_reader::edge_iterator::operator++(int)
 246 {
 247   postincrement_proxy result(**this);
 248   ++(*this);
 249   return result;
 250 }
 251
 252 BOOST_GRAPH_METIS_INLINE_KEYWORD
 253 metis_reader::edge_iterator metis_reader::begin()
 254 {
 255   if (edge.first != 0) start();
 256   return edge_iterator(this);
 257 }
 258
 259 BOOST_GRAPH_METIS_INLINE_KEYWORD
 260 metis_reader::edge_iterator metis_reader::end()
 261 {
 262   return edge_iterator(0);
 263 }
 264
 265 BOOST_GRAPH_METIS_INLINE_KEYWORD
 266 metis_reader::edge_weight_iterator metis_reader::weight_begin()
 267 {
 268   return edge_weight_iterator(this);
 269 }
 270
 271 BOOST_GRAPH_METIS_INLINE_KEYWORD
 272 void metis_reader::start()
 273 {
 274   in.seekg(0, std::ios::beg);
 275   std::string line;
 276   while (getline(in, line) && !line.empty() && line[0] == '%') {
 277     /* Keep getting lines in loop header. */
 278   }
 279
 280   if (!in || line.empty()) boost::throw_exception(metis_input_exception());
 281
 282   // Determine number of vertices and edges in the graph
 283   line_in.str(line);
 284   if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(metis_input_exception());
 285
 286   // Determine whether vertex or edge weights are included in the graph
 287   int fmt = 0;
 288   line_in >> fmt;
 289   n_vertex_weights = fmt / 10;
 290   edge_weights = (fmt % 10 == 1);
 291
 292   // Determine how many (if any!) vertex weights are included
 293   if (n_vertex_weights) line_in >> n_vertex_weights;
 294
 295   // Setup the iteration data structures
 296   edge_weight = 1.0;
 297   edge.first = 0;
 298   edge.second = 0;
 299   vertex_weights.reserve(n_vertex_weights * num_vertices());
 300 }
 301
 302 metis_distribution::metis_distribution(std::istream& in, process_id_type my_id)
 303   : in(in), my_id(my_id),
 304     vertices(std::istream_iterator<process_id_type>(in),
 305              std::istream_iterator<process_id_type>())
 306 {
 307 }
 308
 309
 310 metis_distribution::size_type
 311 metis_distribution::block_size(process_id_type id, size_type) const
 312 {
 313   return std::count(vertices.begin(), vertices.end(), id);
 314 }
 315
 316 metis_distribution::size_type metis_distribution::local(size_type n) const
 317 {
 318   return std::count(vertices.begin(), vertices.begin() + n, vertices[n]);
 319 }
 320
 321 metis_distribution::size_type
 322 metis_distribution::global(process_id_type id, size_type n) const
 323 {
 324   std::vector<process_id_type>::const_iterator i = vertices.begin();
 325   while (*i != id) ++i;
 326
 327   while (n > 0) {
 328     do { ++i; } while (*i != id);
 329     --n;
 330   }
 331
 332   return i - vertices.begin();
 333 }
 334
 335 #endif
 336
 337 } } // end namespace boost::graph
 338
 339 #endif // BOOST_GRAPH_METIS_HPP