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)
6 =================================
7 |Logo| Distributed Adjacency List
8 =================================
15 The distributed adjacency list implements a graph data structure using
16 an adjacency list representation. Its interface and behavior are
17 roughly equivalent to the Boost Graph Library's adjacency_list_
18 class template. However, the distributed adjacency list partitions the
19 vertices of the graph across several processes (which need not share
20 an address space). Edges outgoing from any vertex stored by a process
21 are also stored on that process, except in the case of undirected
22 graphs, where either the source or the target may store the edge.
26 template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS,
27 typename DirectedS, typename VertexProperty, typename EdgeProperty,
28 typename GraphProperty, typename EdgeListS>
29 class adjacency_list<OutEdgeListS,
30 distributedS<ProcessGroup, VertexListS>,
31 DirectedS, VertexProperty,
32 EdgeProperty, GraphProperty, EdgeListS>;
34 Defining a Distributed Adjacency List
35 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
36 To create a distributed adjacency list, first determine the
37 representation of the graph in a single address space using these
38 guidelines_. Next, replace the vertex list selector (``VertexListS``)
39 with an instantiation of distributedS_, which includes:
41 - Selecting a `process group`_ type that represents the various
42 coordinating processes that will store the distributed graph. For
43 example, the `MPI process group`_.
45 - A selector indicating how the vertex lists in each process will be
46 stored. Only the ``vecS`` and ``listS`` selectors are well-supported
50 The following ``typedef`` defines a distributed adjacency list
51 containing directed edges. The vertices in the graph will be
52 distributed over several processes, using the MPI process group
53 for communication. In each process, the vertices and outgoing edges
54 will be stored in STL vectors. There are no properties attached to the
55 vertices or edges of the graph.
59 using namespace boost;
60 typedef adjacency_list<vecS,
61 distributedS<parallel::mpi::bsp_process_group, vecS>,
66 Distributed Vertex and Edge Properties
67 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
68 Vertex and edge properties for distributed graphs mirror their
69 counterparts for non-distributed graphs. With a distributed graph,
70 however, vertex and edge properties are stored only in the process
71 that owns the vertex or edge.
73 The most direct way to attach properties to a distributed graph is to
74 create a structure that will be attached to each of the vertices and
75 edges of the graph. For example, if we wish to model a simplistic map
76 of the United States interstate highway system, we might state that
77 the vertices of the graph are cities and the edges are highways, then
78 define the information that we maintain for each city and highway:
84 City(const std::string& name, const std::string& mayor = "Unknown", int population = 0)
85 : name(name), mayor(mayor), population(population) { }
91 // Serialization support is required!
92 template<typename Archiver>
93 void serialize(Archiver& ar, const unsigned int /*version*/) {
94 ar & name & mayor & population;
100 Highway(const std::string& name, int lanes, int miles_per_hour, int length)
101 : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { }
108 // Serialization support is required!
109 template<typename Archiver>
110 void serialize(Archiver& ar, const unsigned int /*version*/) {
111 ar & name & lanes & miles_per_hour & length;
116 To create a distributed graph for a road map, we supply ``City`` and
117 ``Highway`` as the fourth and fifth parameters to ``adjacency_list``,
122 typedef adjacency_list<vecS,
123 distributedS<parallel::mpi::bsp_process_group, vecS>,
129 Property maps for internal properties retain their behavior with
130 distributed graphs via `distributed property maps`_, which automate
131 communication among processes so that ``put`` and ``get`` operations
132 may be applied to non-local vertices and edges. However, for
133 distributed adjacency lists that store vertices in a vector
134 (``VertexListS`` is ``vecS``), the automatic ``vertex_index``
135 property map restricts the domain of ``put`` and ``get`` operations
136 to vertices local to the process executing the operation. For example,
137 we can create a property map that accesses the length of each highway
142 RoadMap map; // distributed graph instance
144 typedef property_map<RoadMap, int Highway::*>::type
145 road_length = get(&Highway::length, map);
148 Now, one can access the length of any given road based on its edge
149 descriptor ``e`` with the expression ``get(road_length, e)``,
150 regardless of which process stores the edge ``e``.
155 The vertices of a graph typically correspond to named entities within
156 the application domain. In the road map example from the previous
157 section, the vertices in the graph represent cities. The distributed
158 adjacency list supports named vertices, which provides an implicit
159 mapping from the names of the vertices in the application domain
160 (e.g., the name of a city, such as "Bloomington") to the actual vertex
161 descriptor stored within the distributed graph (e.g., the third vertex
162 on processor 1). By enabling support for named vertices, one can refer
163 to vertices by name when manipulating the graph. For example, one can
164 add a highway from Indianapolis to Chicago:
168 add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map);
170 The distributed adjacency list will find vertices associated with the
171 names "Indianapolis" and "Chicago", then add an edge between these
172 vertices that represents I-65. The vertices may be stored on any
173 processor, local or remote.
175 To enable named vertices, specialize the ``internal_vertex_name``
176 property for the structure attached to the vertices in your
177 graph. ``internal_vertex_name`` contains a single member, ``type``,
178 which is the type of a function object that accepts a vertex property
179 and returns the name stored within that vertex property. In the case
180 of our road map, the ``name`` field contains the name of each city, so
181 we use the ``member`` function object from the `Boost.MultiIndex`_
182 library to extract the name, e.g.,
186 namespace boost { namespace graph {
189 struct internal_vertex_name<City>
191 typedef multi_index::member<City, std::string, &City::name> type;
197 That's it! One can now refer to vertices by name when interacting with
198 the distributed adjacency list.
200 What happens when one uses the name of a vertex that does not exist?
201 For example, in our ``add_edge`` call above, what happens if the
202 vertex named "Indianapolis" has not yet been added to the graph? By
203 default, the distributed adjacency list will throw an exception if a
204 named vertex does not yet exist. However, one can customize this
205 behavior by specifying a function object that constructs an instance
206 of the vertex property (e.g., ``City``) from just the name of the
207 vertex. This customization occurs via the
208 ``internal_vertex_constructor`` trait. For example, using the
209 ``vertex_from_name`` template (provided with the Parallel BGL), we can
210 state that a ``City`` can be constructed directly from the name of the
211 city using its second constructor:
215 namespace boost { namespace graph {
218 struct internal_vertex_constructor<City>
220 typedef vertex_from_name<City> type;
225 Now, one can add edges by vertex name freely, without worrying about
226 the explicit addition of vertices. The ``mayor`` and ``population``
227 fields will have default values, but the graph structure will be
230 Building a Distributed Graph
231 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
233 Once you have determined the layout of your graph type, including the
234 specific data structures and properties, it is time to construct an
235 instance of the graph by adding the appropriate vertices and
236 edges. Construction of distributed graphs can be slightly more
237 complicated than construction of normal, non-distributed graph data
238 structures, because one must account for both the distribution of the
239 vertices and edges and the multiple processes executing
240 concurrently. There are three main ways to construct distributed
243 1. *Sequence constructors*: if your data can easily be generated by a
244 pair of iterators that produce (source, target) pairs, you can use the
245 sequence constructors to build the distributed graph in parallel. This
246 method is often preferred when creating benchmarks, because random
247 graph generators like the sorted_erdos_renyi_iterator_ create the
248 appropriate input sequence. Note that one must provide the same input
249 iterator sequence on all processes. This method has the advantage that
250 the sequential graph-building code is identical to the parallel
251 graph-building code. An example constructing a random graph this way:
255 typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter;
256 boost::minstd_rand gen;
257 unsigned long n = 1000000; // 1M vertices
258 Graph g(ERIter(gen, n, 0.00005), ERIter(), n);
260 2. *Adding edges by vertex number*: if you are able to map your
261 vertices into values in the random [0, *n*), where *n* is the number
262 of vertices in the distributed graph. Use this method rather than the
263 sequence constructors when your algorithm cannot easily be moved into
264 input iterators, or if you can't replicate the input sequence. For
265 example, you might be reading the graph from an input file:
269 Graph g(n); // initialize with the total number of vertices, n
270 if (process_id(g.process_group()) == 0) {
271 // Only process 0 loads the graph, which is distributed automatically
273 for (std::cin >> source >> target)
274 add_edge(vertex(source, g), vertex(target, g), g);
277 // All processes synchronize at this point, then the graph is complete
278 synchronize(g.process_group());
280 3. *Adding edges by name*: if you are using named vertices, you can
281 construct your graph just by calling ``add_edge`` with the names of
282 the source and target vertices. Be careful to make sure that each edge
283 is added by only one process (it doesn't matter which process it is),
284 otherwise you will end up with multiple edges. For example, in the
285 following program we read edges from the standard input of process 0,
286 adding those edges by name. Vertices and edges will be created and
287 distributed automatically.
292 if (process_id(g.process_group()) == 0) {
293 // Only process 0 loads the graph, which is distributed automatically
294 std:string source, target;
295 for(std::cin >> source >> target)
296 add_edge(source, target, g);
299 // All processes synchronize at this point, then the graph is complete
300 synchronize(g.process_group());
306 The distributed adjacency list models the Graph_ concept, and in
307 particular the `Distributed Graph`_ concept. It also models the
308 `Incidence Graph`_ and `Adjacency Graph`_ concept, but restricts the
309 input domain of the operations to correspond to local vertices
310 only. For instance, a process may only access the outgoing edges of a
311 vertex if that vertex is stored in that process. Undirected and
312 bidirectional distributed adjacency lists model the `Bidirectional
313 Graph`_ concept, with the same domain restrictions. Distributed
314 adjacency lists also model the `Mutable Graph`_ concept (with domain
315 restrictions; see the Reference_ section), `Property Graph`_ concept,
316 and `Mutable Property Graph`_ concept.
318 Unlike its non-distributed counterpart, the distributed adjacency
319 list does **not** model the `Vertex List Graph`_ or `Edge List
320 Graph`_ concepts, because one cannot enumerate all vertices or edges
321 within a distributed graph. Instead, it models the weaker
322 `Distributed Vertex List Graph`_ and `Distributed Edge List Graph`_
323 concepts, which permit access to the local edges and vertices on each
324 processor. Note that if all processes within the process group over
325 which the graph is distributed iterator over their respective vertex
326 or edge lists, all vertices and edges will be covered once.
330 Since the distributed adjacency list closely follows the
331 non-distributed adjacency_list_, this reference documentation
332 only describes where the two implementations differ.
337 <boost/graph/distributed/adjacency_list.hpp>
344 adjacency_list::process_group_type
346 The type of the process group over which the graph will be
349 -----------------------------------------------------------------------------
351 adjacency_list::distribution_type
353 The type of distribution used to partition vertices in the graph.
355 -----------------------------------------------------------------------------
357 adjacency_list::vertex_name_type
359 If the graph supports named vertices, this is the type used to name
360 vertices. Otherwise, this type is not present within the distributed
369 adjacency_list(const ProcessGroup& pg = ProcessGroup());
371 adjacency_list(const GraphProperty& g,
372 const ProcessGroup& pg = ProcessGroup());
374 Construct an empty distributed adjacency list with the given process
375 group (or default) and graph property (or default).
377 -----------------------------------------------------------------------------
381 adjacency_list(vertices_size_type n, const GraphProperty& p,
382 const ProcessGroup& pg, const Distribution& distribution);
384 adjacency_list(vertices_size_type n, const ProcessGroup& pg,
385 const Distribution& distribution);
387 adjacency_list(vertices_size_type n, const GraphProperty& p,
388 const ProcessGroup& pg = ProcessGroup());
390 adjacency_list(vertices_size_type n,
391 const ProcessGroup& pg = ProcessGroup());
393 Construct a distributed adjacency list with ``n`` vertices,
394 optionally providing the graph property, process group, or
395 distribution. The ``n`` vertices will be distributed via the given
396 (or default-constructed) distribution. This operation is collective,
397 requiring all processes with the process group to execute it
400 -----------------------------------------------------------------------------
404 template <class EdgeIterator>
405 adjacency_list(EdgeIterator first, EdgeIterator last,
406 vertices_size_type n,
407 const ProcessGroup& pg = ProcessGroup(),
408 const GraphProperty& p = GraphProperty());
410 template <class EdgeIterator, class EdgePropertyIterator>
411 adjacency_list(EdgeIterator first, EdgeIterator last,
412 EdgePropertyIterator ep_iter,
413 vertices_size_type n,
414 const ProcessGroup& pg = ProcessGroup(),
415 const GraphProperty& p = GraphProperty());
417 template <class EdgeIterator>
418 adjacency_list(EdgeIterator first, EdgeIterator last,
419 vertices_size_type n,
420 const ProcessGroup& process_group,
421 const Distribution& distribution,
422 const GraphProperty& p = GraphProperty());
424 template <class EdgeIterator, class EdgePropertyIterator>
425 adjacency_list(EdgeIterator first, EdgeIterator last,
426 EdgePropertyIterator ep_iter,
427 vertices_size_type n,
428 const ProcessGroup& process_group,
429 const Distribution& distribution,
430 const GraphProperty& p = GraphProperty());
432 Construct a distributed adjacency list with ``n`` vertices and with
433 edges specified in the edge list given by the range ``[first, last)``. The
434 ``EdgeIterator`` must be a model of InputIterator_. The value type of the
435 ``EdgeIterator`` must be a ``std::pair``, where the type in the pair is an
436 integer type. The integers will correspond to vertices, and they must
437 all fall in the range of ``[0, n)``. When provided, ``ep_iter``
438 refers to an edge property list ``[ep_iter, ep_iter + m)`` contains
439 properties for each of the edges.
441 This constructor is a collective operation and must be executed
442 concurrently by each process with the same argument list. Most
443 importantly, the edge lists provided to the constructor in each process
444 should be equivalent. The vertices will be partitioned among the
445 processes according to the ``distribution``, with edges placed on the
446 process owning the source of the edge. Note that this behavior
447 permits sequential graph construction code to be parallelized
448 automatically, regardless of the underlying distribution.
450 -----------------------------------------------------------------------------
456 Removes all of the edges and vertices from the local graph. To
457 eliminate all vertices and edges from the graph, this routine must be
458 executed in all processes.
460 -----------------------------------------------------------------------------
464 process_group_type& process_group();
465 const process_group_type& process_group() const;
467 Returns the process group over which this graph is distributed.
469 -----------------------------------------------------------------------------
473 distribution_type& distribution();
474 const distribution_type& distribution() const;
476 Returns the distribution used for initial placement of vertices.
478 -----------------------------------------------------------------------------
482 template<typename VertexProcessorMap>
483 void redistribute(VertexProcessorMap vertex_to_processor);
485 Redistributes the vertices (and, therefore, the edges) of the
486 graph. The property map ``vertex_to_processor`` provides, for each
487 vertex, the process identifier indicating where the vertex should be
488 moved. Once this collective routine has completed, the distributed
489 graph will reflect the new distribution. All vertex and edge
490 descsriptors and internal and external property maps are invalidated
493 -----------------------------------------------------------------------------
497 template<typename OStreamConstructibleArchive>
498 void save(std::string const& filename) const;
500 template<typename IStreamConstructibleArchive>
501 void load(std::string const& filename);
503 Serializes the graph to a Boost.Serialization archive.
504 ``OStreamConstructibleArchive`` and ``IStreamConstructibleArchive``
505 are models of Boost.Serialization *Archive* with the extra
506 requirement that they can be constructed from a ``std::ostream``
507 and ``std::istream``.
508 ``filename`` names a directory that will hold files for
509 the different processes.
517 std::pair<vertex_iterator, vertex_iterator>
518 vertices(const adjacency_list& g);
520 Returns an iterator-range providing access to the vertex set of graph
521 ``g`` stored in this process. Each of the processes that contain ``g``
522 will get disjoint sets of vertices.
524 -----------------------------------------------------------------------------
528 std::pair<edge_iterator, edge_iterator>
529 edges(const adjacency_list& g);
531 Returns an iterator-range providing access to the edge set of graph
532 ``g`` stored in this process.
534 -----------------------------------------------------------------------------
538 std::pair<adjacency_iterator, adjacency_iterator>
539 adjacent_vertices(vertex_descriptor u, const adjacency_list& g);
541 Returns an iterator-range providing access to the vertices adjacent to
542 vertex ``u`` in graph ``g``. The vertex ``u`` must be local to this process.
544 -----------------------------------------------------------------------------
548 std::pair<out_edge_iterator, out_edge_iterator>
549 out_edges(vertex_descriptor u, const adjacency_list& g);
551 Returns an iterator-range providing access to the out-edges of vertex
552 ``u`` in graph ``g``. If the graph is undirected, this iterator-range
553 provides access to all edges incident on vertex ``u``. For both
554 directed and undirected graphs, for an out-edge ``e``, ``source(e, g)
555 == u`` and ``target(e, g) == v`` where ``v`` is a vertex adjacent to
556 ``u``. The vertex ``u`` must be local to this process.
558 -----------------------------------------------------------------------------
562 std::pair<in_edge_iterator, in_edge_iterator>
563 in_edges(vertex_descriptor v, const adjacency_list& g);
565 Returns an iterator-range providing access to the in-edges of vertex
566 ``v`` in graph ``g``. This operation is only available if
567 ``bidirectionalS`` was specified for the ``Directed`` template
568 parameter. For an in-edge ``e``, ``target(e, g) == v`` and ``source(e,
569 g) == u`` for some vertex ``u`` that is adjacent to ``v``, whether the
570 graph is directed or undirected. The vertex ``v`` must be local to
573 -----------------------------------------------------------------------------
578 out_degree(vertex_descriptor u, const adjacency_list& g);
580 Returns the number of edges leaving vertex ``u``. Vertex ``u`` must
581 be local to the executing process.
583 -----------------------------------------------------------------------------
588 in_degree(vertex_descriptor u, const adjacency_list& g);
590 Returns the number of edges entering vertex ``u``. This operation is
591 only available if ``bidirectionalS`` was specified for the
592 ``Directed`` template parameter. Vertex ``u`` must be local to the
595 -----------------------------------------------------------------------------
600 num_vertices(const adjacency_list& g);
602 Returns the number of vertices in the graph ``g`` that are stored in
603 the executing process.
605 -----------------------------------------------------------------------------
610 num_edges(const adjacency_list& g);
612 Returns the number of edges in the graph ``g`` that are stored in the
615 -----------------------------------------------------------------------------
620 vertex(vertices_size_type n, const adjacency_list& g);
622 Returns the ``n``th vertex in the graph's vertex list, according to the
623 distribution used to partition the graph. ``n`` must be a value
624 between zero and the sum of ``num_vertices(g)`` in each process (minus
625 one). Note that it is not necessarily the case that ``vertex(0, g) ==
626 *num_vertices(g).first``. This function is only guaranteed to be
627 accurate when no vertices have been added to or removed from the
628 graph after its initial construction.
630 -----------------------------------------------------------------------------
634 std::pair<edge_descriptor, bool>
635 edge(vertex_descriptor u, vertex_descriptor v,
636 const adjacency_list& g);
638 Returns an edge connecting vertex ``u`` to vertex ``v`` in graph
639 ``g``. For bidirectional and undirected graphs, either vertex ``u`` or
640 vertex ``v`` must be local; for directed graphs, vertex ``u`` must be
643 -----------------------------------------------------------------------------
647 std::pair<out_edge_iterator, out_edge_iterator>
648 edge_range(vertex_descriptor u, vertex_descriptor v,
649 const adjacency_list& g);
651 TODO: Not implemented. Returns a pair of out-edge iterators that give
652 the range for all the parallel edges from ``u`` to ``v``. This function only
653 works when the ``OutEdgeList`` for the ``adjacency_list`` is a container that
654 sorts the out edges according to target vertex, and allows for
655 parallel edges. The ``multisetS`` selector chooses such a
656 container. Vertex ``u`` must be stored in the executing process.
658 Structure Modification
659 ~~~~~~~~~~~~~~~~~~~~~~
663 unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g);
664 unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g);
665 unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g);
666 unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list& g);
668 Adds edge ``(u,v)`` to the graph. The return type itself is
669 unspecified, but the type can be copy-constructed and implicitly
670 converted into a ``std::pair<edge_descriptor,bool>``. The edge
671 descriptor describes the added (or found) edge. For graphs that do not
672 allow parallel edges, if the edge
673 is already in the graph then a duplicate will not be added and the
674 ``bool`` flag will be ``false``. Also, if u and v are descriptors for
675 the same vertex (creating a self loop) and the graph is undirected,
676 then the edge will not be added and the flag will be ``false``. When
677 the flag is ``false``, the returned edge descriptor points to the
678 already existing edge.
680 The parameters ``u`` and ``v`` can be either vertex descriptors or, if
681 the graph uses named vertices, the names of vertices. If no vertex
682 with the given name exists, the internal vertex constructor will be
683 invoked to create a new vertex property and a vertex with that
684 property will be added to the graph implicitly. The default internal
685 vertex constructor throws an exception.
687 -----------------------------------------------------------------------------
691 unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
692 unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
693 unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
694 unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
697 Adds edge ``(u,v)`` to the graph and attaches ``p`` as the value of the edge's
698 internal property storage. See the previous ``add_edge()`` member
699 function for more details.
701 -----------------------------------------------------------------------------
706 remove_edge(vertex_descriptor u, vertex_descriptor v,
709 Removes the edge ``(u,v)`` from the graph. If the directed selector is
710 ``bidirectionalS`` or ``undirectedS``, either the source or target
711 vertex of the graph must be local. If the directed selector is
712 ``directedS``, then the source vertex must be local.
714 -----------------------------------------------------------------------------
719 remove_edge(edge_descriptor e, adjacency_list& g);
721 Removes the edge ``e`` from the graph. If the directed selector is
722 ``bidirectionalS`` or ``undirectedS``, either the source or target
723 vertex of the graph must be local. If the directed selector is
724 ``directedS``, then the source vertex must be local.
726 -----------------------------------------------------------------------------
730 void remove_edge(out_edge_iterator iter, adjacency_list& g);
732 This has the same effect as ``remove_edge(*iter, g)``. For directed
733 (but not bidirectional) graphs, this will be more efficient than
734 ``remove_edge(*iter, g)``.
736 -----------------------------------------------------------------------------
740 template <class Predicate >
741 void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
744 Removes all out-edges of vertex ``u`` from the graph that satisfy the
745 predicate. That is, if the predicate returns ``true`` when applied to an
746 edge descriptor, then the edge is removed. The vertex ``u`` must be local.
748 The affect on descriptor and iterator stability is the same as that of
749 invoking remove_edge() on each of the removed edges.
751 -----------------------------------------------------------------------------
755 template <class Predicate >
756 void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
759 Removes all in-edges of vertex ``v`` from the graph that satisfy the
760 predicate. That is, if the predicate returns true when applied to an
761 edge descriptor, then the edge is removed. The vertex ``v`` must be local.
763 The affect on descriptor and iterator stability is the same as that of
764 invoking ``remove_edge()`` on each of the removed edges.
766 This operation is available for undirected and bidirectional
767 adjacency_list graphs, but not for directed.
769 -----------------------------------------------------------------------------
773 template <class Predicate>
774 void remove_edge_if(Predicate predicate, adjacency_list& g);
776 Removes all edges from the graph that satisfy the predicate. That is,
777 if the predicate returns true when applied to an edge descriptor, then
780 The affect on descriptor and iterator stability is the same as that
781 of invoking ``remove_edge()`` on each of the removed edges.
783 -----------------------------------------------------------------------------
787 vertex_descriptor add_vertex(adjacency_list& g);
789 Adds a vertex to the graph and returns the vertex descriptor for the
790 new vertex. The vertex will be stored in the local process. This
791 function is not available when using named vertices.
793 -----------------------------------------------------------------------------
797 unspecified add_vertex(const VertexProperties& p, adjacency_list& g);
798 unspecified add_vertex(const vertex_name_type& p, adjacency_list& g);
800 Adds a vertex to the graph with the specified properties. If the graph
801 is using vertex names, the vertex will be added on whichever process
802 "owns" that name. Otherwise, the vertex will be stored in the local
803 process. Note that the second constructor will invoke the
804 user-customizable internal vertex constructor, which (by default)
805 throws an exception when it sees an unknown vertex.
807 The return type is of unspecified type, but can be copy-constructed
808 and can be implicitly converted into a vertex descriptor.
810 -----------------------------------------------------------------------------
814 void clear_vertex(vertex_descriptor u, adjacency_list& g);
816 Removes all edges to and from vertex ``u``. The vertex still appears
817 in the vertex set of the graph.
819 The affect on descriptor and iterator stability is the same as that of
820 invoking ``remove_edge()`` for all of the edges that have ``u`` as the source
823 This operation is not applicable to directed graphs, because the
824 incoming edges to vertex ``u`` are not known.
826 -----------------------------------------------------------------------------
830 void clear_out_edges(vertex_descriptor u, adjacency_list& g);
832 Removes all out-edges from vertex ``u``. The vertex still appears in
833 the vertex set of the graph.
835 The affect on descriptor and iterator stability is the same as that of
836 invoking ``remove_edge()`` for all of the edges that have ``u`` as the
839 This operation is not applicable to undirected graphs (use
840 ``clear_vertex()`` instead).
842 -----------------------------------------------------------------------------
846 void clear_in_edges(vertex_descriptor u, adjacency_list& g);
848 Removes all in-edges from vertex ``u``. The vertex still appears in
849 the vertex set of the graph.
851 The affect on descriptor and iterator stability is the same as that of
852 invoking ``remove_edge()`` for all of the edges that have ``u`` as the
855 This operation is only applicable to bidirectional graphs.
857 -----------------------------------------------------------------------------
861 void remove_vertex(vertex_descriptor u, adjacency_list& g);
863 Remove vertex ``u`` from the vertex set of the graph. It is assumed
864 that there are no edges to or from vertex ``u`` when it is
865 removed. One way to make sure of this is to invoke ``clear_vertex()``
866 beforehand. The vertex ``u`` must be stored locally.
868 Property Map Accessors
869 ~~~~~~~~~~~~~~~~~~~~~~
873 template <class PropertyTag>
874 property_map<adjacency_list, PropertyTag>::type
875 get(PropertyTag, adjacency_list& g);
877 template <class PropertyTag>
878 property_map<adjacency_list, Tag>::const_type
879 get(PropertyTag, const adjacency_list& g);
881 Returns the property map object for the vertex property specified by
882 ``PropertyTag``. The ``PropertyTag`` must match one of the properties
883 specified in the graph's ``VertexProperty`` template argument. The
884 returned property map will be a `distributed property map`_.
886 -----------------------------------------------------------------------------
890 template <class PropertyTag , class X>
891 typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
892 get(PropertyTag, const adjacency_list& g, X x);
894 This returns the property value for ``x``, where ``x`` is either a vertex or
895 edge descriptor. The entity referred to by descriptor ``x`` must be
896 stored in the local process.
898 -----------------------------------------------------------------------------
902 template <class PropertyTag , class X, class Value>
903 void put(PropertyTag, const adjacency_list& g, X x, const Value& value);
905 This sets the property value for ``x`` to value. ``x`` is either a
906 vertex or edge descriptor. ``Value`` must be convertible to ``typename
907 property_traits<property_map<adjacency_list,
908 PropertyTag>::type>::value_type``.
910 -----------------------------------------------------------------------------
914 template <class GraphProperties, class GraphPropertyTag>
915 typename graph_property<adjacency_list, GraphPropertyTag>::type&
916 get_property(adjacency_list& g, GraphPropertyTag);
918 template <class GraphProperties, class GraphPropertyTag >
919 const typename graph_property<adjacency_list, GraphPropertyTag>::type&
920 get_property(const adjacency_list& g, GraphPropertyTag);
922 TODO: not implemented.
924 Return the property specified by ``GraphPropertyTag`` that is attached
925 to the graph object ``g``. The ``graph_property`` traits class is
926 defined in ``boost/graph/adjacency_list.hpp``.
928 -----------------------------------------------------------------------------
930 Copyright (C) 2004 The Trustees of Indiana University.
932 Copyright (C) 2007 Douglas Gregor
934 Authors: Douglas Gregor and Andrew Lumsdaine
936 .. |Logo| image:: pbgl-logo.png
939 :target: http://www.osl.iu.edu/research/pbgl
941 .. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
942 .. _guidelines: http://www.boost.org/libs/graph/doc/using_adjacency_list.html
943 .. _process group: process_group.html
944 .. _mpi process group: process_group.html
945 .. _distributedS: distributedS.html
946 .. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
947 .. _Distributed graph: DistributedGraph.html
948 .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
949 .. _Adjacency Graph: http://www.boost.org/libs/graph/doc/AdjacencyGraph.html
950 .. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html
951 .. _Mutable Graph: http://www.boost.org/libs/graph/doc/MutableGraph.html
952 .. _Property Graph: http://www.boost.org/libs/graph/doc/PropertyGraph.html
953 .. _Mutable Property Graph: http://www.boost.org/libs/graph/doc/MutablePropertyGraph.html
954 .. _Vertex List Graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
955 .. _Edge List Graph: http://www.boost.org/libs/graph/doc/EdgeListGraph.html
956 .. _Distribution: concepts/Distribution.html
957 .. _distributed property map: distributed_property_map.html
958 .. _distributed property maps: distributed_property_map.html
959 .. _Distributed Vertex List Graph: DistributedVertexListGraph.html
960 .. _Distributed Edge List Graph: DistributedEdgeListGraph.html
961 .. _InputIterator: http://www.boost.org/doc/html/InputIterator.html
962 .. _member: http://www.boost.org/libs/multi_index/doc/reference/key_extraction.html#member_synopsis
963 .. _Boost.MultiIndex: http://www.boost.org/libs/multi_index/doc/index.html
964 .. _sorted_erdos_renyi_iterator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html