123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804 |
- <?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 Distributed Adjacency List</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-distributed-adjacency-list">
- <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> Distributed Adjacency List</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) -->
- <div class="contents topic" id="contents">
- <p class="topic-title first">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#introduction" id="id1">Introduction</a><ul>
- <li><a class="reference internal" href="#defining-a-distributed-adjacency-list" id="id2">Defining a Distributed Adjacency List</a></li>
- <li><a class="reference internal" href="#distributed-vertex-and-edge-properties" id="id3">Distributed Vertex and Edge Properties</a></li>
- <li><a class="reference internal" href="#named-vertices" id="id4">Named Vertices</a></li>
- <li><a class="reference internal" href="#building-a-distributed-graph" id="id5">Building a Distributed Graph</a></li>
- <li><a class="reference internal" href="#graph-concepts" id="id6">Graph Concepts</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#reference" id="id7">Reference</a><ul>
- <li><a class="reference internal" href="#where-defined" id="id8">Where Defined</a></li>
- <li><a class="reference internal" href="#associated-types" id="id9">Associated Types</a></li>
- <li><a class="reference internal" href="#member-functions" id="id10">Member Functions</a></li>
- <li><a class="reference internal" href="#non-member-functions" id="id11">Non-Member Functions</a></li>
- <li><a class="reference internal" href="#structure-modification" id="id12">Structure Modification</a></li>
- <li><a class="reference internal" href="#property-map-accessors" id="id13">Property Map Accessors</a></li>
- </ul>
- </li>
- </ul>
- </div>
- <div class="section" id="introduction">
- <h1><a class="toc-backref" href="#id1">Introduction</a></h1>
- <p>The distributed adjacency list implements a graph data structure using
- an adjacency list representation. Its interface and behavior are
- roughly equivalent to the Boost Graph Library's <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>
- class template. However, the distributed adjacency list partitions the
- vertices of the graph across several processes (which need not share
- an address space). Edges outgoing from any vertex stored by a process
- are also stored on that process, except in the case of undirected
- graphs, where either the source or the target may store the edge.</p>
- <pre class="literal-block">
- template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS,
- typename DirectedS, typename VertexProperty, typename EdgeProperty,
- typename GraphProperty, typename EdgeListS>
- class adjacency_list<OutEdgeListS,
- distributedS<ProcessGroup, VertexListS>,
- DirectedS, VertexProperty,
- EdgeProperty, GraphProperty, EdgeListS>;
- </pre>
- <div class="section" id="defining-a-distributed-adjacency-list">
- <h2><a class="toc-backref" href="#id2">Defining a Distributed Adjacency List</a></h2>
- <p>To create a distributed adjacency list, first determine the
- representation of the graph in a single address space using these
- <a class="reference external" href="http://www.boost.org/libs/graph/doc/using_adjacency_list.html">guidelines</a>. Next, replace the vertex list selector (<tt class="docutils literal"><span class="pre">VertexListS</span></tt>)
- with an instantiation of <a class="reference external" href="distributedS.html">distributedS</a>, which includes:</p>
- <ul class="simple">
- <li>Selecting a <a class="reference external" href="process_group.html">process group</a> type that represents the various
- coordinating processes that will store the distributed graph. For
- example, the <a class="reference external" href="process_group.html">MPI process group</a>.</li>
- <li>A selector indicating how the vertex lists in each process will be
- stored. Only the <tt class="docutils literal"><span class="pre">vecS</span></tt> and <tt class="docutils literal"><span class="pre">listS</span></tt> selectors are well-supported
- at this time.</li>
- </ul>
- <p>The following <tt class="docutils literal"><span class="pre">typedef</span></tt> defines a distributed adjacency list
- containing directed edges. The vertices in the graph will be
- distributed over several processes, using the MPI process group
- for communication. In each process, the vertices and outgoing edges
- will be stored in STL vectors. There are no properties attached to the
- vertices or edges of the graph.</p>
- <pre class="literal-block">
- using namespace boost;
- typedef adjacency_list<vecS,
- distributedS<parallel::mpi::bsp_process_group, vecS>,
- directedS>
- Graph;
- </pre>
- </div>
- <div class="section" id="distributed-vertex-and-edge-properties">
- <h2><a class="toc-backref" href="#id3">Distributed Vertex and Edge Properties</a></h2>
- <p>Vertex and edge properties for distributed graphs mirror their
- counterparts for non-distributed graphs. With a distributed graph,
- however, vertex and edge properties are stored only in the process
- that owns the vertex or edge.</p>
- <p>The most direct way to attach properties to a distributed graph is to
- create a structure that will be attached to each of the vertices and
- edges of the graph. For example, if we wish to model a simplistic map
- of the United States interstate highway system, we might state that
- the vertices of the graph are cities and the edges are highways, then
- define the information that we maintain for each city and highway:</p>
- <pre class="literal-block">
- struct City {
- City() { }
- City(const std::string& name, const std::string& mayor = "Unknown", int population = 0)
- : name(name), mayor(mayor), population(population) { }
- std::string name;
- std::string mayor;
- int population;
- // Serialization support is required!
- template<typename Archiver>
- void serialize(Archiver& ar, const unsigned int /*version*/) {
- ar & name & mayor & population;
- }
- };
- struct Highway {
- Highway() { }
- Highway(const std::string& name, int lanes, int miles_per_hour, int length)
- : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { }
- std::string name;
- int lanes;
- int miles_per_hour;
- int length;
- // Serialization support is required!
- template<typename Archiver>
- void serialize(Archiver& ar, const unsigned int /*version*/) {
- ar & name & lanes & miles_per_hour & length;
- }
- };
- </pre>
- <p>To create a distributed graph for a road map, we supply <tt class="docutils literal"><span class="pre">City</span></tt> and
- <tt class="docutils literal"><span class="pre">Highway</span></tt> as the fourth and fifth parameters to <tt class="docutils literal"><span class="pre">adjacency_list</span></tt>,
- respectively:</p>
- <pre class="literal-block">
- typedef adjacency_list<vecS,
- distributedS<parallel::mpi::bsp_process_group, vecS>,
- directedS,
- City, Highway>
- RoadMap;
- </pre>
- <p>Property maps for internal properties retain their behavior with
- distributed graphs via <a class="reference external" href="distributed_property_map.html">distributed property maps</a>, which automate
- communication among processes so that <tt class="docutils literal"><span class="pre">put</span></tt> and <tt class="docutils literal"><span class="pre">get</span></tt> operations
- may be applied to non-local vertices and edges. However, for
- distributed adjacency lists that store vertices in a vector
- (<tt class="docutils literal"><span class="pre">VertexListS</span></tt> is <tt class="docutils literal"><span class="pre">vecS</span></tt>), the automatic <tt class="docutils literal"><span class="pre">vertex_index</span></tt>
- property map restricts the domain of <tt class="docutils literal"><span class="pre">put</span></tt> and <tt class="docutils literal"><span class="pre">get</span></tt> operations
- to vertices local to the process executing the operation. For example,
- we can create a property map that accesses the length of each highway
- as follows:</p>
- <pre class="literal-block">
- RoadMap map; // distributed graph instance
- typedef property_map<RoadMap, int Highway::*>::type
- road_length = get(&Highway::length, map);
- </pre>
- <p>Now, one can access the length of any given road based on its edge
- descriptor <tt class="docutils literal"><span class="pre">e</span></tt> with the expression <tt class="docutils literal"><span class="pre">get(road_length,</span> <span class="pre">e)</span></tt>,
- regardless of which process stores the edge <tt class="docutils literal"><span class="pre">e</span></tt>.</p>
- </div>
- <div class="section" id="named-vertices">
- <h2><a class="toc-backref" href="#id4">Named Vertices</a></h2>
- <p>The vertices of a graph typically correspond to named entities within
- the application domain. In the road map example from the previous
- section, the vertices in the graph represent cities. The distributed
- adjacency list supports named vertices, which provides an implicit
- mapping from the names of the vertices in the application domain
- (e.g., the name of a city, such as "Bloomington") to the actual vertex
- descriptor stored within the distributed graph (e.g., the third vertex
- on processor 1). By enabling support for named vertices, one can refer
- to vertices by name when manipulating the graph. For example, one can
- add a highway from Indianapolis to Chicago:</p>
- <pre class="literal-block">
- add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map);
- </pre>
- <p>The distributed adjacency list will find vertices associated with the
- names "Indianapolis" and "Chicago", then add an edge between these
- vertices that represents I-65. The vertices may be stored on any
- processor, local or remote.</p>
- <p>To enable named vertices, specialize the <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt>
- property for the structure attached to the vertices in your
- graph. <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt> contains a single member, <tt class="docutils literal"><span class="pre">type</span></tt>,
- which is the type of a function object that accepts a vertex property
- and returns the name stored within that vertex property. In the case
- of our road map, the <tt class="docutils literal"><span class="pre">name</span></tt> field contains the name of each city, so
- we use the <tt class="docutils literal"><span class="pre">member</span></tt> function object from the <a class="reference external" href="http://www.boost.org/libs/multi_index/doc/index.html">Boost.MultiIndex</a>
- library to extract the name, e.g.,</p>
- <pre class="literal-block">
- namespace boost { namespace graph {
- template<>
- struct internal_vertex_name<City>
- {
- typedef multi_index::member<City, std::string, &City::name> type;
- };
- } }
- </pre>
- <p>That's it! One can now refer to vertices by name when interacting with
- the distributed adjacency list.</p>
- <p>What happens when one uses the name of a vertex that does not exist?
- For example, in our <tt class="docutils literal"><span class="pre">add_edge</span></tt> call above, what happens if the
- vertex named "Indianapolis" has not yet been added to the graph? By
- default, the distributed adjacency list will throw an exception if a
- named vertex does not yet exist. However, one can customize this
- behavior by specifying a function object that constructs an instance
- of the vertex property (e.g., <tt class="docutils literal"><span class="pre">City</span></tt>) from just the name of the
- vertex. This customization occurs via the
- <tt class="docutils literal"><span class="pre">internal_vertex_constructor</span></tt> trait. For example, using the
- <tt class="docutils literal"><span class="pre">vertex_from_name</span></tt> template (provided with the Parallel BGL), we can
- state that a <tt class="docutils literal"><span class="pre">City</span></tt> can be constructed directly from the name of the
- city using its second constructor:</p>
- <pre class="literal-block">
- namespace boost { namespace graph {
- template<>
- struct internal_vertex_constructor<City>
- {
- typedef vertex_from_name<City> type;
- };
- } }
- </pre>
- <p>Now, one can add edges by vertex name freely, without worrying about
- the explicit addition of vertices. The <tt class="docutils literal"><span class="pre">mayor</span></tt> and <tt class="docutils literal"><span class="pre">population</span></tt>
- fields will have default values, but the graph structure will be
- correct.</p>
- </div>
- <div class="section" id="building-a-distributed-graph">
- <h2><a class="toc-backref" href="#id5">Building a Distributed Graph</a></h2>
- <p>Once you have determined the layout of your graph type, including the
- specific data structures and properties, it is time to construct an
- instance of the graph by adding the appropriate vertices and
- edges. Construction of distributed graphs can be slightly more
- complicated than construction of normal, non-distributed graph data
- structures, because one must account for both the distribution of the
- vertices and edges and the multiple processes executing
- concurrently. There are three main ways to construct distributed
- graphs:</p>
- <p>1. <em>Sequence constructors</em>: if your data can easily be generated by a
- pair of iterators that produce (source, target) pairs, you can use the
- sequence constructors to build the distributed graph in parallel. This
- method is often preferred when creating benchmarks, because random
- graph generators like the <a class="reference external" href="http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html">sorted_erdos_renyi_iterator</a> create the
- appropriate input sequence. Note that one must provide the same input
- iterator sequence on all processes. This method has the advantage that
- the sequential graph-building code is identical to the parallel
- graph-building code. An example constructing a random graph this way:</p>
- <blockquote>
- <pre class="literal-block">
- typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter;
- boost::minstd_rand gen;
- unsigned long n = 1000000; // 1M vertices
- Graph g(ERIter(gen, n, 0.00005), ERIter(), n);
- </pre>
- </blockquote>
- <p>2. <em>Adding edges by vertex number</em>: if you are able to map your
- vertices into values in the random [0, <em>n</em>), where <em>n</em> is the number
- of vertices in the distributed graph. Use this method rather than the
- sequence constructors when your algorithm cannot easily be moved into
- input iterators, or if you can't replicate the input sequence. For
- example, you might be reading the graph from an input file:</p>
- <blockquote>
- <pre class="literal-block">
- Graph g(n); // initialize with the total number of vertices, n
- if (process_id(g.process_group()) == 0) {
- // Only process 0 loads the graph, which is distributed automatically
- int source, target;
- for (std::cin >> source >> target)
- add_edge(vertex(source, g), vertex(target, g), g);
- }
- // All processes synchronize at this point, then the graph is complete
- synchronize(g.process_group());
- </pre>
- </blockquote>
- <p>3. <em>Adding edges by name</em>: if you are using named vertices, you can
- construct your graph just by calling <tt class="docutils literal"><span class="pre">add_edge</span></tt> with the names of
- the source and target vertices. Be careful to make sure that each edge
- is added by only one process (it doesn't matter which process it is),
- otherwise you will end up with multiple edges. For example, in the
- following program we read edges from the standard input of process 0,
- adding those edges by name. Vertices and edges will be created and
- distributed automatically.</p>
- <blockquote>
- <pre class="literal-block">
- Graph g;
- if (process_id(g.process_group()) == 0) {
- // Only process 0 loads the graph, which is distributed automatically
- std:string source, target;
- for(std::cin >> source >> target)
- add_edge(source, target, g);
- }
- // All processes synchronize at this point, then the graph is complete
- synchronize(g.process_group());
- </pre>
- </blockquote>
- </div>
- <div class="section" id="graph-concepts">
- <h2><a class="toc-backref" href="#id6">Graph Concepts</a></h2>
- <p>The distributed adjacency list models the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Graph.html">Graph</a> concept, and in
- particular the <a class="reference external" href="DistributedGraph.html">Distributed Graph</a> concept. It also models the
- <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> and <a class="reference external" href="http://www.boost.org/libs/graph/doc/AdjacencyGraph.html">Adjacency Graph</a> concept, but restricts the
- input domain of the operations to correspond to local vertices
- only. For instance, a process may only access the outgoing edges of a
- vertex if that vertex is stored in that process. Undirected and
- bidirectional distributed adjacency lists model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional
- Graph</a> concept, with the same domain restrictions. Distributed
- adjacency lists also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutableGraph.html">Mutable Graph</a> concept (with domain
- restrictions; see the <a class="reference internal" href="#reference">Reference</a> section), <a class="reference external" href="http://www.boost.org/libs/graph/doc/PropertyGraph.html">Property Graph</a> concept,
- and <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutablePropertyGraph.html">Mutable Property Graph</a> concept.</p>
- <p>Unlike its non-distributed counterpart, the distributed adjacency
- list does <strong>not</strong> model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> or <a class="reference external" href="http://www.boost.org/libs/graph/doc/EdgeListGraph.html">Edge List
- Graph</a> concepts, because one cannot enumerate all vertices or edges
- within a distributed graph. Instead, it models the weaker
- <a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List Graph</a> and <a class="reference external" href="DistributedEdgeListGraph.html">Distributed Edge List Graph</a>
- concepts, which permit access to the local edges and vertices on each
- processor. Note that if all processes within the process group over
- which the graph is distributed iterator over their respective vertex
- or edge lists, all vertices and edges will be covered once.</p>
- </div>
- </div>
- <div class="section" id="reference">
- <h1><a class="toc-backref" href="#id7">Reference</a></h1>
- <p>Since the distributed adjacency list closely follows the
- non-distributed <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>, this reference documentation
- only describes where the two implementations differ.</p>
- <div class="section" id="where-defined">
- <h2><a class="toc-backref" href="#id8">Where Defined</a></h2>
- <p><boost/graph/distributed/adjacency_list.hpp></p>
- </div>
- <div class="section" id="associated-types">
- <h2><a class="toc-backref" href="#id9">Associated Types</a></h2>
- <pre class="literal-block">
- adjacency_list::process_group_type
- </pre>
- <p>The type of the process group over which the graph will be
- distributed.</p>
- <hr class="docutils" />
- <blockquote>
- adjacency_list::distribution_type</blockquote>
- <p>The type of distribution used to partition vertices in the graph.</p>
- <hr class="docutils" />
- <blockquote>
- adjacency_list::vertex_name_type</blockquote>
- <p>If the graph supports named vertices, this is the type used to name
- vertices. Otherwise, this type is not present within the distributed
- adjacency list.</p>
- </div>
- <div class="section" id="member-functions">
- <h2><a class="toc-backref" href="#id10">Member Functions</a></h2>
- <pre class="literal-block">
- adjacency_list(const ProcessGroup& pg = ProcessGroup());
- adjacency_list(const GraphProperty& g,
- const ProcessGroup& pg = ProcessGroup());
- </pre>
- <p>Construct an empty distributed adjacency list with the given process
- group (or default) and graph property (or default).</p>
- <hr class="docutils" />
- <pre class="literal-block">
- adjacency_list(vertices_size_type n, const GraphProperty& p,
- const ProcessGroup& pg, const Distribution& distribution);
- adjacency_list(vertices_size_type n, const ProcessGroup& pg,
- const Distribution& distribution);
- adjacency_list(vertices_size_type n, const GraphProperty& p,
- const ProcessGroup& pg = ProcessGroup());
- adjacency_list(vertices_size_type n,
- const ProcessGroup& pg = ProcessGroup());
- </pre>
- <p>Construct a distributed adjacency list with <tt class="docutils literal"><span class="pre">n</span></tt> vertices,
- optionally providing the graph property, process group, or
- distribution. The <tt class="docutils literal"><span class="pre">n</span></tt> vertices will be distributed via the given
- (or default-constructed) distribution. This operation is collective,
- requiring all processes with the process group to execute it
- concurrently.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class EdgeIterator>
- adjacency_list(EdgeIterator first, EdgeIterator last,
- vertices_size_type n,
- const ProcessGroup& pg = ProcessGroup(),
- const GraphProperty& p = GraphProperty());
- template <class EdgeIterator, class EdgePropertyIterator>
- adjacency_list(EdgeIterator first, EdgeIterator last,
- EdgePropertyIterator ep_iter,
- vertices_size_type n,
- const ProcessGroup& pg = ProcessGroup(),
- const GraphProperty& p = GraphProperty());
- template <class EdgeIterator>
- adjacency_list(EdgeIterator first, EdgeIterator last,
- vertices_size_type n,
- const ProcessGroup& process_group,
- const Distribution& distribution,
- const GraphProperty& p = GraphProperty());
- template <class EdgeIterator, class EdgePropertyIterator>
- adjacency_list(EdgeIterator first, EdgeIterator last,
- EdgePropertyIterator ep_iter,
- vertices_size_type n,
- const ProcessGroup& process_group,
- const Distribution& distribution,
- const GraphProperty& p = GraphProperty());
- </pre>
- <p>Construct a distributed adjacency list with <tt class="docutils literal"><span class="pre">n</span></tt> vertices and with
- edges specified in the edge list given by the range <tt class="docutils literal"><span class="pre">[first,</span> <span class="pre">last)</span></tt>. The
- <tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> must be a model of <a class="reference external" href="http://www.boost.org/doc/html/InputIterator.html">InputIterator</a>. The value type of the
- <tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> must be a <tt class="docutils literal"><span class="pre">std::pair</span></tt>, where the type in the pair is an
- integer type. The integers will correspond to vertices, and they must
- all fall in the range of <tt class="docutils literal"><span class="pre">[0,</span> <span class="pre">n)</span></tt>. When provided, <tt class="docutils literal"><span class="pre">ep_iter</span></tt>
- refers to an edge property list <tt class="docutils literal"><span class="pre">[ep_iter,</span> <span class="pre">ep_iter</span> <span class="pre">+</span> <span class="pre">m)</span></tt> contains
- properties for each of the edges.</p>
- <p>This constructor is a collective operation and must be executed
- concurrently by each process with the same argument list. Most
- importantly, the edge lists provided to the constructor in each process
- should be equivalent. The vertices will be partitioned among the
- processes according to the <tt class="docutils literal"><span class="pre">distribution</span></tt>, with edges placed on the
- process owning the source of the edge. Note that this behavior
- permits sequential graph construction code to be parallelized
- automatically, regardless of the underlying distribution.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void clear()
- </pre>
- <p>Removes all of the edges and vertices from the local graph. To
- eliminate all vertices and edges from the graph, this routine must be
- executed in all processes.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- process_group_type& process_group();
- const process_group_type& process_group() const;
- </pre>
- <p>Returns the process group over which this graph is distributed.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- distribution_type& distribution();
- const distribution_type& distribution() const;
- </pre>
- <p>Returns the distribution used for initial placement of vertices.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template<typename VertexProcessorMap>
- void redistribute(VertexProcessorMap vertex_to_processor);
- </pre>
- <p>Redistributes the vertices (and, therefore, the edges) of the
- graph. The property map <tt class="docutils literal"><span class="pre">vertex_to_processor</span></tt> provides, for each
- vertex, the process identifier indicating where the vertex should be
- moved. Once this collective routine has completed, the distributed
- graph will reflect the new distribution. All vertex and edge
- descsriptors and internal and external property maps are invalidated
- by this operation.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template<typename OStreamConstructibleArchive>
- void save(std::string const& filename) const;
- template<typename IStreamConstructibleArchive>
- void load(std::string const& filename);
- </pre>
- <p>Serializes the graph to a Boost.Serialization archive.
- <tt class="docutils literal"><span class="pre">OStreamConstructibleArchive</span></tt> and <tt class="docutils literal"><span class="pre">IStreamConstructibleArchive</span></tt>
- are models of Boost.Serialization <em>Archive</em> with the extra
- requirement that they can be constructed from a <tt class="docutils literal"><span class="pre">std::ostream</span></tt>
- and <tt class="docutils literal"><span class="pre">std::istream</span></tt>.
- <tt class="docutils literal"><span class="pre">filename</span></tt> names a directory that will hold files for
- the different processes.</p>
- </div>
- <div class="section" id="non-member-functions">
- <h2><a class="toc-backref" href="#id11">Non-Member Functions</a></h2>
- <pre class="literal-block">
- std::pair<vertex_iterator, vertex_iterator>
- vertices(const adjacency_list& g);
- </pre>
- <p>Returns an iterator-range providing access to the vertex set of graph
- <tt class="docutils literal"><span class="pre">g</span></tt> stored in this process. Each of the processes that contain <tt class="docutils literal"><span class="pre">g</span></tt>
- will get disjoint sets of vertices.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::pair<edge_iterator, edge_iterator>
- edges(const adjacency_list& g);
- </pre>
- <p>Returns an iterator-range providing access to the edge set of graph
- <tt class="docutils literal"><span class="pre">g</span></tt> stored in this process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::pair<adjacency_iterator, adjacency_iterator>
- adjacent_vertices(vertex_descriptor u, const adjacency_list& g);
- </pre>
- <p>Returns an iterator-range providing access to the vertices adjacent to
- vertex <tt class="docutils literal"><span class="pre">u</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to this process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::pair<out_edge_iterator, out_edge_iterator>
- out_edges(vertex_descriptor u, const adjacency_list& g);
- </pre>
- <p>Returns an iterator-range providing access to the out-edges of vertex
- <tt class="docutils literal"><span class="pre">u</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. If the graph is undirected, this iterator-range
- provides access to all edges incident on vertex <tt class="docutils literal"><span class="pre">u</span></tt>. For both
- directed and undirected graphs, for an out-edge <tt class="docutils literal"><span class="pre">e</span></tt>, <tt class="docutils literal"><span class="pre">source(e,</span> <span class="pre">g)</span>
- <span class="pre">==</span> <span class="pre">u</span></tt> and <tt class="docutils literal"><span class="pre">target(e,</span> <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">v</span></tt> where <tt class="docutils literal"><span class="pre">v</span></tt> is a vertex adjacent to
- <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to this process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::pair<in_edge_iterator, in_edge_iterator>
- in_edges(vertex_descriptor v, const adjacency_list& g);
- </pre>
- <p>Returns an iterator-range providing access to the in-edges of vertex
- <tt class="docutils literal"><span class="pre">v</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. This operation is only available if
- <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> was specified for the <tt class="docutils literal"><span class="pre">Directed</span></tt> template
- parameter. For an in-edge <tt class="docutils literal"><span class="pre">e</span></tt>, <tt class="docutils literal"><span class="pre">target(e,</span> <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">v</span></tt> and <tt class="docutils literal"><span class="pre">source(e,</span>
- <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">u</span></tt> for some vertex <tt class="docutils literal"><span class="pre">u</span></tt> that is adjacent to <tt class="docutils literal"><span class="pre">v</span></tt>, whether the
- graph is directed or undirected. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local to
- this process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- degree_size_type
- out_degree(vertex_descriptor u, const adjacency_list& g);
- </pre>
- <p>Returns the number of edges leaving vertex <tt class="docutils literal"><span class="pre">u</span></tt>. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must
- be local to the executing process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- degree_size_type
- in_degree(vertex_descriptor u, const adjacency_list& g);
- </pre>
- <p>Returns the number of edges entering vertex <tt class="docutils literal"><span class="pre">u</span></tt>. This operation is
- only available if <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> was specified for the
- <tt class="docutils literal"><span class="pre">Directed</span></tt> template parameter. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to the
- executing process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- vertices_size_type
- num_vertices(const adjacency_list& g);
- </pre>
- <p>Returns the number of vertices in the graph <tt class="docutils literal"><span class="pre">g</span></tt> that are stored in
- the executing process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- edges_size_type
- num_edges(const adjacency_list& g);
- </pre>
- <p>Returns the number of edges in the graph <tt class="docutils literal"><span class="pre">g</span></tt> that are stored in the
- executing process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- vertex_descriptor
- vertex(vertices_size_type n, const adjacency_list& g);
- </pre>
- <p>Returns the <tt class="docutils literal"><span class="pre">n``th</span> <span class="pre">vertex</span> <span class="pre">in</span> <span class="pre">the</span> <span class="pre">graph's</span> <span class="pre">vertex</span> <span class="pre">list,</span> <span class="pre">according</span> <span class="pre">to</span> <span class="pre">the</span>
- <span class="pre">distribution</span> <span class="pre">used</span> <span class="pre">to</span> <span class="pre">partition</span> <span class="pre">the</span> <span class="pre">graph.</span> <span class="pre">``n</span></tt> must be a value
- between zero and the sum of <tt class="docutils literal"><span class="pre">num_vertices(g)</span></tt> in each process (minus
- one). Note that it is not necessarily the case that <tt class="docutils literal"><span class="pre">vertex(0,</span> <span class="pre">g)</span> <span class="pre">==</span>
- <span class="pre">*num_vertices(g).first</span></tt>. This function is only guaranteed to be
- accurate when no vertices have been added to or removed from the
- graph after its initial construction.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::pair<edge_descriptor, bool>
- edge(vertex_descriptor u, vertex_descriptor v,
- const adjacency_list& g);
- </pre>
- <p>Returns an edge connecting vertex <tt class="docutils literal"><span class="pre">u</span></tt> to vertex <tt class="docutils literal"><span class="pre">v</span></tt> in graph
- <tt class="docutils literal"><span class="pre">g</span></tt>. For bidirectional and undirected graphs, either vertex <tt class="docutils literal"><span class="pre">u</span></tt> or
- vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local; for directed graphs, vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be
- local.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- std::pair<out_edge_iterator, out_edge_iterator>
- edge_range(vertex_descriptor u, vertex_descriptor v,
- const adjacency_list& g);
- </pre>
- <p>TODO: Not implemented. Returns a pair of out-edge iterators that give
- the range for all the parallel edges from <tt class="docutils literal"><span class="pre">u</span></tt> to <tt class="docutils literal"><span class="pre">v</span></tt>. This function only
- works when the <tt class="docutils literal"><span class="pre">OutEdgeList</span></tt> for the <tt class="docutils literal"><span class="pre">adjacency_list</span></tt> is a container that
- sorts the out edges according to target vertex, and allows for
- parallel edges. The <tt class="docutils literal"><span class="pre">multisetS</span></tt> selector chooses such a
- container. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be stored in the executing process.</p>
- </div>
- <div class="section" id="structure-modification">
- <h2><a class="toc-backref" href="#id12">Structure Modification</a></h2>
- <pre class="literal-block">
- unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g);
- unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g);
- unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g);
- unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list& g);
- </pre>
- <p>Adds edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> to the graph. The return type itself is
- unspecified, but the type can be copy-constructed and implicitly
- converted into a <tt class="docutils literal"><span class="pre">std::pair<edge_descriptor,bool></span></tt>. The edge
- descriptor describes the added (or found) edge. For graphs that do not
- allow parallel edges, if the edge
- is already in the graph then a duplicate will not be added and the
- <tt class="docutils literal"><span class="pre">bool</span></tt> flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. Also, if u and v are descriptors for
- the same vertex (creating a self loop) and the graph is undirected,
- then the edge will not be added and the flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. When
- the flag is <tt class="docutils literal"><span class="pre">false</span></tt>, the returned edge descriptor points to the
- already existing edge.</p>
- <p>The parameters <tt class="docutils literal"><span class="pre">u</span></tt> and <tt class="docutils literal"><span class="pre">v</span></tt> can be either vertex descriptors or, if
- the graph uses named vertices, the names of vertices. If no vertex
- with the given name exists, the internal vertex constructor will be
- invoked to create a new vertex property and a vertex with that
- property will be added to the graph implicitly. The default internal
- vertex constructor throws an exception.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
- unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
- unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
- unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
- </pre>
- <p>Adds edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> to the graph and attaches <tt class="docutils literal"><span class="pre">p</span></tt> as the value of the edge's
- internal property storage. See the previous <tt class="docutils literal"><span class="pre">add_edge()</span></tt> member
- function for more details.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void
- remove_edge(vertex_descriptor u, vertex_descriptor v,
- adjacency_list& g);
- </pre>
- <p>Removes the edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> from the graph. If the directed selector is
- <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> or <tt class="docutils literal"><span class="pre">undirectedS</span></tt>, either the source or target
- vertex of the graph must be local. If the directed selector is
- <tt class="docutils literal"><span class="pre">directedS</span></tt>, then the source vertex must be local.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void
- remove_edge(edge_descriptor e, adjacency_list& g);
- </pre>
- <p>Removes the edge <tt class="docutils literal"><span class="pre">e</span></tt> from the graph. If the directed selector is
- <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> or <tt class="docutils literal"><span class="pre">undirectedS</span></tt>, either the source or target
- vertex of the graph must be local. If the directed selector is
- <tt class="docutils literal"><span class="pre">directedS</span></tt>, then the source vertex must be local.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void remove_edge(out_edge_iterator iter, adjacency_list& g);
- </pre>
- <p>This has the same effect as <tt class="docutils literal"><span class="pre">remove_edge(*iter,</span> <span class="pre">g)</span></tt>. For directed
- (but not bidirectional) graphs, this will be more efficient than
- <tt class="docutils literal"><span class="pre">remove_edge(*iter,</span> <span class="pre">g)</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class Predicate >
- void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
- adjacency_list& g);
- </pre>
- <p>Removes all out-edges of vertex <tt class="docutils literal"><span class="pre">u</span></tt> from the graph that satisfy the
- predicate. That is, if the predicate returns <tt class="docutils literal"><span class="pre">true</span></tt> when applied to an
- edge descriptor, then the edge is removed. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local.</p>
- <p>The affect on descriptor and iterator stability is the same as that of
- invoking remove_edge() on each of the removed edges.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class Predicate >
- void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
- adjacency_list& g);
- </pre>
- <p>Removes all in-edges of vertex <tt class="docutils literal"><span class="pre">v</span></tt> from the graph that satisfy the
- predicate. That is, if the predicate returns true when applied to an
- edge descriptor, then the edge is removed. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local.</p>
- <p>The affect on descriptor and iterator stability is the same as that of
- invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> on each of the removed edges.</p>
- <p>This operation is available for undirected and bidirectional
- adjacency_list graphs, but not for directed.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class Predicate>
- void remove_edge_if(Predicate predicate, adjacency_list& g);
- </pre>
- <p>Removes all edges from the graph that satisfy the predicate. That is,
- if the predicate returns true when applied to an edge descriptor, then
- the edge is removed.</p>
- <p>The affect on descriptor and iterator stability is the same as that
- of invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> on each of the removed edges.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- vertex_descriptor add_vertex(adjacency_list& g);
- </pre>
- <p>Adds a vertex to the graph and returns the vertex descriptor for the
- new vertex. The vertex will be stored in the local process. This
- function is not available when using named vertices.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- unspecified add_vertex(const VertexProperties& p, adjacency_list& g);
- unspecified add_vertex(const vertex_name_type& p, adjacency_list& g);
- </pre>
- <p>Adds a vertex to the graph with the specified properties. If the graph
- is using vertex names, the vertex will be added on whichever process
- "owns" that name. Otherwise, the vertex will be stored in the local
- process. Note that the second constructor will invoke the
- user-customizable internal vertex constructor, which (by default)
- throws an exception when it sees an unknown vertex.</p>
- <p>The return type is of unspecified type, but can be copy-constructed
- and can be implicitly converted into a vertex descriptor.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void clear_vertex(vertex_descriptor u, adjacency_list& g);
- </pre>
- <p>Removes all edges to and from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears
- in the vertex set of the graph.</p>
- <p>The affect on descriptor and iterator stability is the same as that of
- invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the source
- or target.</p>
- <p>This operation is not applicable to directed graphs, because the
- incoming edges to vertex <tt class="docutils literal"><span class="pre">u</span></tt> are not known.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void clear_out_edges(vertex_descriptor u, adjacency_list& g);
- </pre>
- <p>Removes all out-edges from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears in
- the vertex set of the graph.</p>
- <p>The affect on descriptor and iterator stability is the same as that of
- invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the
- source.</p>
- <p>This operation is not applicable to undirected graphs (use
- <tt class="docutils literal"><span class="pre">clear_vertex()</span></tt> instead).</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void clear_in_edges(vertex_descriptor u, adjacency_list& g);
- </pre>
- <p>Removes all in-edges from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears in
- the vertex set of the graph.</p>
- <p>The affect on descriptor and iterator stability is the same as that of
- invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the
- target.</p>
- <p>This operation is only applicable to bidirectional graphs.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void remove_vertex(vertex_descriptor u, adjacency_list& g);
- </pre>
- <p>Remove vertex <tt class="docutils literal"><span class="pre">u</span></tt> from the vertex set of the graph. It is assumed
- that there are no edges to or from vertex <tt class="docutils literal"><span class="pre">u</span></tt> when it is
- removed. One way to make sure of this is to invoke <tt class="docutils literal"><span class="pre">clear_vertex()</span></tt>
- beforehand. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be stored locally.</p>
- </div>
- <div class="section" id="property-map-accessors">
- <h2><a class="toc-backref" href="#id13">Property Map Accessors</a></h2>
- <pre class="literal-block">
- template <class PropertyTag>
- property_map<adjacency_list, PropertyTag>::type
- get(PropertyTag, adjacency_list& g);
- template <class PropertyTag>
- property_map<adjacency_list, Tag>::const_type
- get(PropertyTag, const adjacency_list& g);
- </pre>
- <p>Returns the property map object for the vertex property specified by
- <tt class="docutils literal"><span class="pre">PropertyTag</span></tt>. The <tt class="docutils literal"><span class="pre">PropertyTag</span></tt> must match one of the properties
- specified in the graph's <tt class="docutils literal"><span class="pre">VertexProperty</span></tt> template argument. The
- returned property map will be a <a class="reference external" href="distributed_property_map.html">distributed property map</a>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class PropertyTag , class X>
- typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
- get(PropertyTag, const adjacency_list& g, X x);
- </pre>
- <p>This returns the property value for <tt class="docutils literal"><span class="pre">x</span></tt>, where <tt class="docutils literal"><span class="pre">x</span></tt> is either a vertex or
- edge descriptor. The entity referred to by descriptor <tt class="docutils literal"><span class="pre">x</span></tt> must be
- stored in the local process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class PropertyTag , class X, class Value>
- void put(PropertyTag, const adjacency_list& g, X x, const Value& value);
- </pre>
- <p>This sets the property value for <tt class="docutils literal"><span class="pre">x</span></tt> to value. <tt class="docutils literal"><span class="pre">x</span></tt> is either a
- vertex or edge descriptor. <tt class="docutils literal"><span class="pre">Value</span></tt> must be convertible to <tt class="docutils literal"><span class="pre">typename</span>
- <span class="pre">property_traits<property_map<adjacency_list,</span>
- <span class="pre">PropertyTag>::type>::value_type</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template <class GraphProperties, class GraphPropertyTag>
- typename graph_property<adjacency_list, GraphPropertyTag>::type&
- get_property(adjacency_list& g, GraphPropertyTag);
- template <class GraphProperties, class GraphPropertyTag >
- const typename graph_property<adjacency_list, GraphPropertyTag>::type&
- get_property(const adjacency_list& g, GraphPropertyTag);
- </pre>
- <p>TODO: not implemented.</p>
- <p>Return the property specified by <tt class="docutils literal"><span class="pre">GraphPropertyTag</span></tt> that is attached
- to the graph object <tt class="docutils literal"><span class="pre">g</span></tt>. The <tt class="docutils literal"><span class="pre">graph_property</span></tt> traits class is
- defined in <tt class="docutils literal"><span class="pre">boost/graph/adjacency_list.hpp</span></tt>.</p>
- <hr class="docutils" />
- <p>Copyright (C) 2004 The Trustees of Indiana University.</p>
- <p>Copyright (C) 2007 Douglas Gregor</p>
- <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
- </div>
- </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>
|