ceph/src/boost/libs/graph/include/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   process_id_type my_id;
 165   std::vector<process_id_type> vertices;
 166 };
 167
 168 #if !defined(BOOST_GRAPH_METIS_NO_INLINE) || defined(BOOST_GRAPH_METIS_SOURCE)
 169 BOOST_GRAPH_METIS_INLINE_KEYWORD
 170 bool operator==(metis_reader::edge_iterator x, metis_reader::edge_iterator y)
 171 {
 172   return (x.self == y.self
 173           || (x.self && x.self->edge.first == x.self->num_vertices())
 174           || (y.self && y.self->edge.first == y.self->num_vertices()));
 175 }
 176
 177 BOOST_GRAPH_METIS_INLINE_KEYWORD
 178 bool operator!=(metis_reader::edge_iterator x, metis_reader::edge_iterator y)
 179 {
 180   return !(x == y);
 181 }
 182
 183 BOOST_GRAPH_METIS_INLINE_KEYWORD
 184 metis_reader::edge_iterator::edge_iterator(metis_reader* self)
 185   : self(self)
 186 {
 187   if (self) advance(true);
 188 }
 189
 190 BOOST_GRAPH_METIS_INLINE_KEYWORD
 191 metis_reader::edge_iterator& metis_reader::edge_iterator::operator++()
 192 {
 193   advance(false);
 194   return *this;
 195 }
 196
 197 BOOST_GRAPH_METIS_INLINE_KEYWORD
 198 void metis_reader::edge_iterator::advance(bool skip_initial_read)
 199 {
 200   do {
 201
 202     if (!skip_initial_read) {
 203       // Try to read the next edge
 204       if (self->line_in >> std::ws >> self->edge.second) {
 205         --self->edge.second;
 206         if (self->has_edge_weights()) {
 207           if (!(self->line_in >> self->edge_weight))
 208             boost::throw_exception(metis_input_exception());
 209         }
 210         return;
 211       }
 212
 213       // Check if we're done
 214       ++self->edge.first;
 215       if (self->edge.first == self->num_vertices())
 216         return;
 217     }
 218
 219     // Find the next line
 220     std::string line;
 221     while (getline(self->in, line) && !line.empty() && line[0] == '%') {
 222       /* Keep reading lines in the loop header... */
 223     }
 224     if (!self->in) boost::throw_exception(metis_input_exception());
 225     self->line_in.str(line);
 226     self->line_in.clear();
 227
 228     // Read the next line
 229     std::size_t weights_left = self->n_vertex_weights;
 230     vertex_weight_type weight;
 231     while (weights_left > 0) {
 232       if (self->line_in >> weight) self->vertex_weights.push_back(weight);
 233       else boost::throw_exception(metis_input_exception());
 234       --weights_left;
 235     }
 236
 237     // Successive iterations will pick up edges for this vertex.
 238     skip_initial_read = false;
 239   } while (true);
 240 }
 241
 242 BOOST_GRAPH_METIS_INLINE_KEYWORD
 243 metis_reader::edge_iterator::postincrement_proxy
 244 metis_reader::edge_iterator::operator++(int)
 245 {
 246   postincrement_proxy result(**this);
 247   ++(*this);
 248   return result;
 249 }
 250
 251 BOOST_GRAPH_METIS_INLINE_KEYWORD
 252 metis_reader::edge_iterator metis_reader::begin()
 253 {
 254   if (edge.first != 0) start();
 255   return edge_iterator(this);
 256 }
 257
 258 BOOST_GRAPH_METIS_INLINE_KEYWORD
 259 metis_reader::edge_iterator metis_reader::end()
 260 {
 261   return edge_iterator(0);
 262 }
 263
 264 BOOST_GRAPH_METIS_INLINE_KEYWORD
 265 metis_reader::edge_weight_iterator metis_reader::weight_begin()
 266 {
 267   return edge_weight_iterator(this);
 268 }
 269
 270 BOOST_GRAPH_METIS_INLINE_KEYWORD
 271 void metis_reader::start()
 272 {
 273   in.seekg(0, std::ios::beg);
 274   std::string line;
 275   while (getline(in, line) && !line.empty() && line[0] == '%') {
 276     /* Keep getting lines in loop header. */
 277   }
 278
 279   if (!in || line.empty()) boost::throw_exception(metis_input_exception());
 280
 281   // Determine number of vertices and edges in the graph
 282   line_in.str(line);
 283   if (!(line_in >> n_vertices >> n_edges)) boost::throw_exception(metis_input_exception());
 284
 285   // Determine whether vertex or edge weights are included in the graph
 286   int fmt = 0;
 287   line_in >> fmt;
 288   n_vertex_weights = fmt / 10;
 289   edge_weights = (fmt % 10 == 1);
 290
 291   // Determine how many (if any!) vertex weights are included
 292   if (n_vertex_weights) line_in >> n_vertex_weights;
 293
 294   // Setup the iteration data structures
 295   edge_weight = 1.0;
 296   edge.first = 0;
 297   edge.second = 0;
 298   vertex_weights.reserve(n_vertex_weights * num_vertices());
 299 }
 300
 301 metis_distribution::metis_distribution(std::istream& in, process_id_type my_id)
 302   : my_id(my_id),
 303     vertices(std::istream_iterator<process_id_type>(in),
 304              std::istream_iterator<process_id_type>())
 305 {
 306 }
 307
 308
 309 metis_distribution::size_type
 310 metis_distribution::block_size(process_id_type id, size_type) const
 311 {
 312   return std::count(vertices.begin(), vertices.end(), id);
 313 }
 314
 315 metis_distribution::size_type metis_distribution::local(size_type n) const
 316 {
 317   return std::count(vertices.begin(), vertices.begin() + n, vertices[n]);
 318 }
 319
 320 metis_distribution::size_type
 321 metis_distribution::global(process_id_type id, size_type n) const
 322 {
 323   std::vector<process_id_type>::const_iterator i = vertices.begin();
 324   while (*i != id) ++i;
 325
 326   while (n > 0) {
 327     do { ++i; } while (*i != id);
 328     --n;
 329   }
 330
 331   return i - vertices.begin();
 332 }
 333
 334 #endif
 335
 336 } } // end namespace boost::graph
 337
 338 #endif // BOOST_GRAPH_METIS_HPP