123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL METIS Input Routines</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-metis-input-routines">
- <h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> METIS Input Routines</h1>
- <!-- 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) -->
- <pre class="literal-block">
- namespace boost {
- namespace graph {
- class metis_reader;
- class metis_exception;
- class metis_input_exception;
- class metis_distribution;
- }
- }
- </pre>
- <p><a class="reference external" href="http://www-users.cs.umn.edu/~karypis/metis/metis/">METIS</a> 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.</p>
- <div class="contents topic" id="contents">
- <p class="topic-title first">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#where-defined" id="id3">Where Defined</a><ul>
- <li><a class="reference internal" href="#graph-reader" id="id4">Graph Reader</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#usage" id="id5">Usage</a></li>
- <li><a class="reference internal" href="#associated-types" id="id6">Associated Types</a></li>
- <li><a class="reference internal" href="#member-functions" id="id7">Member Functions</a><ul>
- <li><a class="reference internal" href="#partition-reader" id="id8">Partition Reader</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#id1" id="id9">Usage</a></li>
- <li><a class="reference internal" href="#id2" id="id10">Member Functions</a></li>
- </ul>
- </div>
- <div class="section" id="where-defined">
- <h1><a class="toc-backref" href="#id3">Where Defined</a></h1>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/metis.hpp</span></tt>></p>
- <div class="section" id="graph-reader">
- <h2><a class="toc-backref" href="#id4">Graph Reader</a></h2>
- <pre class="literal-block">
- 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;
- };
- </pre>
- </div>
- </div>
- <div class="section" id="usage">
- <h1><a class="toc-backref" href="#id5">Usage</a></h1>
- <p>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
- <tt class="docutils literal"><span class="pre">g</span></tt> from a METIS graph stored in <tt class="docutils literal"><span class="pre">argv[1]</span></tt>.</p>
- <pre class="literal-block">
- std::ifstream in_graph(argv[1]);
- metis_reader reader(in_graph);
- Graph g(reader.begin(), reader.end(),
- reader.weight_begin(),
- reader.num_vertices());
- </pre>
- <p>The calls to <tt class="docutils literal"><span class="pre">begin()</span></tt> and <tt class="docutils literal"><span class="pre">end()</span></tt> return an iterator range for
- the edges in the graph; the call to <tt class="docutils literal"><span class="pre">weight_begin()</span></tt> 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 <a class="reference internal" href="#partition-reader">Partition Reader</a>.</p>
- </div>
- <div class="section" id="associated-types">
- <h1><a class="toc-backref" href="#id6">Associated Types</a></h1>
- <pre class="literal-block">
- metis_reader::edge_iterator
- </pre>
- <p>An <a class="reference external" href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a> that enumerates the edges in the METIS graph, and
- is suitable for use as the <tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> of an <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>.
- The <tt class="docutils literal"><span class="pre">value_type</span></tt> of this iterator is a pair of vertex numbers.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- metis_reader::edge_weight_iterator
- </pre>
- <p>An <a class="reference external" href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a> that enumerates the edge weights in the METIS
- graph. The <tt class="docutils literal"><span class="pre">value_type</span></tt> of this iterator is <tt class="docutils literal"><span class="pre">edge_weight_type</span></tt>. If
- the edges in the METIS graph are unweighted, the result of
- dereferencing this iterator will always be zero.</p>
- </div>
- <div class="section" id="member-functions">
- <h1><a class="toc-backref" href="#id7">Member Functions</a></h1>
- <pre class="literal-block">
- metis_reader(std::istream& in);
- </pre>
- <p>Constructs a new METIS reader that will retrieve edges from the input
- stream <tt class="docutils literal"><span class="pre">in</span></tt>. If any errors are encountered while initially parsing
- <tt class="docutils literal"><span class="pre">in</span></tt>, <tt class="docutils literal"><span class="pre">metis_input_exception</span></tt> will be thrown.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- edge_iterator begin();
- </pre>
- <p>Returns an iterator to the first edge in the METIS file.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- edge_iterator end();
- </pre>
- <p>Returns an iterator one past the last edge in the METIS file.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- edge_weight_iterator weight_begin();
- </pre>
- <p>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.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- vertices_size_type num_vertices() const;
- </pre>
- <p>Returns the number of vertices in the graph.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- edges_size_type num_edges() const;
- </pre>
- <p>Returns the number of edges in the graph.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::size_t num_vertex_weights() const;
- </pre>
- <p>Returns the number of weights attached to each vertex.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);
- </pre>
- <hr class="docutils" />
- <pre class="literal-block">
- bool has_edge_weights() const;
- </pre>
- <p>Returns <tt class="docutils literal"><span class="pre">true</span></tt> when the edges of the graph have weights, <tt class="docutils literal"><span class="pre">false</span></tt>
- otherwise. When <tt class="docutils literal"><span class="pre">false</span></tt>, the edge weight iterator is still valid
- but returns zero for the weight of each edge.</p>
- <div class="section" id="partition-reader">
- <h2><a class="toc-backref" href="#id8">Partition Reader</a></h2>
- <pre class="literal-block">
- 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;
- };
- </pre>
- </div>
- </div>
- <div class="section" id="id1">
- <h1><a class="toc-backref" href="#id9">Usage</a></h1>
- <p>The class <tt class="docutils literal"><span class="pre">metis_distribution</span></tt> loads a METIS partition file and
- makes it available as a Distribution suitable for use with the
- <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a> graph type. To load a METIS graph using
- a METIS partitioning, use a <tt class="docutils literal"><span class="pre">metis_reader</span></tt> object for the graph and
- a <tt class="docutils literal"><span class="pre">metis_distribution</span></tt> object for the distribution, as in the
- following example.</p>
- <pre class="literal-block">
- 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);
- </pre>
- <p>In this example, <tt class="docutils literal"><span class="pre">argv[1]</span></tt> is the graph and <tt class="docutils literal"><span class="pre">argv[2]</span></tt> is the
- partition file generated by <tt class="docutils literal"><span class="pre">pmetis</span></tt>. The <tt class="docutils literal"><span class="pre">dist</span></tt> 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 <tt class="docutils literal"><span class="pre">pg</span></tt>.</p>
- </div>
- <div class="section" id="id2">
- <h1><a class="toc-backref" href="#id10">Member Functions</a></h1>
- <pre class="literal-block">
- metis_distribution(std::istream& in, process_id_type my_id);
- </pre>
- <p>Creates a new METIS distribution from the input stream
- <tt class="docutils literal"><span class="pre">in</span></tt>. <tt class="docutils literal"><span class="pre">my_id</span></tt> is the process ID of the current process in the
- process group over which the graph will be distributed.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- size_type block_size(process_id_type id, size_type) const;
- </pre>
- <p>Returns the number of vertices to be stored in the process
- <tt class="docutils literal"><span class="pre">id</span></tt>. The second parameter, <tt class="docutils literal"><span class="pre">size_type</span></tt>, is unused and may be any
- value.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- process_id_type operator()(size_type n);
- </pre>
- <p>Returns the ID for the process that will store vertex number <tt class="docutils literal"><span class="pre">n</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- size_type local(size_type n) const;
- </pre>
- <p>Returns the local index of vertex number <tt class="docutils literal"><span class="pre">n</span></tt> within its owning
- process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- size_type global(size_type n) const;
- </pre>
- <p>Returns the global index of the current processor's local vertex <tt class="docutils literal"><span class="pre">n</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- size_type global(process_id_type id, size_type n) const;
- </pre>
- <p>Returns the global index of the process <tt class="docutils literal"><span class="pre">id</span></tt>'s local vertex <tt class="docutils literal"><span class="pre">n</span></tt>.</p>
- <hr class="docutils" />
- <p>Copyright (C) 2005 The Trustees of Indiana University.</p>
- <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:21 UTC.
- Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
- </div>
- </body>
- </html>
|