]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |