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)
6 =========================================
7 |Logo| METIS Input Routines
8 =========================================
15 class metis_exception;
16 class metis_input_exception;
17 class metis_distribution;
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.
31 <``boost/graph/metis.hpp``>
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;
48 class edge_weight_iterator;
50 metis_reader(std::istream& in);
52 edge_iterator begin();
54 edge_weight_iterator weight_begin();
56 vertices_size_type num_vertices() const;
57 edges_size_type num_edges() const;
59 std::size_t num_vertex_weights() const;
61 vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);
63 bool has_edge_weights() const;
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]``.
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());
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`_.
96 metis_reader::edge_iterator
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.
102 -----------------------------------------------------------------------------
106 metis_reader::edge_weight_iterator
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.
118 metis_reader(std::istream& in);
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.
124 -----------------------------------------------------------------------------
128 edge_iterator begin();
130 Returns an iterator to the first edge in the METIS file.
132 -----------------------------------------------------------------------------
138 Returns an iterator one past the last edge in the METIS file.
140 -----------------------------------------------------------------------------
144 edge_weight_iterator weight_begin();
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.
151 -----------------------------------------------------------------------------
155 vertices_size_type num_vertices() const;
157 Returns the number of vertices in the graph.
160 -----------------------------------------------------------------------------
164 edges_size_type num_edges() const;
166 Returns the number of edges in the graph.
168 -----------------------------------------------------------------------------
172 std::size_t num_vertex_weights() const;
174 Returns the number of weights attached to each vertex.
176 -----------------------------------------------------------------------------
180 vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);
182 -----------------------------------------------------------------------------
186 bool has_edge_weights() const;
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.
198 class metis_distribution
201 typedef int process_id_type;
202 typedef std::size_t size_type;
204 metis_distribution(std::istream& in, process_id_type my_id);
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;
214 process_id_type my_id;
215 std::vector<process_id_type> vertices;
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
231 std::ifstream in_graph(argv[1]);
232 metis_reader reader(in_graph);
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(),
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``.
255 metis_distribution(std::istream& in, process_id_type my_id);
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.
261 -----------------------------------------------------------------------------
265 size_type block_size(process_id_type id, size_type) const;
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
271 -----------------------------------------------------------------------------
275 process_id_type operator()(size_type n);
277 Returns the ID for the process that will store vertex number ``n``.
279 -----------------------------------------------------------------------------
283 size_type local(size_type n) const;
285 Returns the local index of vertex number ``n`` within its owning
288 -----------------------------------------------------------------------------
292 size_type global(size_type n) const;
294 Returns the global index of the current processor's local vertex ``n``.
296 -----------------------------------------------------------------------------
301 size_type global(process_id_type id, size_type n) const;
303 Returns the global index of the process ``id``'s local vertex ``n``.
305 -----------------------------------------------------------------------------
307 Copyright (C) 2005 The Trustees of Indiana University.
309 Authors: Douglas Gregor and Andrew Lumsdaine
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
316 .. |Logo| image:: pbgl-logo.png
319 :target: http://www.osl.iu.edu/research/pbgl