123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320 |
- .. 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
-
|