ceph/src/boost/libs/graph_parallel/doc/metis.rst

   1 .. Copyright (C) 2004-2008 The Trustees of Indiana University.
   2    Use, modification and distribution is subject to the Boost Software
   3    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4    http://www.boost.org/LICENSE_1_0.txt)
   5
   6 =========================================
   7 |Logo| METIS Input Routines
   8 =========================================
   9
  10 ::
  11
  12   namespace boost {
  13     namespace graph {
  14       class metis_reader;
  15       class metis_exception;
  16       class metis_input_exception;
  17       class metis_distribution;
  18     }
  19   }
  20
  21
  22 METIS_ is a set of programs for partitioning graphs (among other
  23 things). The Parallel BGL can read the METIS graph format and
  24 partition format, allowing one to easily load METIS-partitioned
  25 graphs into the Parallel BGL's data structures.
  26
  27 .. contents::
  28
  29 Where Defined
  30 ~~~~~~~~~~~~~
  31 <``boost/graph/metis.hpp``>
  32
  33
  34 Graph Reader
  35 ------------------
  36
  37 ::
  38
  39   class metis_reader
  40   {
  41    public:
  42     typedef std::size_t vertices_size_type;
  43     typedef std::size_t edges_size_type;
  44     typedef double vertex_weight_type;
  45     typedef double edge_weight_type;
  46
  47     class edge_iterator;
  48     class edge_weight_iterator;
  49
  50     metis_reader(std::istream& in);
  51
  52     edge_iterator begin();
  53     edge_iterator end();
  54     edge_weight_iterator weight_begin();
  55
  56     vertices_size_type num_vertices() const;
  57     edges_size_type num_edges() const;
  58
  59     std::size_t num_vertex_weights() const;
  60
  61     vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);
  62
  63     bool has_edge_weights() const;
  64   };
  65
  66
  67 Usage
  68 ~~~~~
  69
  70 The METIS reader provides an iterator interface to the METIS graph
  71 file. The iterator interface is most useful when constructing Parallel
  72 BGL graphs on-the-fly. For instance, the following code builds a graph
  73 ``g`` from a METIS graph stored in ``argv[1]``.
  74
  75 ::
  76
  77   std::ifstream in_graph(argv[1]);
  78   metis_reader reader(in_graph);
  79   Graph g(reader.begin(), reader.end(),
  80           reader.weight_begin(),
  81           reader.num_vertices());
  82
  83
  84 The calls to ``begin()`` and ``end()`` return an iterator range for
  85 the edges in the graph; the call to ``weight_begin()`` returns an
  86 iterator that will enumerate the weights of the edges in the
  87 graph. For a distributed graph, the distribution will be determined
  88 automatically by the graph; to use a METIS partitioning, see the
  89 section `Partition Reader`_.
  90
  91 Associated Types
  92 ~~~~~~~~~~~~~~~~
  93
  94 ::
  95
  96   metis_reader::edge_iterator
  97
  98 An `Input Iterator`_ that enumerates the edges in the METIS graph, and
  99 is suitable for use as the ``EdgeIterator`` of an adjacency_list_.
 100 The ``value_type`` of this iterator is a pair of vertex numbers.
 101
 102 -----------------------------------------------------------------------------
 103
 104 ::
 105
 106   metis_reader::edge_weight_iterator
 107
 108 An `Input Iterator`_ that enumerates the edge weights in the METIS
 109 graph. The ``value_type`` of this iterator is ``edge_weight_type``. If
 110 the edges in the METIS graph are unweighted, the result of
 111 dereferencing this iterator will always be zero.
 112
 113 Member Functions
 114 ~~~~~~~~~~~~~~~~
 115
 116 ::
 117
 118   metis_reader(std::istream& in);
 119
 120 Constructs a new METIS reader that will retrieve edges from the input
 121 stream ``in``. If any errors are encountered while initially parsing
 122 ``in``, ``metis_input_exception`` will be thrown.
 123
 124 -----------------------------------------------------------------------------
 125
 126 ::
 127
 128   edge_iterator begin();
 129
 130 Returns an iterator to the first edge in the METIS file.
 131
 132 -----------------------------------------------------------------------------
 133
 134 ::
 135
 136   edge_iterator end();
 137
 138 Returns an iterator one past the last edge in the METIS file.
 139
 140 -----------------------------------------------------------------------------
 141
 142 ::
 143
 144   edge_weight_iterator weight_begin();
 145
 146 Returns an iterator to the first edge weight in the METIS file. The
 147 weight iterator should be moved in concert with the edge iterator;
 148 when the edge iterator moves, the edge weight changes. If the edges
 149 in the graph are unweighted, the weight returned will always be zero.
 150
 151 -----------------------------------------------------------------------------
 152
 153 ::
 154
 155   vertices_size_type num_vertices() const;
 156
 157 Returns the number of vertices in the graph.
 158
 159
 160 -----------------------------------------------------------------------------
 161
 162 ::
 163
 164     edges_size_type num_edges() const;
 165
 166 Returns the number of edges in the graph.
 167
 168 -----------------------------------------------------------------------------
 169
 170 ::
 171
 172     std::size_t num_vertex_weights() const;
 173
 174 Returns the number of weights attached to each vertex.
 175
 176 -----------------------------------------------------------------------------
 177
 178 ::
 179
 180     vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);
 181
 182 -----------------------------------------------------------------------------
 183
 184 ::
 185
 186     bool has_edge_weights() const;
 187
 188 Returns ``true`` when the edges of the graph have weights, ``false``
 189 otherwise. When ``false``, the edge weight iterator is still valid
 190 but returns zero for the weight of each edge.
 191
 192
 193 Partition Reader
 194 ----------------
 195
 196 ::
 197
 198   class metis_distribution
 199   {
 200    public:
 201     typedef int process_id_type;
 202     typedef std::size_t size_type;
 203
 204     metis_distribution(std::istream& in, process_id_type my_id);
 205
 206     size_type block_size(process_id_type id, size_type) const;
 207     process_id_type operator()(size_type n);
 208     size_type local(size_type n) const;
 209     size_type global(size_type n) const;
 210     size_type global(process_id_type id, size_type n) const;
 211
 212    private:
 213     std::istream& in;
 214     process_id_type my_id;
 215     std::vector<process_id_type> vertices;
 216   };
 217
 218
 219 Usage
 220 ~~~~~
 221
 222 The class ``metis_distribution`` loads a METIS partition file and
 223 makes it available as a Distribution suitable for use with the
 224 `distributed adjacency list`_ graph type. To load a METIS graph using
 225 a METIS partitioning, use a ``metis_reader`` object for the graph and
 226 a ``metis_distribution`` object for the distribution, as in the
 227 following example.
 228
 229 ::
 230
 231   std::ifstream in_graph(argv[1]);
 232   metis_reader reader(in_graph);
 233
 234   std::ifstream in_partitions(argv[2]);
 235   metis_distribution dist(in_partitions, process_id(pg));
 236   Graph g(reader.begin(), reader.end(),
 237           reader.weight_begin(),
 238           reader.num_vertices(),
 239           pg,
 240           dist);
 241
 242 In this example, ``argv[1]`` is the graph and ``argv[2]`` is the
 243 partition file generated by ``pmetis``. The ``dist`` object loads the
 244 partitioning information from the input stream it is given and uses
 245 that to distributed the adjacency list. Note that the input stream
 246 must be in the METIS partition file format and must have been
 247 partitioned for the same number of processes are there are in the
 248 process group ``pg``.
 249
 250 Member Functions
 251 ~~~~~~~~~~~~~~~~
 252
 253 ::
 254
 255   metis_distribution(std::istream& in, process_id_type my_id);
 256
 257 Creates a new METIS distribution from the input stream
 258 ``in``. ``my_id`` is the process ID of the current process in the
 259 process group over which the graph will be distributed.
 260
 261 -----------------------------------------------------------------------------
 262
 263 ::
 264
 265   size_type block_size(process_id_type id, size_type) const;
 266
 267 Returns the number of vertices to be stored in the process
 268 ``id``. The second parameter, ``size_type``, is unused and may be any
 269 value.
 270
 271 -----------------------------------------------------------------------------
 272
 273 ::
 274
 275   process_id_type operator()(size_type n);
 276
 277 Returns the ID for the process that will store vertex number ``n``.
 278
 279 -----------------------------------------------------------------------------
 280
 281 ::
 282
 283   size_type local(size_type n) const;
 284
 285 Returns the local index of vertex number ``n`` within its owning
 286 process.
 287
 288 -----------------------------------------------------------------------------
 289
 290 ::
 291
 292   size_type global(size_type n) const;
 293
 294 Returns the global index of the current processor's local vertex ``n``.
 295
 296 -----------------------------------------------------------------------------
 297
 298
 299 ::
 300
 301   size_type global(process_id_type id, size_type n) const;
 302
 303 Returns the global index of the process ``id``'s local vertex ``n``.
 304
 305 -----------------------------------------------------------------------------
 306
 307 Copyright (C) 2005 The Trustees of Indiana University.
 308
 309 Authors: Douglas Gregor and Andrew Lumsdaine
 310
 311 .. _METIS: http://www-users.cs.umn.edu/~karypis/metis/metis/
 312 .. _distributed adjacency list: distributed_adjacency_list.html
 313 .. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
 314 .. _input iterator: http://www.sgi.com/tech/stl/InputIterator.html
 315
 316 .. |Logo| image:: pbgl-logo.png
 317             :align: middle
 318             :alt: Parallel BGL
 319             :target: http://www.osl.iu.edu/research/pbgl
 320