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 22METIS_ is a set of programs for partitioning graphs (among other 23things). The Parallel BGL can read the METIS graph format and 24partition format, allowing one to easily load METIS-partitioned 25graphs into the Parallel BGL's data structures. 26 27.. contents:: 28 29Where Defined 30~~~~~~~~~~~~~ 31<``boost/graph/metis.hpp``> 32 33 34Graph 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 67Usage 68~~~~~ 69 70The METIS reader provides an iterator interface to the METIS graph 71file. The iterator interface is most useful when constructing Parallel 72BGL 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 84The calls to ``begin()`` and ``end()`` return an iterator range for 85the edges in the graph; the call to ``weight_begin()`` returns an 86iterator that will enumerate the weights of the edges in the 87graph. For a distributed graph, the distribution will be determined 88automatically by the graph; to use a METIS partitioning, see the 89section `Partition Reader`_. 90 91Associated Types 92~~~~~~~~~~~~~~~~ 93 94:: 95 96 metis_reader::edge_iterator 97 98An `Input Iterator`_ that enumerates the edges in the METIS graph, and 99is suitable for use as the ``EdgeIterator`` of an adjacency_list_. 100The ``value_type`` of this iterator is a pair of vertex numbers. 101 102----------------------------------------------------------------------------- 103 104:: 105 106 metis_reader::edge_weight_iterator 107 108An `Input Iterator`_ that enumerates the edge weights in the METIS 109graph. The ``value_type`` of this iterator is ``edge_weight_type``. If 110the edges in the METIS graph are unweighted, the result of 111dereferencing this iterator will always be zero. 112 113Member Functions 114~~~~~~~~~~~~~~~~ 115 116:: 117 118 metis_reader(std::istream& in); 119 120Constructs a new METIS reader that will retrieve edges from the input 121stream ``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 130Returns an iterator to the first edge in the METIS file. 131 132----------------------------------------------------------------------------- 133 134:: 135 136 edge_iterator end(); 137 138Returns an iterator one past the last edge in the METIS file. 139 140----------------------------------------------------------------------------- 141 142:: 143 144 edge_weight_iterator weight_begin(); 145 146Returns an iterator to the first edge weight in the METIS file. The 147weight iterator should be moved in concert with the edge iterator; 148when the edge iterator moves, the edge weight changes. If the edges 149in the graph are unweighted, the weight returned will always be zero. 150 151----------------------------------------------------------------------------- 152 153:: 154 155 vertices_size_type num_vertices() const; 156 157Returns the number of vertices in the graph. 158 159 160----------------------------------------------------------------------------- 161 162:: 163 164 edges_size_type num_edges() const; 165 166Returns the number of edges in the graph. 167 168----------------------------------------------------------------------------- 169 170:: 171 172 std::size_t num_vertex_weights() const; 173 174Returns 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 188Returns ``true`` when the edges of the graph have weights, ``false`` 189otherwise. When ``false``, the edge weight iterator is still valid 190but returns zero for the weight of each edge. 191 192 193Partition 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 219Usage 220~~~~~ 221 222The class ``metis_distribution`` loads a METIS partition file and 223makes it available as a Distribution suitable for use with the 224`distributed adjacency list`_ graph type. To load a METIS graph using 225a METIS partitioning, use a ``metis_reader`` object for the graph and 226a ``metis_distribution`` object for the distribution, as in the 227following 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 242In this example, ``argv[1]`` is the graph and ``argv[2]`` is the 243partition file generated by ``pmetis``. The ``dist`` object loads the 244partitioning information from the input stream it is given and uses 245that to distributed the adjacency list. Note that the input stream 246must be in the METIS partition file format and must have been 247partitioned for the same number of processes are there are in the 248process group ``pg``. 249 250Member Functions 251~~~~~~~~~~~~~~~~ 252 253:: 254 255 metis_distribution(std::istream& in, process_id_type my_id); 256 257Creates a new METIS distribution from the input stream 258``in``. ``my_id`` is the process ID of the current process in the 259process 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 267Returns the number of vertices to be stored in the process 268``id``. The second parameter, ``size_type``, is unused and may be any 269value. 270 271----------------------------------------------------------------------------- 272 273:: 274 275 process_id_type operator()(size_type n); 276 277Returns 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 285Returns the local index of vertex number ``n`` within its owning 286process. 287 288----------------------------------------------------------------------------- 289 290:: 291 292 size_type global(size_type n) const; 293 294Returns 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 303Returns the global index of the process ``id``'s local vertex ``n``. 304 305----------------------------------------------------------------------------- 306 307Copyright (C) 2005 The Trustees of Indiana University. 308 309Authors: 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 321
