mirror of
https://github.com/boostorg/graph.git
synced 2026-01-29 19:42:11 +00:00
779 lines
22 KiB
Plaintext
779 lines
22 KiB
Plaintext
[/
|
|
/ Copyright (c) 2007 Andrew Sutton
|
|
/
|
|
/ Distributed under 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)
|
|
/]
|
|
|
|
[section Directed Graph]
|
|
This section provides detailed information about the `directed_graph` class,
|
|
its associated types, member functions and non-member interface. A directed
|
|
graph is one in which edges have distinct direction. Edges flow from a /source/
|
|
vertex to a /target/ and are generally only traversed through the outgoing
|
|
edges of a vertex. However, incoming edges are also accessible. The class
|
|
provides a general purpose implementation of directed graphs and can be
|
|
used with algorithms in the Boost Graph Library.
|
|
|
|
[h4 Notation]
|
|
The following notation is used in this documentation. The following type names
|
|
are generally meant to mean the following:
|
|
[table
|
|
[[Used Type] [Actual Type]]
|
|
[
|
|
[`directed_graph`]
|
|
[
|
|
`directed_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
|
|
arguments that correspond to user-defined or default verex properties,
|
|
edge properties, and graph properties.
|
|
]
|
|
]
|
|
[
|
|
[`vertex_descriptor`]
|
|
[`directed_graph<VP,EP,GP>::vertex_descriptor`]
|
|
]
|
|
[
|
|
[`edge_descriptor`]
|
|
[`directed_graph<VP,EP,GP>::edge_descriptor`]
|
|
]
|
|
[
|
|
[`vertex_iterator`]
|
|
[`directed_graph<VP,EP,GP>::vertex_iterator`]
|
|
]
|
|
[
|
|
[`edge_iterator`]
|
|
[`directed_graph<VP,EP,GP>::edge_iterator`]
|
|
]
|
|
]
|
|
|
|
Moreover, objects with the following names are generally expected to have the
|
|
following types.
|
|
|
|
[table
|
|
[[Object Name] [Type]]
|
|
[[`g`] [`directed_graph`]]
|
|
[[`u`, `v`] [`vertex_descriptor`]]
|
|
[[`e`] [`edge_descriptor`]]
|
|
[[`i`] [`vertex_iterator` or `edge_iterator`]]
|
|
[[`p`] [A property tag (usually a template parameter)]]
|
|
[[`d`] [A vertex or edge descriptor (usually a template parameter)]]
|
|
[[`v`] [The value of a property (usually a template parameter)]]
|
|
]
|
|
|
|
[h4 Descriptor and Iterator Stability]
|
|
With the `directed_graph` class, descriptors and iterators remain stable after
|
|
all operations except descriptors and iterators to those edges or vertices being
|
|
removed. Removing a vertex or edge will not invalidate descriptors or iterators
|
|
referencing other vertices or edges.
|
|
|
|
For example, consider the following code:
|
|
|
|
directed_graph<> g;
|
|
directed_graph<>::vertex_descriptor u = add_vertex(g);
|
|
directed_graph<>::vertex_descriptor v = add_vertex(g);
|
|
directed_graph<>::vertex_descriptor w = add_vertex(g);
|
|
remove_vertex(u);
|
|
add_edge(v, w, g);
|
|
|
|
After running this program, the descriptor `u` will be invalid but `v` and `w` will
|
|
still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
|
|
property does not hold for all graph types.
|
|
|
|
[h4 Vertex Indexing and Stability]
|
|
The `directed_graph` class provides a built-in internal properties for vertex
|
|
types, and will provide some degree of automated index management. Algorithms
|
|
that use vertex indices generally assume that they are in the range
|
|
\[0, `num_vertices(g)`). With the `directed_graph` class vertex indices will
|
|
be in this continuous range until a vertex is removed from the graph. This is
|
|
the only operation that invalidates vertex indices, but the vertices will need
|
|
to be renumbered using the `renumber_vertex_indices()` function.
|
|
|
|
The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
|
|
renumber indices after removing the vertex referenced by the given iterator. Because
|
|
this function runs in linear time, it should not be used for repeated removals.
|
|
|
|
[h4 Template Parameters]
|
|
There are three parameters to the `directed_graph` class.
|
|
[table
|
|
[[Parameter] [Description] [Default]]
|
|
[
|
|
[`VertexProperties`]
|
|
[Specifies internal properties for vertices of the graph.]
|
|
[`no_property`]
|
|
]
|
|
[
|
|
[`EdgeProperties`]
|
|
[Specifies internal properties for edges of the graph.]
|
|
[`no_property`]
|
|
]
|
|
[
|
|
[`GraphProperties`]
|
|
[Specifies internal properties for the graph itself.]
|
|
[`no_property`]
|
|
]
|
|
]
|
|
|
|
[h5 Model Of]
|
|
[IncidenceGraph], [VertexListGraph], [EdgeListGraph], [AdjacencyGraph],
|
|
[MutableGraph], and [PropertyGraph].
|
|
|
|
[h5 Where Defined]
|
|
`boost/graph/directed_graph.hpp`
|
|
|
|
[h4 Associated Types]
|
|
There are a number of useful types associated with the `directed_graph` class.
|
|
Most of these are accessed through [graph_traits] or other template classes.
|
|
For convenience these types have been grouped by purpose.
|
|
|
|
[h5 Descriptor Types]
|
|
[table
|
|
[[Type] [Description]]
|
|
[
|
|
[`graph_traits<directed_graph>::vertex_descriptor`]
|
|
[
|
|
The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
|
|
models the [Descriptor] and [NoConcept Hashable] concepts.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::edge_descriptor`]
|
|
[
|
|
The type for the edge descriptors associated with the graph. The `edge_descriptor`
|
|
models the [Descriptor] and [NoConcept Hashable] concepts.
|
|
]
|
|
]
|
|
]
|
|
|
|
Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
|
|
[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
|
|
`std::tr1::unordered_map` respectively.
|
|
|
|
[h5 Iterator Types]
|
|
[table
|
|
[[Type] [Description]]
|
|
[
|
|
[`graph_traits<directed_graph>::vertex_iterator`]
|
|
[
|
|
The type for iterators returned by `vertices()`. Verex iterators are
|
|
models of the [SgiBidirectionalIterator] concept.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::edge_iterator`]
|
|
[
|
|
The type for iterators returned by `edges()`. Edge iterators are
|
|
models of the [SgiBidirectionalIterator] concept.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::out_edge_iterator`]
|
|
[
|
|
The type for iterators returned by `out_edges()`. Out-edge iterators
|
|
are models of the [SgiBidirectionalIterator] concept.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::in_edge_iterator`]
|
|
[
|
|
The type for iterators returned by `in_edges()`. In-edge iterators
|
|
are models of the [SgiBidirectionalIterator] concept.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::adjacency_iterator`]
|
|
[
|
|
The type for iterators returned by `adjacent_vertices`. Adjacency
|
|
iterators are models of the [SgiBidirectionalIterator] concept.
|
|
]
|
|
]
|
|
]
|
|
|
|
[h5 Miscellaneous Types]
|
|
[table
|
|
[[Type] [Description]]
|
|
[
|
|
[`graph_traits<directed_graph>::vertices_size_type`]
|
|
[The type used for dealing with the number of vertices in the graph.]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::edge_size_type`]
|
|
[The type used for dealing with the number of edges in the graph.]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::degree_size_type`]
|
|
[The type used for dealing with the number of edges incident to a vertex in the graph.]
|
|
]
|
|
[
|
|
[`directed_graph::vertex_index_type`]
|
|
[The integral type representing vertex indices (generally `unsigned int`).]
|
|
]
|
|
[
|
|
[
|
|
`property_map<directed_graph, Property>::type`
|
|
|
|
`property_map<directed_graph, Property>::const_type`
|
|
]
|
|
[
|
|
The property map type for vertex or edge properties in the graph. The specific
|
|
property is specified by the `Property` template argument, and must match one of
|
|
the properties specified in the `VertexProperties` or `EdgeProperties` for the
|
|
graph.
|
|
]
|
|
]
|
|
[
|
|
[`graph_property<directed_graph, Property>::type`]
|
|
[
|
|
The value type for the graph property specified by the `Property` parameter.
|
|
`Property` must be one of the types in the `GraphProperties` template argument.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::directed_category`]
|
|
[
|
|
This is always `bidirectional_tag`, indicating that the graph supports in- and
|
|
out-edge operations.
|
|
]
|
|
]
|
|
[
|
|
[`graph_traits<directed_graph>::edge_parallel_category`]
|
|
[
|
|
This is always `allow_parallel_edges_tag`, indicating that multiple edges
|
|
may be added between two vertices (i.e., graphs can be /multigraphs/).
|
|
]
|
|
]
|
|
]
|
|
|
|
[h4 Member Functions]
|
|
[table
|
|
[[Function] [Description]]
|
|
[
|
|
[
|
|
``
|
|
directed_graph(const GraphProperties& p = GraphProperties())
|
|
``
|
|
]
|
|
[The default constructor creates a graph with no vertices or edges.]
|
|
]
|
|
[
|
|
[
|
|
``directed_graph(const directed_graph& g)
|
|
``
|
|
]
|
|
[The copy constructor creates a copy of the given graph `g`.]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
directed_graph(vertices_size_type n,
|
|
const GraphProperties& p = GraphProperties())
|
|
``
|
|
]
|
|
[The default constructor creates a graph with `n` vertices and no edges.]
|
|
]
|
|
[
|
|
[
|
|
``directed_graph& operator =(const directed_graph& g)
|
|
``
|
|
]
|
|
[Copies the edges and vertices of the graph `g`.]
|
|
]
|
|
]
|
|
|
|
[h4 Non-member Functions]
|
|
[h5 Non-member Accessors]
|
|
[table
|
|
[[Function] [Description]]
|
|
[
|
|
[
|
|
``
|
|
std::pair<vertex_iterator, vertex_iterator>
|
|
vertices(const directed_graph& g)
|
|
``
|
|
]
|
|
[Returns an iterator range providing access to the vertex list of `g`.]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
std::pair<edge_iterator, edge_iterator>
|
|
edges(const directed_graph& g)
|
|
``
|
|
]
|
|
[Returns an iterator range providing access to the edge list of `g`.]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
std::pair<out_edge_iterator, out_edge_iterator>
|
|
out_edges(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns an iterator range providing access to the out-edges of
|
|
vertex `v` in the graph `g`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
std::pair<in_edge_iterator, in_edge_iterator>
|
|
in_edges(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns an iterator range providing access to the in-edges of
|
|
vertex `v` in the graph `g`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
std::pair<adjacency_iterator, adjacency_iterator>
|
|
adjacent_vertices(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns an iterator range providing access to the adjacenct vertices
|
|
of vertex `v` in the graph `g`. Note that this is functionally
|
|
equivalent to iterating over the targets of all out-edges of `v`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
vertices_size_type
|
|
num_vertices(const directed_graph& g)
|
|
``
|
|
]
|
|
[Returns the number of vertices in the graph `g`.]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
edge_size_type
|
|
num_edges(const directed_graph& g)
|
|
``
|
|
]
|
|
[Returns the number of edges the graph `g`.]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
degree_size_type
|
|
degree(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the total degree of vertex `v` in the graph `g`. This is
|
|
functionally equivalent `out_degree(v,g) + in_degree(v,g)`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
degree_size_type
|
|
out_degree(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the out-degree of vertex `v` in the graph `g`. In an
|
|
`directed_graph` this is equal to `in_degree(v, g)`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
degree_size_type
|
|
in_degree(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the in-degree of vertex `v` in the graph `g`. In an
|
|
`directed_graph` this is equal to `out_degree(v, g)`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
vertex_descriptor
|
|
vertex(vertices_size_type n
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the /nth/ vertex in the graph `g`. With directed graphs,
|
|
this method is /O(n)/. As such its use with this type of graph is
|
|
discouraged.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
std::pair<edge_descriptor, bool>
|
|
edge(vertex_descriptor u,
|
|
vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
If the edge /(u,v)/ is in `g`, then this function returns the
|
|
descriptor for the edge connecting `u` and `v` with boolean value
|
|
set to `true`. Otherwise, the boolean value is `false` and the
|
|
edge descriptor is invalid.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
vertex_size_type
|
|
get_vertex_index(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the vertex index of the given vertex descriptor v. Note
|
|
that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
|
|
This function is an alias for `get(vertex_index,g,v)`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
vertex_size_type
|
|
max_vertex_index(vertex_descriptor v,
|
|
const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the vertex index of the given vertex descriptor v. Note
|
|
that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
|
|
This function is an alias for `get(vertex_index,g,v)`.
|
|
]
|
|
]
|
|
]
|
|
|
|
[h5 Non-member Modifiers]
|
|
[table
|
|
[[Function] [Description]]
|
|
[
|
|
[
|
|
``
|
|
vertex_descriptor
|
|
add_vertex(directed_graph& g)
|
|
``
|
|
]
|
|
[Adds a vertex to `g` and returns a descriptors for the new vertex.]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
clear_vertex(vertex_descriptor v,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes all in- and out-edges of `v`, but leaves `v` in the graph `g`.
|
|
This is functioanlly equivalent to invoking `remove_edge()` on all
|
|
in- or out-edges of `v`, invalidating descriptors and iterators that
|
|
reference edges incident to `v`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
clear_out_edges(vertex_descriptor v,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes all out-edges from vertex `v`, but does not remove the vertex
|
|
itself. This is functionally equivalent to calling `remove_edge()` for
|
|
all out-edges of `v`, invalidating any descriptors and iterators that
|
|
reference edges incident to that vertex.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
clear_in_edges(vertex_descriptor v,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes all in-edges from vertex `v`, but does not remove the vertex
|
|
itself. This is functionally equivalent to calling `remove_edge()` for
|
|
all in-edges of `v`, invalidating any descriptors and iterators that
|
|
reference edges incident to that vertex.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
vertex_descriptor
|
|
remove_vertex(vertex_descriptor v,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes vertex `v` from the graph `g`. It is assumed that `v` has no
|
|
incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
|
|
before removing it.
|
|
|
|
Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
|
|
before calling this method, this operation will invalidate all vertex indices
|
|
in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
|
|
be renumbered using the `renumber_vertex_indices(g)` method. If possible,
|
|
prefer to remove groups of vertices at one time before renumbering since
|
|
renumbering is a /O(n)/ time operation.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
remove_vertex_and_renumber_indices(vertex_iterator i,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes the vertex indicated by the iterator `i` from the graph `g`. Like
|
|
the `remove_vertex(v,g)` function, it is expected that `*i` have no
|
|
incident edges at the time of removal.
|
|
|
|
As indicated by the name, this method will also renumber vertex indices
|
|
after the removal of `*i`. This operation iterates over vertices after
|
|
`i`, decrementing their index by 1. If your program removes several
|
|
vertices at once, prefer to call several `remove_vertex(v,g)` methods,
|
|
followed by `renumber_vertices(g)` before using `g` in an algorithm.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
renumber_vertex_indices(directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Renumbers all interior vertex indices such that each vertex has an index
|
|
in the range \[0, `num_vertices(g)`). Generally, this function needs to
|
|
be called after removing vertices and before invoking different graph
|
|
algorithms.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
std::pair<edge_descriptor, bool>
|
|
add_edge(vertex_descriptor u,
|
|
vertex_descriptor v,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
|
|
edge. For `directed_graph`s, the boolean value of the pair will always
|
|
be true.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
remove_edge(vertex_descriptor u,
|
|
vertex_descriptor v,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes the edge /(u,v)/from the graph. This operation invalidates any
|
|
descriptors or iterators referencing the edge. Note that `u` and `v` must
|
|
be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
|
|
(with multiple edges between /(u,v)/, this mehtod will cause the removal of
|
|
all such edges connecting `u` and `v`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
remove_edge(edge_descriptor e,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes the edge `e` from the graph. If multuple edges exist from
|
|
/(`source(e,g)`, `target(e,g)`)/, then this method will remove only
|
|
the single, specified edge.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
remove_edge(out_edge_iterator i,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
This is functionally equivalent to `remove_edge(*i, g)`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
void
|
|
remove_edge_if(Predicate p,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes all edges from the graph that satisfy `predicate`. That is, if
|
|
`p()` returns true when applied to an edge, then that edge is removed.
|
|
The affect on descriptor and iterator is the same as that of invoking
|
|
`remove_edge()` for on each of the removed vertices.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
template <class Predicate>
|
|
void
|
|
remove_out_edge_if(vertex_descriptor v,
|
|
Predicate p,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes all edges out-edges from vertex`v` that satisfy `predicate`.
|
|
That is, if `p()` returns true when applied to an edge, then that edge
|
|
is removed. The affect on descriptor and iterator is the same as that
|
|
of invoking `remove_edge()` for on each of the removed vertices.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
template <class Predicate>
|
|
void
|
|
remove_in_edge_if(vertex_descriptor v,
|
|
Predicate p,
|
|
directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Removes all edges in-edges from vertex`v` that satisfy `predicate`.
|
|
That is, if `p()` returns true when applied to an edge, then that edge
|
|
is removed. The affect on descriptor and iterator is the same as that
|
|
of invoking `remove_edge()` for on each of the removed vertices.
|
|
]
|
|
]
|
|
]
|
|
|
|
[h5 Proprety Map Acessors]
|
|
[table
|
|
[[Function] [Description]]
|
|
[
|
|
[
|
|
``
|
|
template <class Property>
|
|
property_map<directed_graph, Property>::type
|
|
get(Property, directed_graph& g)
|
|
``
|
|
|
|
``
|
|
template <class Property>
|
|
property_map<directed_graph, Property>::const_type
|
|
get(Property, const directed_graph& g)
|
|
``
|
|
]
|
|
[
|
|
Returns the property map object for the vertex property specified by the
|
|
type `Property`. This type must match one of the properties specified in
|
|
the `VertexProperties` template argument.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
template <class Property, class Descriptor>
|
|
typename
|
|
property_traits<
|
|
property_map<directed_graph, Property>::const_type
|
|
>::value_type
|
|
get(Property,
|
|
const directed_graph& g,
|
|
Descriptor d)
|
|
``
|
|
]
|
|
[
|
|
Returns the property value specified by the type `Property` for either
|
|
the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
template <class Property, class Descriptor, class Value>
|
|
void
|
|
put(Property,
|
|
const directed_graph& g,
|
|
Descriptor d,
|
|
Value v)
|
|
``
|
|
]
|
|
[
|
|
Sets the property value denoted by the type `Property` for either edge
|
|
or vertex descriptor `d` to the given value `v`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
template <class GraphProprety>
|
|
typename graph_property<directed_graph, GraphProperty>::type&
|
|
get_property(directed_graph& g, GraphProperty)
|
|
``
|
|
|
|
``
|
|
template <class GraphProprety>
|
|
const typename graph_property<directed_graph, GraphProperty>::type&
|
|
get_property(const directed_graph& g, GraphProperty)
|
|
``
|
|
]
|
|
[
|
|
Returns the graph property specified by the type `GraphProperty` for
|
|
the graph `g`.
|
|
]
|
|
]
|
|
[
|
|
[
|
|
``
|
|
template <class GraphProprety, class Value>
|
|
void
|
|
set_property(const directed_graph& g, GraphProperty, Value v)
|
|
``
|
|
]
|
|
[
|
|
Sets the graph proeprty specified by the type `GraphProperty` to
|
|
the given value `v`. Note that `GraphProperty` must be one of
|
|
the properties in the `GraphProperties` template argument.
|
|
]
|
|
]
|
|
]
|
|
|
|
[h4 Rationale]
|
|
Unlike most graph classes in Boost.Graph, the `directed_graph` does not model the
|
|
[MutablePropertyGraph] concept. The reason for this is that it is relatively
|
|
difficult from a usability standpoint to easily deduce the type to be passed as a
|
|
property when adding vertices and edges - but especially vertices.
|
|
|
|
[endsect] |