| .. Copyright (C) 2004-2008 The Trustees of Indiana University. |
| Use, modification and distribution is subject to the Boost Software |
| License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| |
| ========================================= |
| |Logo| METIS Input Routines |
| ========================================= |
| |
| :: |
| |
| namespace boost { |
| namespace graph { |
| class metis_reader; |
| class metis_exception; |
| class metis_input_exception; |
| class metis_distribution; |
| } |
| } |
| |
| |
| METIS_ is a set of programs for partitioning graphs (among other |
| things). The Parallel BGL can read the METIS graph format and |
| partition format, allowing one to easily load METIS-partitioned |
| graphs into the Parallel BGL's data structures. |
| |
| .. contents:: |
| |
| Where Defined |
| ~~~~~~~~~~~~~ |
| <``boost/graph/metis.hpp``> |
| |
| |
| Graph Reader |
| ------------------ |
| |
| :: |
| |
| class metis_reader |
| { |
| public: |
| typedef std::size_t vertices_size_type; |
| typedef std::size_t edges_size_type; |
| typedef double vertex_weight_type; |
| typedef double edge_weight_type; |
| |
| class edge_iterator; |
| class edge_weight_iterator; |
| |
| metis_reader(std::istream& in); |
| |
| edge_iterator begin(); |
| edge_iterator end(); |
| edge_weight_iterator weight_begin(); |
| |
| vertices_size_type num_vertices() const; |
| edges_size_type num_edges() const; |
| |
| std::size_t num_vertex_weights() const; |
| |
| vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n); |
| |
| bool has_edge_weights() const; |
| }; |
| |
| |
| Usage |
| ~~~~~ |
| |
| The METIS reader provides an iterator interface to the METIS graph |
| file. The iterator interface is most useful when constructing Parallel |
| BGL graphs on-the-fly. For instance, the following code builds a graph |
| ``g`` from a METIS graph stored in ``argv[1]``. |
| |
| :: |
| |
| std::ifstream in_graph(argv[1]); |
| metis_reader reader(in_graph); |
| Graph g(reader.begin(), reader.end(), |
| reader.weight_begin(), |
| reader.num_vertices()); |
| |
| |
| The calls to ``begin()`` and ``end()`` return an iterator range for |
| the edges in the graph; the call to ``weight_begin()`` returns an |
| iterator that will enumerate the weights of the edges in the |
| graph. For a distributed graph, the distribution will be determined |
| automatically by the graph; to use a METIS partitioning, see the |
| section `Partition Reader`_. |
| |
| Associated Types |
| ~~~~~~~~~~~~~~~~ |
| |
| :: |
| |
| metis_reader::edge_iterator |
| |
| An `Input Iterator`_ that enumerates the edges in the METIS graph, and |
| is suitable for use as the ``EdgeIterator`` of an adjacency_list_. |
| The ``value_type`` of this iterator is a pair of vertex numbers. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| metis_reader::edge_weight_iterator |
| |
| An `Input Iterator`_ that enumerates the edge weights in the METIS |
| graph. The ``value_type`` of this iterator is ``edge_weight_type``. If |
| the edges in the METIS graph are unweighted, the result of |
| dereferencing this iterator will always be zero. |
| |
| Member Functions |
| ~~~~~~~~~~~~~~~~ |
| |
| :: |
| |
| metis_reader(std::istream& in); |
| |
| Constructs a new METIS reader that will retrieve edges from the input |
| stream ``in``. If any errors are encountered while initially parsing |
| ``in``, ``metis_input_exception`` will be thrown. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| edge_iterator begin(); |
| |
| Returns an iterator to the first edge in the METIS file. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| edge_iterator end(); |
| |
| Returns an iterator one past the last edge in the METIS file. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| edge_weight_iterator weight_begin(); |
| |
| Returns an iterator to the first edge weight in the METIS file. The |
| weight iterator should be moved in concert with the edge iterator; |
| when the edge iterator moves, the edge weight changes. If the edges |
| in the graph are unweighted, the weight returned will always be zero. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| vertices_size_type num_vertices() const; |
| |
| Returns the number of vertices in the graph. |
| |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| edges_size_type num_edges() const; |
| |
| Returns the number of edges in the graph. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| std::size_t num_vertex_weights() const; |
| |
| Returns the number of weights attached to each vertex. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n); |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| bool has_edge_weights() const; |
| |
| Returns ``true`` when the edges of the graph have weights, ``false`` |
| otherwise. When ``false``, the edge weight iterator is still valid |
| but returns zero for the weight of each edge. |
| |
| |
| Partition Reader |
| ---------------- |
| |
| :: |
| |
| class metis_distribution |
| { |
| public: |
| typedef int process_id_type; |
| typedef std::size_t size_type; |
| |
| metis_distribution(std::istream& in, process_id_type my_id); |
| |
| size_type block_size(process_id_type id, size_type) const; |
| process_id_type operator()(size_type n); |
| size_type local(size_type n) const; |
| size_type global(size_type n) const; |
| size_type global(process_id_type id, size_type n) const; |
| |
| private: |
| std::istream& in; |
| process_id_type my_id; |
| std::vector<process_id_type> vertices; |
| }; |
| |
| |
| Usage |
| ~~~~~ |
| |
| The class ``metis_distribution`` loads a METIS partition file and |
| makes it available as a Distribution suitable for use with the |
| `distributed adjacency list`_ graph type. To load a METIS graph using |
| a METIS partitioning, use a ``metis_reader`` object for the graph and |
| a ``metis_distribution`` object for the distribution, as in the |
| following example. |
| |
| :: |
| |
| std::ifstream in_graph(argv[1]); |
| metis_reader reader(in_graph); |
| |
| std::ifstream in_partitions(argv[2]); |
| metis_distribution dist(in_partitions, process_id(pg)); |
| Graph g(reader.begin(), reader.end(), |
| reader.weight_begin(), |
| reader.num_vertices(), |
| pg, |
| dist); |
| |
| In this example, ``argv[1]`` is the graph and ``argv[2]`` is the |
| partition file generated by ``pmetis``. The ``dist`` object loads the |
| partitioning information from the input stream it is given and uses |
| that to distributed the adjacency list. Note that the input stream |
| must be in the METIS partition file format and must have been |
| partitioned for the same number of processes are there are in the |
| process group ``pg``. |
| |
| Member Functions |
| ~~~~~~~~~~~~~~~~ |
| |
| :: |
| |
| metis_distribution(std::istream& in, process_id_type my_id); |
| |
| Creates a new METIS distribution from the input stream |
| ``in``. ``my_id`` is the process ID of the current process in the |
| process group over which the graph will be distributed. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| size_type block_size(process_id_type id, size_type) const; |
| |
| Returns the number of vertices to be stored in the process |
| ``id``. The second parameter, ``size_type``, is unused and may be any |
| value. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| process_id_type operator()(size_type n); |
| |
| Returns the ID for the process that will store vertex number ``n``. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| size_type local(size_type n) const; |
| |
| Returns the local index of vertex number ``n`` within its owning |
| process. |
| |
| ----------------------------------------------------------------------------- |
| |
| :: |
| |
| size_type global(size_type n) const; |
| |
| Returns the global index of the current processor's local vertex ``n``. |
| |
| ----------------------------------------------------------------------------- |
| |
| |
| :: |
| |
| size_type global(process_id_type id, size_type n) const; |
| |
| Returns the global index of the process ``id``'s local vertex ``n``. |
| |
| ----------------------------------------------------------------------------- |
| |
| Copyright (C) 2005 The Trustees of Indiana University. |
| |
| Authors: Douglas Gregor and Andrew Lumsdaine |
| |
| .. _METIS: http://www-users.cs.umn.edu/~karypis/metis/metis/ |
| .. _distributed adjacency list: distributed_adjacency_list.html |
| .. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html |
| .. _input iterator: http://www.sgi.com/tech/stl/InputIterator.html |
| |
| .. |Logo| image:: pbgl-logo.png |
| :align: middle |
| :alt: Parallel BGL |
| :target: http://www.osl.iu.edu/research/pbgl |
| |