|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r55976 - in trunk/libs/graph/quickbook: . concepts guide reference
From: asutton_at_[hidden]
Date: 2009-09-02 10:23:31
Author: asutton
Date: 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
New Revision: 55976
URL: http://svn.boost.org/trac/boost/changeset/55976
Log:
Working on quickbook docs.
Restructuring parts of the user's guide.
Removed some concepts and fixed issues with others.
Added (incomplete) adjacency_matrix docs.
Added:
trunk/libs/graph/quickbook/guide/theory.qbk (contents, props changed)
- copied, changed from r55957, /trunk/libs/graph/quickbook/theory.qbk
trunk/libs/graph/quickbook/guide/tour.qbk (contents, props changed)
- copied, changed from r55957, /trunk/libs/graph/quickbook/tour.qbk
trunk/libs/graph/quickbook/reference/adjacency_matrix.qbk (contents, props changed)
Removed:
trunk/libs/graph/quickbook/theory.qbk
trunk/libs/graph/quickbook/tour.qbk
Text files modified:
trunk/libs/graph/quickbook/boost_reference.qbk | 36 +
trunk/libs/graph/quickbook/concepts/clique_visitor.qbk | 31 -
trunk/libs/graph/quickbook/concepts/cycle_visitor.qbk | 26 -
trunk/libs/graph/quickbook/concepts/degree_measure.qbk | 2
trunk/libs/graph/quickbook/concepts/descriptor.qbk | 3
trunk/libs/graph/quickbook/concepts/dfs_visitor.qbk | 2
trunk/libs/graph/quickbook/concepts/dijkstra_visitor.qbk | 2
trunk/libs/graph/quickbook/concepts/distance_measure.qbk | 2
trunk/libs/graph/quickbook/concepts/event_visitor.qbk | 44 +-
trunk/libs/graph/quickbook/concepts/event_visitor_list.qbk | 6
trunk/libs/graph/quickbook/concepts/graphs.qbk | 75 ++--
trunk/libs/graph/quickbook/concepts/incidence_graph.qbk | 2
trunk/libs/graph/quickbook/concepts/numeric_value.qbk | 15
trunk/libs/graph/quickbook/concepts/utility.qbk | 12
trunk/libs/graph/quickbook/concepts/vertex_index_graph.qbk | 2
trunk/libs/graph/quickbook/concepts/visitor.qbk | 13
trunk/libs/graph/quickbook/guide/adjacency_list.qbk | 264 ++++++++--------
trunk/libs/graph/quickbook/guide/directed_graph.qbk | 2
trunk/libs/graph/quickbook/guide/guide.qbk | 8
trunk/libs/graph/quickbook/guide/theory.qbk | 391 +++++++++++++----------
trunk/libs/graph/quickbook/guide/tour.qbk | 291 +++++++++--------
trunk/libs/graph/quickbook/introduction.qbk | 8
trunk/libs/graph/quickbook/reference/adjacency_list.qbk | 649 +++++++++++++++++++++++++++++----------
trunk/libs/graph/quickbook/reference/reference.qbk | 10
trunk/libs/graph/quickbook/sgi_concepts.qbk | 69 ++-
25 files changed, 1183 insertions(+), 782 deletions(-)
Modified: trunk/libs/graph/quickbook/boost_reference.qbk
==============================================================================
--- trunk/libs/graph/quickbook/boost_reference.qbk (original)
+++ trunk/libs/graph/quickbook/boost_reference.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -14,12 +14,22 @@
[template undirected_graph[] [link boost_graph.reference.graph_types.undirected_graph [^undirected_graph]]]
[template directed_graph[] [link boost_graph.reference.graph_types.directed_graph [^directed_graph]]]
[template adjacency_list[] [link boost_graph.reference.graph_types.adjacency_list [^adjacecncy_list]]]
+[template adjacency_matrix[] [link boost_graph.reference.graph_types.adjacency_matrix [^adjacecncy_matrix]]]
[template edge_list[] [link boost_graph.reference.graph_types.edge_list [^edge_list]]]
[/ Visitor types /]
[template null_visitor[] [link boost_graph.reference.visitor_types.null_visitor [^null_visitor]]]
[template bfs_visitor[] [link boost_graph.reference.visitor_types.bfs_visitor [^bfs_visitor]]]
[template dfs_visitor[] [link boost_graph.reference.visitor_types.dfs_visitor [^dfs_visitor]]]
+[template astar_visitor[] [link boost_graph.reference.visitor_types.astar_visitor [^astar_visitor]]]
+[template dijkstra_visitor[] [link boost_graph.reference.visitor_types.dijkstra_visitor [^dijkstra_visitor]]]
+[template bellman_ford_visitor[] [link boost_graph.reference.visitor_types.bellman_ford_visitor [^bellman_ford_visitor]]]
+[template clique_visitor[] [link boost_graph.reference.visitor_types.clique_visitor [^clique_visitor]]]
+[template max_clique_visitor[] [link boost_graph.reference.visitor_types.max_clique_visitor [^max_clique_visitor]]]
+[template cycle_visitor[] [link boost_graph.reference.visitor_types.cycle_visitor [^cycle_visitor]]]
+[template min_max_cycle_visitor[] [link boost_graph.reference.visitor_types.min_max_cycle_visitor [^min_max_cycle_visitor]]]
+
+[/ Event Visitors /]
[template predecessor_recorder[] [link boost_graph.reference.event_visitors.predecessor_recorder [^predecessor_recorder]]]
[template distance_recorder[] [link boost_graph.reference.event_visitors.distance_recorder [^distance_recorder]]]
[template time_stamper[] [link boost_graph.reference.event_visitors.time_stamper [^time_stamper]]]
@@ -155,16 +165,16 @@
graph
[^exterior_edge_property]]]
-[/ Import a number of examples to build code templates /]
-[import ../examples/degree_centrality.cpp]
-[import ../examples/influence_prestige.cpp]
-[import ../examples/closeness_centrality.cpp]
-[import ../examples/scaled_closeness_centrality.cpp]
-[import ../examples/mean_geodesic.cpp]
-[import ../examples/inclusive_mean_geodesic.cpp]
-[import ../examples/eccentricity.cpp]
-[import ../examples/clustering_coefficient.cpp]
-[import ../examples/tiernan_print_cycles.cpp]
-[import ../examples/tiernan_girth_circumference.cpp]
-[import ../examples/bron_kerbosch_print_cliques.cpp]
-[import ../examples/bron_kerbosch_clique_number.cpp]
+[/ Import a number of example to build code templates /]
+[import ../example/degree_centrality.cpp]
+[import ../example/influence_prestige.cpp]
+[import ../example/closeness_centrality.cpp]
+[import ../example/scaled_closeness_centrality.cpp]
+[import ../example/mean_geodesic.cpp]
+[import ../example/inclusive_mean_geodesic.cpp]
+[import ../example/eccentricity.cpp]
+[import ../example/clustering_coefficient.cpp]
+[import ../example/tiernan_print_cycles.cpp]
+[import ../example/tiernan_girth_circumference.cpp]
+[import ../example/bron_kerbosch_print_cliques.cpp]
+[import ../example/bron_kerbosch_clique_number.cpp]
Modified: trunk/libs/graph/quickbook/concepts/clique_visitor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/clique_visitor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/clique_visitor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -18,36 +18,27 @@
[[Name] [Expression] [Result Type] [Description]]
[
[Visit Clique]
- [`vis.clique(vs,g)`]
+ [`vis.clique(c,g)`]
[`void`]
[
The `clique()` member function of the visitor is invoked when a fully
- connected subgraph is identified in the graph `g`.
+ connected subgraph, `c`, is identified in the graph `g`.
*Requirements:* `g` is an object whose type `G` is a refinement of the
[Graph] concept.
- *Requirements:* `vs` is an object whose type `VS` is a refinement of the
- [SgiContainer] concept. The `value_type` of `VS` must be the `vertex_descriptor`
- of `G`.
-
- *Precondition:* All vertices in the [SgiContainer] `vs` are connected.
- If `g` is a directed graph, then all vertices, /u/ and /v/, are connected
- by edges /(u,v)/ and /(v,u)/.
+ *Requirements:* `c` is an object whose type `C` is a refinement of the
+ [SgiContainer] concept, and the `value_type` of `C` must be the same
+ as the `vertex_descriptor` of `G`.
+
+ *Note:* All vertices in the `c` are connected. If `g` is a directed
+ graph, then all vertices, /u/ and /v/, are stringly connected (i.e.,
+ the edges /(u,v)/ and /(v,u)/ are in `g`).
]
]
]
-[heading C++0x]
-This concept is defined as:
-
- concept CliqueVisitor<typename T>
- {
- Graph graph_type;
-
- template<Container VertexSet>
- requires SameType<VertexSet::value_type, graph_type::vertex_descriptor>
- void T::clique(const VertexSet&, graph_type&);
- };
+[heading Models]
+[clique_visitor], [max_clique_visitor]
[endsect]
Modified: trunk/libs/graph/quickbook/concepts/cycle_visitor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/cycle_visitor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/cycle_visitor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -18,36 +18,26 @@
[[Name] [Expression] [Result Type] [Description]]
[
[Visit Cycle]
- [`vis.cycle(vs,g)`]
+ [`vis.cycle(c,g)`]
[`void`]
[
The `vis.cycle()` member function of the visitor is invoked when a
- cycle is identified in the graph `g`. The vertices in `vs` are arranged
+ cycle is identified in the graph `g`. The vertices in `c` are arranged
such that first vertex is connected to the second, and that is connected
to the third, etc. The `back()` vertex is connected to the `front()`
- to form a cycle.
+ to form the reported cycle.
*Requirements:* `g` is an object whose type `G` is a model of the
[Graph] concept.
- *Requirements:* `vs` is an object whose type `VertexSet` is a model
- of the [SgiContainer] concept. The `value_type` of `VS` must be the
- the same as the `vertex_descriptor` of `G`.
+ *Requirements:* `c` is an object whose type `C` is a model of the
+ [SgiContainer] concept. The `value_type` of `C` must be the same type
+ as the `vertex_descriptor` of `G`.
]
]
]
-[heading C++0x]
-This concept is defined as:
-
- concept CliqueVisitor<typename T>
- {
- Graph graph_type;
-
- template<Container VertexSet>
- requires SameType<VertexSet::value_type, graph_type::vertex_descriptor>
- void T::cycle(const VertexSet&, graph_type&);
- };
-
+[heading Models]
+[cycle_visitor], [min_max_cycle_visitor]
[endsect]
Modified: trunk/libs/graph/quickbook/concepts/degree_measure.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/degree_measure.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/degree_measure.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -5,6 +5,8 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
+[/ TODO: Redefine this as a function taking a vertex and a graph. /]
+
[section Degree Measure]
The [DegreeMeasure] concept defines requirements for function objects
that are used in computations on the degree of a vertex.
Modified: trunk/libs/graph/quickbook/concepts/descriptor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/descriptor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/descriptor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -10,8 +10,7 @@
all graph types.
[heading Refinement Of]
-[SgiDefaultConstructible], [SgiCopyConstructible], [SgiAssignable], [SgiEqualityComparable],
-and [SgiLessThanComparable].
+[StdRegular] and [SgiLessThanComparable].
[heading Associated Types]
There are no associated types of a Descriptor.
Modified: trunk/libs/graph/quickbook/concepts/dfs_visitor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/dfs_visitor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/dfs_visitor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -94,6 +94,6 @@
]
[h4 Models]
-* [boost_dfs_visitor]
+* [dfs_visitor]
[endsect]
Modified: trunk/libs/graph/quickbook/concepts/dijkstra_visitor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/dijkstra_visitor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/dijkstra_visitor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -82,6 +82,6 @@
]
[h4 Models]
-* [dijkstra_visitor]
+* [boost_dijkstra_visitor]
[endsect]
Modified: trunk/libs/graph/quickbook/concepts/distance_measure.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/distance_measure.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/distance_measure.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -5,6 +5,8 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
+[/ TODO: Redefine this as a function taking some distance value and a graph. /]
+
[section Distance Measure]
The [DistanceMeasure] concept defines requirements for function objects
that are used in computations of distances.
Modified: trunk/libs/graph/quickbook/concepts/event_visitor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/event_visitor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/event_visitor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -9,26 +9,26 @@
This concept defines the interface for single-event visitors. An EventVisitor has an
/apply/ member function (`operator()`) which is invoked within the graph algorithm
at the event-point specified by the `event_filter` typedef within the type modeling
-the EventVisitor concept. EventVisitors can be combined into an [EventVistorList].
+the EventVisitor concept. EventVisitors can be combined into an [EventVisitorList].
The following is the list of event tags that can be invoked in Boost.Graph algorithms.
Each tag corresponds to a member function of the visitor for an algorithm. For example,
-the [BFSVisitor] of [[breadth_first_search] has a `cycle_edge()` member function.
-The corresponding tag is `on_cycle_edge`. The first argument in the event visitor's
-`operator()` must be either an edge or vertex depending on the event tag.
+the [BFSVisitor] has a `cycle_edge()` member function. The corresponding tag is
+`on_cycle_edge`. The first argument in the event visitor's `operator()` must be
+either an edge or vertex depending on the event tag.
[h4 Event Tags]
[table
[[Type] [Description]]
[
- [on_initialize_vertex]
+ [`on_initialize_vertex`]
[
An event tag corresponding to the initialization of a vertex. The parameter
type associated with this event is `vertex_descriptor`.
]
]
[
- [on_start_vertex]
+ [`on_start_vertex`]
[
In algorithms that without explicit starting points, this event tag
corresponds to the selection of a starting vertex. The parameter
@@ -36,7 +36,7 @@
]
]
[
- [on_discover_vertex]
+ [`on_discover_vertex`]
[
An event tag that corresponds to a vertex that is being used for
the first time. The parameter type associated with this event is
@@ -44,7 +44,7 @@
]
]
[
- [on_examine_edge]
+ [`on_examine_edge`]
[
An event tag that corresponds to the examination of edges for recently
discovered vertices. The parameter type associated with this event
@@ -52,7 +52,7 @@
]
]
[
- [on_tree_edge]
+ [`on_tree_edge`]
[
For algorithms whose iterations of a vertex set implicitly define a
tree (such as [[breadth_first_search] or [[depth_first_search]),
@@ -62,7 +62,7 @@
]
]
[
- [on_cycle_edge]
+ [`on_cycle_edge`]
[
For algorithms capable of detecting cycles in graphs such as
[[depth_first_search], this event tag is associated with discovery
@@ -71,7 +71,7 @@
]
]
[
- [on_forward_or_cross_edge]
+ [`on_forward_or_cross_edge`]
[
Forward and cross edges refer to types of edges that can be found by
different types of searches on graph (e.g., [[depth_first_search]).
@@ -81,7 +81,7 @@
]
]
[
- [on_back_edge]
+ [`on_back_edge`]
[
Back edges refer to types of edges that can be found by different types
of searches on a graph (e.g., [[breadth_first_search] and
@@ -91,7 +91,7 @@
]
]
[
- [on_finish_vertex]
+ [`on_finish_vertex`]
[
The inverse event of `on_discover_vertex`, this event tag corresponds to
the completion of an iteration of an algorithm that is operating on a
@@ -99,7 +99,7 @@
]
]
[
- [on_edge_relaxed]
+ [`on_edge_relaxed`]
[
For algorithms implementing edge relaxation (e.g.,
[[dijkstra_shortest_paths]), this event corresponds to the case
@@ -108,7 +108,7 @@
]
]
[
- [on_edge_not_relaxed]
+ [`on_edge_not_relaxed`]
[
For algorithms implementing edge relaxation (e.g.,
[[dijkstra_shortest_paths]), this event corresponds to the case
@@ -117,7 +117,7 @@
]
]
[
- [on_edge_minimized]
+ [`on_edge_minimized`]
[
For algorithms implementing edge minimization (e.g.,
[[bellman_ford_shortest_paths]), this event corresponds to the case
@@ -126,7 +126,7 @@
]
]
[
- [on_edge_not_minimized]
+ [`on_edge_not_minimized`]
[
For algorithms implementing edge minimization (e.g.,
[[bellman_ford_shortest_paths]), this event corresponds to the case
@@ -166,10 +166,10 @@
]
[h4 Models]
-* [[predecessor_recorder]
-* [[distance_recorder]
-* [[time_stamper]
-* [[property_writer]
-* [[null_visitor]
+* [predecessor_recorder]
+* [distance_recorder]
+* [time_stamper]
+* [property_writer]
+* [null_visitor]
[endsect]
Modified: trunk/libs/graph/quickbook/concepts/event_visitor_list.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/event_visitor_list.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/event_visitor_list.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -47,14 +47,14 @@
make_pair(open_paren(), close_paren());
-Next we want to pass this list into [[depth_first_search], but it is
+Next we want to pass this list into [depth_first_search], but it is
expecting a [DFSVisitor], not a [EventVisitorList]. We therefore use the [[dfs_visitor]
adaptor which turns an [EventVisitor] list into a [DFSVisitor]. Like all of the visitor
-adaptors, [dfs_visitor] has a creation function called [[make_dfs_visitor].
+adaptors, [dfs_visitor] has a creation function called [make_dfs_visitor].
make_dfs_visitor((open_paren(), close_paren()));
-Now we can pass the resulting visitor object into [[depth_first_search] as follows.
+Now we can pass the resulting visitor object into [depth_first_search] as follows.
depth_first_search(
G,
Modified: trunk/libs/graph/quickbook/concepts/graphs.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/graphs.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/graphs.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -105,27 +105,29 @@
[include mutable_property_graph.qbk]
[heading Pseudo-Concepts]
-The concepts above describe the type and functional requirements of graphs. However,
-these do not directly common concepts such as "directed graph" or "multigraph". As
-such, there are a number of pseudo-concepts with which we can also describe graph objects.
+The concepts above describe the syntactic and semantic requirements of graphs
+types. However, these do not directly address common graph notions such as
+"directed" graphs or "multigraphs". As such, there are a number of
+pseudo-concepts with which we can also describe graph objects.
[heading Directed and Undirected Graphs]
-The interface that Boost.Graph provides for accessing and manipulating an undirected
-graph is the same as the interface for directed graphs described in the following
-sections, however there are some differences in the behaviour and semantics. For example,
-in a directed graph we can talk about out-edges and in-edges of a vertex. In an
-undirected graph there is no "in" and "out", there are just edges incident to a vertex.
-Nevertheless, in Boost.Graph we still use the `out_edges()` function (or `in_edges()`)
-to access the incident edges in an undirected graph. Similarly, an undirected edge has
-no "source" and "target" but merely an unordered pair of vertices, but we still use
-`source()` and `target()` to access these vertices. The reason Boost.Graph does not
-provide a separate interface for undirected graphs is that many algorithms on directed
-graphs also work on undirected graphs, and it would be inconvenient to have to duplicate
-the algorithms just because of an interface difference. When using undirected graphs
-just mentally disregard the directionality in the function names. The example below
-demonstrates using the `out_edges()`, `source()`, and `target()` with an undirected
-graph. The source code for this example and the following one can be found in
-`examples/undirected.cpp`.
+The interface that Boost.Graph provides for accessing and manipulating an
+undirected graph is the same as the interface for directed graphs described in
+the following sections, however there are some differences in the behaviour and
+semantics. For example, in a directed graph we can talk about out-edges and
+in-edges of a vertex. In an undirected graph there is no "in" and "out", there
+are just edges incident to a vertex. Nevertheless, in Boost.Graph we still use
+the `out_edges()` function (or `in_edges()`) to access the incident edges in an
+undirected graph. Similarly, an undirected edge has no "source" and "target" but
+merely an unordered pair of vertices, but we still use `source()` and `target()`
+to access these vertices. The reason Boost.Graph does not provide a separate
+interface for undirected graphs is that many algorithms on directed graphs also
+work on undirected graphs, and it would be inconvenient to have to duplicate the
+algorithms just because of an interface difference. When using undirected graphs
+just mentally disregard the directionality in the function names. The example
+below demonstrates using the `out_edges()`, `source()`, and `target()` with an
+undirected graph. The source code for this example and the following one can be
+found in `examples/undirected.cpp`.
const int V = 2;
@@ -141,21 +143,22 @@
<< ")" << endl;
}
-Even though the interface is the same for undirected graphs, there are some behavioral
-differences because edge equality is defined differently. In a directed graph,
-edge /(u,v)/ is never equal to edge /(v,u)/, but in an undirected graph they may
-be equal. If the undirected graph is a multigraph then /(u,v)/ and /(v,u)/ might be
-parallel edges. If the graph is not a multigraph then /(u,v)/ and /(v,u)/ must be the
-same edge.
-
-In the example below the edge equality test will return false for the directed graph
-and true for the undirected graph. The difference also affects the meaning of `add_edge()`.
-In the example below, if we had also written `add_add(v, u, graph)`, this would have
-added a parallel edge between `u` and `v` (provided the graph type allows parallel edges -
-which most do). The difference in edge equality also affects the association of edge
-properties. In the directed graph, the edges /(u,v)/ and /(v,u)/ can have distinct
-weight values, whereas in the undirected graph the weight of /(u,v)/ is the same as
-the weight of /(v,u)/ since they are the same edge.
+Even though the interface is the same for undirected graphs, there are some
+behavioral differences because edge equality is defined differently. In a
+directed graph, edge /(u,v)/ is never equal to edge /(v,u)/, but in an
+undirected graph they may be equal. If the undirected graph is a multigraph then
+/(u,v)/ and /(v,u)/ might be parallel edges. If the graph is not a multigraph
+then /(u,v)/ and /(v,u)/ must be the same edge.
+
+In the example below the edge equality test will return false for the directed
+graph and true for the undirected graph. The difference also affects the meaning
+of `add_edge()`. In the example below, if we had also written `add_add(v, u,
+graph)`, this would have added a parallel edge between `u` and `v` (provided the
+graph type allows parallel edges - which most do). The difference in edge
+equality also affects the association of edge properties. In the directed graph,
+the edges /(u,v)/ and /(v,u)/ can have distinct weight values, whereas in the
+undirected graph the weight of /(u,v)/ is the same as the weight of /(v,u)/
+since they are the same edge.
typedef ... DirectedGraph;
typedef ... UndirectedGraph;
@@ -218,8 +221,8 @@
without any additional work.
There are certain sets of graph types that do not allow the addition of parallel edges.
-Specifically, if the EdgeList and OutEdgeList of an [adjacency_list] models an
-associative container, then the graph cannont be a multigraph.
+Specifically, if the EdgeList and OutEdgeList of an [adjacency_list] models
+[StdUniqueAssociativeContainer], then the graph cannont be a multigraph.
[heading Indexed Graphs]
Indexed graph provide a specific property, an index, for verticese, edges or both.
Modified: trunk/libs/graph/quickbook/concepts/incidence_graph.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/incidence_graph.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/incidence_graph.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -11,7 +11,7 @@
the graph.
[h4 Refinement Of]
-[BootGraph]
+[BoostGraph]
[h4 Associated Types]
[table
Modified: trunk/libs/graph/quickbook/concepts/numeric_value.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/numeric_value.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/numeric_value.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -5,6 +5,15 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
+[/ TODO: This concept is fundamentally broken. It's trying to capture the
+ / association of named constants with a type or a particular use. We probably
+ / need to explore the design space of named concepts before we can really
+ / attribute this as a legitimate operation.
+ /
+ / For example, why are these required to be scoped? Why not simply use the
+ / functions zero<T>() and infinity<T>()?
+ /]
+
[section Numeric Value]
The [NumericValue] concept describes requirements for a type to behave
as if it were numeric. This concept is generally used by algorithms that
@@ -20,12 +29,6 @@
zero and infinity. These are used within certain computations to represent
infinite and zero states.
-[heading Refinement Of]
-[StdRegularType], [StdAddable], [StdSubtractable], [StdMulitplicable],
-[StdDivisible].
-
-[note Why is numeric not a standard concept?]
-
[heading Notation]
The following expressions are used within this document:
[table
Modified: trunk/libs/graph/quickbook/concepts/utility.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/utility.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/utility.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -10,8 +10,14 @@
pertain explicitly to graphs or visitors for algorithms.
[include descriptor.qbk]
-[include numeric_value.qbk]
-[include degree_measure.qbk]
-[include distance_measure.qbk]
+
+[/ TODO: These concepts need some serious revisions, which means that the
+ algorithms requiring them need to be revised so that they don't need them or
+ use them in modified ways.
+]
+
+[/ [include numeric_value.qbk] ]
+[/ [include degree_measure.qbk] ]
+[/ [include distance_measure.qbk] ]
[endsect]
Modified: trunk/libs/graph/quickbook/concepts/vertex_index_graph.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/vertex_index_graph.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/vertex_index_graph.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -99,7 +99,7 @@
[
[Renumber Vertex Indices]
[`renumber_vertex_indices(g)`]
- []
+ [`void`]
[
Renumbers all vertices in the graph such that each vertex is in the
range \[0, `num_vertices(g)`).
Modified: trunk/libs/graph/quickbook/concepts/visitor.qbk
==============================================================================
--- trunk/libs/graph/quickbook/concepts/visitor.qbk (original)
+++ trunk/libs/graph/quickbook/concepts/visitor.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -6,15 +6,18 @@
/]
[section Visitor]
-This concept defines the basic requirements of all visitor concepts in the Boost.Graph
-library.
+The [Visitor] concept defines the basic requirements of all visitor concepts in
+the Boost.Graph library.
[h4 Refinement Of]
[SgiCopyConstructible]
[h4 Design Rationale]
-This concpet is provided primarily as a base concept for its refinements. Its sole purpose
-is to require that instances of concepts be copy-constructible, which is how they are
-passed to different graph algorithms.
+This concept is provided primarily as a base concept for its refinements. Its
+sole purpose is to require that instances of concepts be copy-constructible,
+which is how they are passed to different graph algorithms.
+Note that visitor types are most often constructed over references to other
+objects such as property maps or data local to the calling function. As such,
+most [Visitor] types are almost /never/ [SgiDefaultConstructible].
[endsect]
Modified: trunk/libs/graph/quickbook/guide/adjacency_list.qbk
==============================================================================
--- trunk/libs/graph/quickbook/guide/adjacency_list.qbk (original)
+++ trunk/libs/graph/quickbook/guide/adjacency_list.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -1,5 +1,5 @@
[/
- / Copyright (c) 2007 Andrew Sutton
+ / Copyright (c) 2007-2009 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)
@@ -21,7 +21,7 @@
Boost.Graph uses containers from the STL such as `std::vector`, `std::list`, and `std::set` to represent
the set of vertices and the adjacency structure (out-edges and in-edges) of the graph. There are several
-selector types that are used to specify the choice of container for `OutEdgeList` and `VertexList`.
+selector types that are used to specify the choice of container for `OutEdgeList` and `VertexList`.
* `vecS` selects `std::vector`.
* `listS` selects `std::list`.
@@ -41,40 +41,40 @@
per vertex.
[h4 Time Complexity of the VertexList]
-The choice of VertexList affects the time complexity of the following operations.
+The choice of VertexList affects the time complexity of the following operations.
[table VertexList Storage Options
- [[Operation] [Performance Considerations]]
- [
- [`add_vertex()`]
- [
- This operation is amortized constant time for both vecS and listS (implemented with
- `push_back()`). However, when the VertexList type is `vecS` the time for this operation
- is occasionally large because the vector will be reallocated and the whole graph copied
- but is still amortized constant time.
- ]
- ]
- [
- [`remove_vertex()`]
- [
- This operation is constant time for listS and O(V + E) for vecS. The large time
- complexity for vecS is because the vertex descriptors (which in this case are indices
- that correspond to the vertices' place in the vertex list) must be adjusted in the
- out-edges for the whole graph.
- ]
- ]
- [
- [`vertex()`]
- [
- This operation is constant time for vecS and for `listS`.
- ]
- ]
+ [[Operation] [Performance Considerations]]
+ [
+ [`add_vertex()`]
+ [
+ This operation is amortized constant time for both vecS and listS (implemented with
+ `push_back()`). However, when the VertexList type is `vecS` the time for this operation
+ is occasionally large because the vector will be reallocated and the whole graph copied
+ but is still amortized constant time.
+ ]
+ ]
+ [
+ [`remove_vertex()`]
+ [
+ This operation is constant time for listS and O(V + E) for vecS. The large time
+ complexity for vecS is because the vertex descriptors (which in this case are indices
+ that correspond to the vertices' place in the vertex list) must be adjusted in the
+ out-edges for the whole graph.
+ ]
+ ]
+ [
+ [`vertex()`]
+ [
+ This operation is constant time for vecS and for `listS`.
+ ]
+ ]
]
[h3 Choosing the OutEdgeList Type]
The OutEdgeList parameter determines what kind of container will be used to store the out-edges (and
possibly in-edges) for each vertex in the graph. The containers used for edge lists must either satisfy
-the requirements for Sequence or for AssociativeContainer.
+the requirements for Sequence or for AssociativeContainer.
One of the first things to consider when choosing the OutEdgeList is whether you want `adjacency_list` to
enforce the absence of parallel edges in the graph (that is, enforce that the graph not become a multi-graph).
@@ -82,96 +82,96 @@
multi-graph, or know that you will not be inserting parallel edges into the graph, then choose one of
the Sequence types: `vecS`, `listS`, or `slistS`. You will also want to take into account the differences in
time and space complexity for the various graph operations. Below we use V for the total number of vertices
-in the graph and E for the total number of edges. Operations not discussed here are constant time.
+in the graph and E for the total number of edges. Operations not discussed here are constant time.
[h4 Space Complexity of the OutEdgeList]
The selection of the OutEdgeList affects the amount of space overhead per edge in the graph object. In the
-order of least space to most space, the selectors are `vecS`, `slistS`, `listS`, and `setS`.
+order of least space to most space, the selectors are `vecS`, `slistS`, `listS`, and `setS`.
[h4 Time Complexity of the OutEdgeList]
In the following description of the time complexity for various operations, we use E/V inside of the "big-O"
notation to express the length of an out-edge list. Strictly speaking this is not accurate because E/V merely
gives the average number of edges per vertex in a random graph. The worst-case number of out-edges for a vertex
is V (unless it is a multi-graph). For sparse graphs E/V is typically much smaller than V and can be considered
-a constant.
+a constant.
[table OutEdgeList Storage Options
- [[Operation] [Performance Considerations]]
- [
- [`add_edge()`]
- [
- When the OutEdgeList is a UniqueAssociativeContainer like `std::set` the absence of
- parallel edges is enforced when an edge is added. The extra lookup involved has time
- complexity O(log(E/V)). The OutEdgeList types that model Sequence do not perform this
- check and therefore add_edge() is amortized constant time. This means that it if you
- don't care whether the graph has parallel edges, or know that the input to the
- graph does not contain them, then it is better to use the sequence-based OutEdgeList.
- The `add_edge()` for the sequence-based OutEdgeList is implemented with `push_front()`
- or `push_back()`. However, for `std::list` and `std::slist` this operation will
- typically be faster than with `std::vector` which occasionally reallocates
- and copies all elements.
- ]
- ]
- [
- [`remove_edge()`]
- [
- For sequence-based OutEdgeList types this operation is implemented with `std::remove_if()`
- which means the average time is E/V. For set-based OutEdgeList types this is implemented
- with the `erase()` member function, which has average time log(E/V).
- ]
- ]
- [
- [`edge()`]
- [
- The time complexity for this operation is O(E/V) when the OutEdgeList type is a Sequence
- and it is O(log(E/V)) when the OutEdgeList type is an AssociativeContainer.
- ]
- ]
- [
- [`clear_vertex()`]
- [
- For directed graphs with sequence-based OutEdgeList types the time complexity is O(V + E),
- while for associative container based OutEdgeList types the operation is faster, with
- time complexity O(V log(E/V)). For undirected graphs this operation is O(E2/V2) or
- O(E/V log(E/V)).
- ]
- ]
- [
- [`remove_vertex()`]
- [
- The time complexity for this operation is O(V + E) regardless of the OutEdgeList type.
- ]
- ]
- [
- [`out_edge_iterator::operator++()`]
- [
- This operation is constant time and exhibits a similar speed ordering as
- the `out_edge_iterator` with respect to the OutEdgeList selection.
- ]
- ]
-
- [
- [`in_edge_iterator::operator++()`]
- [
- This operation is constant time and fast (same speed as incrementing a pointer).
- The selection of OneD does not affect the speed of this operation.
- ]
- ]
- [
- [`vertex_iterator::operator++()`]
- [
- This operation is constant time and exhibits a similar speed ordering as the
- out_edge_iterator with respect to the OutEdgeList selection. Traversing through the
- whole edge set is O(V + E).
- ]
- ]
- [
- [`adjacency_iterator::operator++()`]
- [
- This operation is constant time and exhibits a similar speed ordering as
- the out_edge_iterator with respect to the OutEdgeList selection.
- ]
- ]
+ [[Operation] [Performance Considerations]]
+ [
+ [`add_edge()`]
+ [
+ When the OutEdgeList is a UniqueAssociativeContainer like `std::set` the absence of
+ parallel edges is enforced when an edge is added. The extra lookup involved has time
+ complexity O(log(E/V)). The OutEdgeList types that model Sequence do not perform this
+ check and therefore add_edge() is amortized constant time. This means that it if you
+ don't care whether the graph has parallel edges, or know that the input to the
+ graph does not contain them, then it is better to use the sequence-based OutEdgeList.
+ The `add_edge()` for the sequence-based OutEdgeList is implemented with `push_front()`
+ or `push_back()`. However, for `std::list` and `std::slist` this operation will
+ typically be faster than with `std::vector` which occasionally reallocates
+ and copies all elements.
+ ]
+ ]
+ [
+ [`remove_edge()`]
+ [
+ For sequence-based OutEdgeList types this operation is implemented with `std::remove_if()`
+ which means the average time is E/V. For set-based OutEdgeList types this is implemented
+ with the `erase()` member function, which has average time log(E/V).
+ ]
+ ]
+ [
+ [`edge()`]
+ [
+ The time complexity for this operation is O(E/V) when the OutEdgeList type is a Sequence
+ and it is O(log(E/V)) when the OutEdgeList type is an AssociativeContainer.
+ ]
+ ]
+ [
+ [`clear_vertex()`]
+ [
+ For directed graphs with sequence-based OutEdgeList types the time complexity is O(V + E),
+ while for associative container based OutEdgeList types the operation is faster, with
+ time complexity O(V log(E/V)). For undirected graphs this operation is O(E2/V2) or
+ O(E/V log(E/V)).
+ ]
+ ]
+ [
+ [`remove_vertex()`]
+ [
+ The time complexity for this operation is O(V + E) regardless of the OutEdgeList type.
+ ]
+ ]
+ [
+ [`out_edge_iterator::operator++()`]
+ [
+ This operation is constant time and exhibits a similar speed ordering as
+ the `out_edge_iterator` with respect to the OutEdgeList selection.
+ ]
+ ]
+
+ [
+ [`in_edge_iterator::operator++()`]
+ [
+ This operation is constant time and fast (same speed as incrementing a pointer).
+ The selection of OneD does not affect the speed of this operation.
+ ]
+ ]
+ [
+ [`vertex_iterator::operator++()`]
+ [
+ This operation is constant time and exhibits a similar speed ordering as the
+ out_edge_iterator with respect to the OutEdgeList selection. Traversing through the
+ whole edge set is O(V + E).
+ ]
+ ]
+ [
+ [`adjacency_iterator::operator++()`]
+ [
+ This operation is constant time and exhibits a similar speed ordering as
+ the out_edge_iterator with respect to the OutEdgeList selection.
+ ]
+ ]
]
[h2 Directed and Undirected Adjacency Lists]
@@ -194,7 +194,7 @@
Otherwise, we strongly suggest that you read about the bundled properties mechanism.]
One may specify internal properties via property lists, which are built from instances of the property class
-declared as follows.
+declared as follows.
template <class PropertyTag, class T, class NextProperty = no_property> struct property;
@@ -236,19 +236,19 @@
property objects of type T are held by-value inside of the graph.
The NextProperty parameter allows property types to be nested, so that an arbitrary number of properties
-can be attached to the same graph.
+can be attached to the same graph.
The following code shows how a vertex and edge property type can be assembled and used to create a graph type.
We have attached a distance property with values of type float and a name property with values of type
std::string to the vertices of the graph. We have attached a weight property with values of type float to
-the edges of the graph.
+the edges of the graph.
// specify property types fora graph
typedef property<vertex_distance_t, float, property<vertex_name_t, std::string> > VertexProperty;
typedef property<edge_weight_t, float> EdgeProperty;
// specify the graph has having the above properties
- typedef adjacency_list<mapS, vecS, undirectedS,
+ typedef adjacency_list<mapS, vecS, undirectedS,
VertexProperty, EdgeProperty> Graph;
// instantiate the graph with N (a compile-time constant integer) vertices
@@ -276,14 +276,14 @@
typedef edge_property_tag kind;
};
- struct capacity_t {
+ struct capacity_t {
typedef edge_property_tag kind;
};
You can also use enum's instead of struct's to create tag types. Create an enum type for each property.
The first part of the name of the enum type must be edge, vertex, or graph followed by an underscore,
the new property name, and a _t at the end. Inside the enum, define a value with the same name minus the
-_t. Then invoke the BOOST_INSTALL_PROPERTY macro.
+_t. Then invoke the BOOST_INSTALL_PROPERTY macro.
enum edge_flow_t { edge_flow };
enum edge_capacity_t { edge_capacity };
@@ -293,22 +293,22 @@
BOOST_INSTALL_PROPERTY(edge, capacity);
}
-Now you can use your new property tag in the definition of properties just as you would one of the builtin tags.
+Now you can use your new property tag in the definition of properties just as you would one of the builtin tags.
typedef property<capacity_t, int> Cap;
typedef property<flow_t, int, Cap> EdgeProperty;
typedef adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;
-Just as before, the property maps for these properties can be obtained from the graph via the get(Property, g) function.
+Just as before, the property maps for these properties can be obtained from the graph via the get(Property, g) function.
property_map<Graph, capacity_t>::type capacity = get(capacity_t(), G);
property_map<Graph, flow_t>::type flow = get(flow_t(), G);
-The file edge_property.cpp shows the complete source code for this example.
-
+The file edge_property.cpp shows the complete source code for this example.
+
[h3 Custom Vertex Properties]
Creating your own properties to attach to vertices is just as easy as for edges. Here we want to attach people's
-first names to the vertices in the graph.
+first names to the vertices in the graph.
struct first_name_t {
typedef vertex_property_tag kind;
@@ -319,15 +319,15 @@
names to the vertices. The edges will represent "who owes who";
typedef property<first_name_t, std::string> FirstNameProperty;
- typedef adjacency_list<vecS, vecS, directedS,
+ typedef adjacency_list<vecS, vecS, directedS,
FirstNameProperty> MyGraphType;
typedef pair<int,int> Pair;
- Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
- Pair(0,4), Pair(2,0), Pair(3,0),
- Pair(2,4), Pair(3,1), Pair(3,4),
+ Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
+ Pair(0,4), Pair(2,0), Pair(3,0),
+ Pair(2,4), Pair(3,1), Pair(3,4),
Pair(4,0), Pair(4,1) };
-
+
MyGraphType G(5);
for (int i = 0; i < 11; ++i) {
add_edge(edge_array[i].first, edge_array[i].second, G);
@@ -348,7 +348,7 @@
first-name property, we need to use the property_map traits class. The const_type is used since the graph
parameter is const. Once we have the property map type, we can deduce the value type of the property using
the property_traits class. In this example, we know that the property's value type will be `std::string`, but
-written in this generic fashion the `who_owes_who()` function could work with other property value types.
+written in this generic fashion the `who_owes_who()` function could work with other property value types.
template <class EdgeIter, class Graph>
void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
@@ -363,13 +363,13 @@
while (first != last) {
src_name = boost::get(name, source(*first, G));
targ_name = boost::get(name, target(*first, G));
- cout << src_name << " owes "
+ cout << src_name << " owes "
<< targ_name << " some money" << "\n";
++first;
}
}
-The output is:
+The output is:
Jeremy owes Rich some money
Jeremy owes Andrew some money
@@ -383,7 +383,7 @@
Kinis owes Jeremy some money
Kinis owes Rich some money
-The complete source code to this example is in the file interior_property_map.cpp.
+The complete source code to this example is in the file interior_property_map.cpp.
[h3 Customizing the Adjacency List Storage]
The `adjacency_list` is constructed out of two kinds of containers. One type of container to hold all the
@@ -426,7 +426,7 @@
just ValueType. For instance, you may want to supply the allocator type. One way to do this is to
hard-code in the extra parameters within the specialization of container_gen. However, if you want more
flexibility then you can add a template parameter to the selector class. In the code below we show how
-to create a selector that lets you specify the allocator to be used with the `std::list`.
+to create a selector that lets you specify the allocator to be used with the `std::list`.
template <class Allocator>
struct list_with_allocatorS { };
@@ -440,7 +440,7 @@
};
}
- // now you can define a graph using std::list and a specific allocator
+ // now you can define a graph using std::list and a specific allocator
typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
[h4 Push and Erase for the Custom Container]
@@ -465,12 +465,12 @@
c.erase(std::remove(c.begin(), c.end(), x), c.end());
}
-There are default `push()` and `erase()` functions implemented for the STL container types.
+There are default `push()` and `erase()` functions implemented for the STL container types.
[h4 Parallel Edge Traits]
When customizing the OutEdgeList, you must also specialize the `parallel_edge_traits` class to specify whether
the container type allows parallel edges (and is a Sequence) or if the container does not allow parallel
-edges (and is an AssociativeContainer).
+edges (and is an AssociativeContainer).
template <>
struct parallel_edge_traits<custom_containerS> {
Modified: trunk/libs/graph/quickbook/guide/directed_graph.qbk
==============================================================================
--- trunk/libs/graph/quickbook/guide/directed_graph.qbk (original)
+++ trunk/libs/graph/quickbook/guide/directed_graph.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -223,7 +223,7 @@
order. The `vertex_index_map()` named parameter is also required for the implementation.
After computation, we simply print the ordering to standard output.
-[h4 parallel Compilation]
+[h4 Parallel Compilation]
What if we have multiple processors available? Surely there is a way to determine if
we can compile several independent files simultaneously, thereby reducing the overall
build time. In fact, there is. Consider rephrasing the question to "what is the earliest
Modified: trunk/libs/graph/quickbook/guide/guide.qbk
==============================================================================
--- trunk/libs/graph/quickbook/guide/guide.qbk (original)
+++ trunk/libs/graph/quickbook/guide/guide.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -5,8 +5,16 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
+[/
+ / The user's guide encompasses non-reference documentation that includes
+ / overviews of graph theory, different graph implementations, etc. For all
+ / technical docuementation, see the concepts or reference material.
+ /]
+
[section User's Guide]
+[include theory.qbk]
+[include tour.qbk]
[include undirected_graph.qbk]
[include directed_graph.qbk]
[include adjacency_list.qbk]
Copied: trunk/libs/graph/quickbook/guide/theory.qbk (from r55957, /trunk/libs/graph/quickbook/theory.qbk)
==============================================================================
--- /trunk/libs/graph/quickbook/theory.qbk (original)
+++ trunk/libs/graph/quickbook/guide/theory.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -6,177 +6,210 @@
/]
[section Review of Elementary Graph Theory]
-This chapter is meant as a refresher on elementary graph theory. If the reader has some previous
-acquaintance with graph algorithms, this chapter should be enough to get started. If the reader
-has no previous background in graph algorithms we suggest a more thorough introduction such as
-/Introduction to Algorithms/ by Cormen, Leiserson, and Rivest.
+This chapter is meant as a refresher on elementary graph theory. If the reader
+has some previous acquaintance with graph algorithms, this chapter should be
+enough to get started. If the reader has no previous background in graph
+algorithms we suggest a more thorough introduction such as /Introduction to
+Algorithms/ by Cormen, Leiserson, and Rivest.
[h2 The Graph Abstraction]
-A graph is a mathematical abstraction that is useful for solving many kinds of problems. Fundamentally,
-a graph consists of a set of vertices, and a set of edges, where an edge is something that connects two
-vertices in the graph. More precisely, a graph is a pair (V,E), where V is a finite set and E is a binary
-relation on V. V is called a vertex set whose elements are called vertices. E is a collection of edges,
-where an edge is a pair (u,v) with u,v in V. In a directed graph, edges are ordered pairs, connecting a
-source vertex to a target vertex. In an undirected graph edges are unordered pairs and connect the two
-vertices in both directions, hence in an undirected graph (u,v) and (v,u) are two ways of writing the same
-edge.
-
-This definition of a graph is vague in certain respects; it does not say what a vertex or edge represents.
-They could be cities with connecting roads, or web-pages with hyperlinks. These details are left out of
-the definition of a graph for an important reason; they are not a necessary part of the graph abstraction.
-By leaving out the details we can construct a theory that is reusable, that can help us solve lots of
-different kinds of problems.
-
-Back to the definition: a graph is a set of vertices and edges. For purposes of demonstration, let us
-consider a graph where we have labeled the vertices with letters, and we write an edge simply as a pair
-of letters. Now we can write down an example of a directed graph as follows:
+A graph is a mathematical abstraction that is useful for solving many kinds of
+problems. Fundamentally, a graph consists of a set of vertices, and a set of
+edges, where an edge is something that connects two vertices in the graph. More
+precisely, a graph is a pair (V,E), where V is a finite set and E is a binary
+relation on V. V is called a vertex set whose elements are called vertices. E
+is a collection of edges, where an edge is a pair (u,v) with u,v in V. In a
+directed graph, edges are ordered pairs, connecting a source vertex to a target
+vertex. In an undirected graph edges are unordered pairs and connect the two
+vertices in both directions, hence in an undirected graph (u,v) and (v,u) are
+two ways of writing the same edge.
+
+This definition of a graph is vague in certain respects; it does not say what a
+vertex or edge represents. They could be cities with connecting roads, or
+web-pages with hyperlinks. These details are left out of the definition of a
+graph for an important reason; they are not a necessary part of the graph
+abstraction. By leaving out the details we can construct a theory that is
+reusable, that can help us solve lots of different kinds of problems.
+
+Back to the definition: a graph is a set of vertices and edges. For purposes of
+demonstration, let us consider a graph where we have labeled the vertices with
+letters, and we write an edge simply as a pair of letters. Now we can write down
+an example of a directed graph as follows:
G = (V, E)
- V = {v, b, x, z, a, y }
- E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) }
+ V = {v, b, x, z, a, y }
+ E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) }
-Figure 1 gives a pictorial view of this graph. The edge (x,x) is called a self-loop. Edges (b,y) and (b,y)
-are parallel edges, which are allowed in a multigraph (but are normally not allowed in a directed or
-undirected graph).
-
-[$../images/review_figure_1.png]
-
-Next we have a similar graph, though this time it is undirected. Figure 2 gives the pictorial view.
-Self loops are not allowed in undirected graphs. This graph is the undirected version(b,y)), meaning it
-has the same vertices and the same edges with their directions removed. Also the self edge has been
-removed, and edges such as (a,z) and (z,a) are collapsed into one edge. One can go the other way,
-and make a directed version of an undirected graph be replacing each edge by two edges, one pointing
-in each direction.
+Figure 1 gives a pictorial view of this graph. The edge (x,x) is called a
+self-loop. Edges (b,y) and (b,y) are parallel edges, which are allowed in a
+multigraph (but are normally not allowed in a directed or undirected graph).
+
+[$../../images/review_figure_1.png]
+
+Next we have a similar graph, though this time it is undirected. Figure 2 gives
+the pictorial view. Self loops are not allowed in undirected graphs. This graph
+is the undirected version(b,y)), meaning it has the same vertices and the same
+edges with their directions removed. Also the self edge has been removed, and
+edges such as (a,z) and (z,a) are collapsed into one edge. One can go the other
+way, and make a directed version of an undirected graph be replacing each edge
+by two edges, one pointing in each direction.
G = (V, E)
V = {v, b, x, z, a, y }
E = { (b,y), (y,v), (z,a), (b,x), (x,v) }
-[$../images/review_figure_2.png]
+[$../../images/review_figure_2.png]
-Now for some more graph terminology. If some edge (u,v) is in graph , then vertex v is adjacent to vertex u.
-In a directed graph, edge (u,v) is an out-edge of vertex u and an in-edge of vertex v. In an undirected graph
-edge (u,v) is incident on vertices u and v.
-
-In Figure 1, vertex y is adjacent to vertex b (but b is not adjacent to y). The edge (b,y) is an out-edge
-of b and an in-edge of y. In Figure 2, y is adjacent to b and vice-versa. The edge (y,b) is incident on
-vertices y and b.
-
-In a directed graph, the number of out-edges of a vertex is its out-degree and the number of in-edges is
-its in-degree. For an undirected graph, the number of edges incident to a vertex is its degree. In Figure 1,
-vertex b has an out-degree of 3 and an in-degree of zero. In Figure 2, vertex b simply has a degree of 2.
-
-Now a path is a sequence of edges in a graph such that the target vertex of each edge is the source vertex
-of the next edge in the sequence. If there is a path starting at vertex u and ending at vertex v we say
-that v is reachable from u. A path is simple if none of the vertices in the sequence are repeated. The
-path <(b,x), (x,v)> is simple, while the path <(a,z), (z,a)> is not. Also, the path <(a,z), (z,a)> is called
-a cycle because the first and last vertex in the path are the same. A graph with no cycles is acyclic.
-
-A planar graph is a graph that can be drawn on a plane without any of the edges crossing over each other.
-Such a drawing is called a plane graph. A face of a plane graph is a connected region of the plane
-surrounded by edges. An important property of planar graphs is that the number of faces, edges, and
-vertices are related through Euler's formula: |F| - |E| + |V| = 2. This means that a simple planar graph
-has at most O(|V|) edges.
+Now for some more graph terminology. If some edge (u,v) is in graph , then
+vertex v is adjacent to vertex u. In a directed graph, edge (u,v) is an out-edge
+of vertex u and an in-edge of vertex v. In an undirected graph edge (u,v) is
+incident on vertices u and v.
+
+In Figure 1, vertex y is adjacent to vertex b (but b is not adjacent to y). The
+edge (b,y) is an out-edge of b and an in-edge of y. In Figure 2, y is adjacent
+to b and vice-versa. The edge (y,b) is incident on vertices y and b.
+
+In a directed graph, the number of out-edges of a vertex is its out-degree and
+the number of in-edges is its in-degree. For an undirected graph, the number of
+edges incident to a vertex is its degree. In Figure 1, vertex b has an
+out-degree of 3 and an in-degree of zero. In Figure 2, vertex b simply has a
+degree of 2.
+
+Now a path is a sequence of edges in a graph such that the target vertex of each
+edge is the source vertex of the next edge in the sequence. If there is a path
+starting at vertex u and ending at vertex v we say that v is reachable from u. A
+path is simple if none of the vertices in the sequence are repeated. The path
+<(b,x), (x,v)> is simple, while the path <(a,z), (z,a)> is not. Also, the path
+<(a,z), (z,a)> is called a cycle because the first and last vertex in the path
+are the same. A graph with no cycles is acyclic.
+
+A planar graph is a graph that can be drawn on a plane without any of the edges
+crossing over each other. Such a drawing is called a plane graph. A face of a
+plane graph is a connected region of the plane surrounded by edges. An important
+property of planar graphs is that the number of faces, edges, and vertices are
+related through Euler's formula: |F| - |E| + |V| = 2. This means that a simple
+planar graph has at most O(|V|) edges.
[h2 Graph Data Structures]
-The primary property of a graph to consider when deciding which data structure to use is sparsity - the
-number of edges relative to the number of vertices in the graph. A graph where E is close to V2 is a
-/dense graph/, whereas a graph where E = alpha V and alpha is much smaller than V is a /sparse graph/. For
-dense graphs, the adjacency-matrix representation is usually the best choice, whereas for sparse graphs
-the adjacency-list representation is a better choice. Also the edge-list representation is a space efficient
-choice for sparse graphs that is appropriate in some situations.
+The primary property of a graph to consider when deciding which data structure
+to use is sparsity - the number of edges relative to the number of vertices in
+the graph. A graph where E is close to V2 is a /dense graph/, whereas a graph
+where E = alpha V and alpha is much smaller than V is a /sparse graph/. For
+dense graphs, the adjacency-matrix representation is usually the best choice,
+whereas for sparse graphs the adjacency-list representation is a better choice.
+Also the edge-list representation is a space efficient choice for sparse graphs
+that is appropriate in some situations.
[h3 Adjacency Matrix Representation]
-An adjacency-matrix representation of a graph is a 2-dimensional V x V array. Each element in the array
-auv stores a Boolean value saying whether the edge (u,v) is in the graph. Figure 3 depicts an adjacency
-matrix for the graph in Figure 1 (minus the parallel edge (b,y)). The ammount of space required to store
-an adjacency-matrix is O(V2). Any edge can be accessed, added, or removed in O(1) time. To add or remove
-a vertex requires reallocating and copying the whole graph, an O(V2) operation. The `adjacency_matrix<>`
-class implements the Boost.Graph interface in terms of the adjacency-matrix data structure.
+An adjacency-matrix representation of a graph is a 2-dimensional V x V array.
+Each element in the array auv stores a Boolean value saying whether the edge
+(u,v) is in the graph. Figure 3 depicts an adjacency matrix for the graph in
+Figure 1 (minus the parallel edge (b,y)). The ammount of space required to store
+an adjacency-matrix is O(V2). Any edge can be accessed, added, or removed in
+O(1) time. To add or remove a vertex requires reallocating and copying the whole
+graph, an O(V2) operation. The `adjacency_matrix<>` class implements the
+Boost.Graph interface in terms of the adjacency-matrix data structure.
[$../images/review_adjacency_matrix.gif]
[h3 Adjacency List Representation]
-An adjacency-list representation of a graph stores an out-edge sequence for each vertex. For sparse
-graphs this saves space since only O(V + E) memory is required. In addition, the out-edges for each
-vertex can be accessed more efficiently. Edge insertion is O(1), though accessing any given edge is
-O(alpha), where alpha is the sparsity factor of the matrix (which is equal to the maximum number of
-out-edges for any vertex in the graph). Figure 4 depicts an adjacency-list representation of the
-graph in Figure 1. The adjacency_list class is an implementation of the adjacency-list representation.
+An adjacency-list representation of a graph stores an out-edge sequence for each
+vertex. For sparse graphs this saves space since only O(V + E) memory is
+required. In addition, the out-edges for each vertex can be accessed more
+efficiently. Edge insertion is O(1), though accessing any given edge is
+O(alpha), where alpha is the sparsity factor of the matrix (which is equal to
+the maximum number of out-edges for any vertex in the graph). Figure 4 depicts
+an adjacency-list representation of the graph in Figure 1. The adjacency_list
+class is an implementation of the adjacency-list representation.
[$../images/review_adjacency_list.gif]
[h3 Edge List Representation]
-An edge-list representation of a graph is simply a sequence of edges, where each edge is represented
-as a pair of vertex ID's. The memory required is only O(E). Edge insertion is typically O(1), though
-accessing a particular edge is O(E) (not efficient). Figure 5 shows an edge-list representation of the
-graph in Figure 1. The edge_list adaptor class can be used to create implementations of the edge-list
-representation.
+An edge-list representation of a graph is simply a sequence of edges, where each
+edge is represented as a pair of vertex ID's. The memory required is only O(E).
+Edge insertion is typically O(1), though accessing a particular edge is O(E)
+(not efficient). Figure 5 shows an edge-list representation of the graph in
+Figure 1. The edge_list adaptor class can be used to create implementations of
+the edge-list representation.
[$../images/review_edge_list.gif]
[h3 Other Respresentations]
-Add something here to discuss optimized storage options for the graph. Specifically, we might
-mention the compressed-sparse-row graph representation and its possible uses.
+Add something here to discuss optimized storage options for the graph.
+Specifically, we might mention the compressed-sparse-row graph representation
+and its possible uses.
[h2 Graph Algorithms]
-Like all data structures, there are numerous algorithms that operate on them to solve various problems.
-In fact, there are often several different approaches to solving the same problem, each with different
-properties and complexities when running on graphs with different properties (e.g., directed vs. undirected
-or sparse vs. dense). The following sections briefly discuss a few such problems and algorithms.
+Like all data structures, there are numerous algorithms that operate on them to
+solve various problems. In fact, there are often several different approaches to
+solving the same problem, each with different properties and complexities when
+running on graphs with different properties (e.g., directed vs. undirected or
+sparse vs. dense). The following sections briefly discuss a few such problems
+and algorithms.
[h3 Graph Search Algorithms]
-Tree edges are edges in the search tree (or forest) constructed (implicitly or explicitly) by running a
-graph search algorithm over a graph. An edge (u,v) is a tree edge if v was first discovered while
-exploring (corresponding to the visitor explore() method) edge (u,v). Back edges connect vertices to
-their ancestors in a search tree. So for edge (u,v) the vertex v must be the ancestor of vertex u. Self
-loops are considered to be back edges. Forward edges are non-tree edges (u,v) that connect a vertex u
-to a descendant v in a search tree. Cross edges are edges that do not fall into the above three categories.
+Tree edges are edges in the search tree (or forest) constructed (implicitly or
+explicitly) by running a graph search algorithm over a graph. An edge (u,v) is a
+tree edge if v was first discovered while exploring (corresponding to the
+visitor explore() method) edge (u,v). Back edges connect vertices to their
+ancestors in a search tree. So for edge (u,v) the vertex v must be the ancestor
+of vertex u. Self loops are considered to be back edges. Forward edges are
+non-tree edges (u,v) that connect a vertex u to a descendant v in a search tree.
+Cross edges are edges that do not fall into the above three categories.
[h4 Breadth-First Search]
-Breadth-first search (BFS) is a traversal through a graph that touches all of the vertices reachable
-from a particular source vertex. In addition, the order of the traversal is such that the algorithm
-will explore all of the neighbors of a vertex before proceeding on to the neighbors of its neighbors.
-One way to think of breadth-first search is that it expands like a wave emanating from a stone dropped
-into a pool of water. Vertices in the same ``wave'' are the same distance from the source vertex. A
-vertex is discovered the first time it is encountered by the algorithm. A vertex is finished after
-all of its neighbors are explored. Here's an example to help make this clear. A graph is shown in
-Figure 6 and the BFS discovery and finish order for the vertices is shown below.
+Breadth-first search (BFS) is a traversal through a graph that touches all of
+the vertices reachable from a particular source vertex. In addition, the order
+of the traversal is such that the algorithm will explore all of the neighbors of
+a vertex before proceeding on to the neighbors of its neighbors. One way to
+think of breadth-first search is that it expands like a wave emanating from a
+stone dropped into a pool of water. Vertices in the same "wave" are the same
+distance from the source vertex. A vertex is discovered the first time it is
+encountered by the algorithm. A vertex is finished after all of its neighbors
+are explored. Here's an example to help make this clear. A graph is shown in
+Figure 6 and the BFS discovery and finish order for the vertices is shown below.
[$../images/review_bfs.gif]
- order of discovery: s r w v t x u y
+ order of discovery: s r w v t x u y
order of finish: s r w v t x u y
-We start at vertex , and first visit r and w (the two neighbors of ). Once both neighbors of are visited,
-we visit the neighbor of r (vertex v), then the neighbors of w (the discovery order between r and w does
-not matter) which are t and x. Finally we visit the neighbors of t and x, which are u and y.
-
-For the algorithm to keep track of where it is in the graph, and which vertex to visit next, BFS needs
-to color the vertices (see the section on Property Maps for more details about attaching properties to
-graphs). The place to put the color can either be inside the graph, or it can be passed into the algorithm
-as an argument.
+We start at vertex , and first visit r and w (the two neighbors of ). Once both
+neighbors of are visited, we visit the neighbor of r (vertex v), then the
+neighbors of w (the discovery order between r and w does not matter) which are t
+and x. Finally we visit the neighbors of t and x, which are u and y.
+
+For the algorithm to keep track of where it is in the graph, and which vertex to
+visit next, BFS needs to color the vertices (see the section on Property Maps
+for more details about attaching properties to graphs). The place to put the
+color can either be inside the graph, or it can be passed into the algorithm as
+an argument.
[h4 Depth-First Search]
-A depth-first search (DFS) visits all the vertices in a graph. When choosing which edge to explore next,
-this algorithm always chooses to go ``deeper'' into the graph. That is, it will pick the next adjacent
-unvisited vertex until reaching a vertex that has no unvisited adjacent vertices. The algorithm will then
-backtrack to the previous vertex and continue along any as-yet unexplored edges from that vertex. After DFS
-has visited all the reachable vertices from a particular source vertex, it chooses one of the remaining
-undiscovered vertices and continues the search. This process creates a set of depth-first trees which together
-form the depth-first forest. A depth-first search categorizes the edges in the graph into three categories:
-tree-edges, back-edges, and forward or cross-edges (it does not specify which). There are typically many
-valid depth-first forests for a given graph, and therefore many different (and equally valid) ways to
-categorize the edges.
-
-One interesting property of depth-first search is that the discover and finish times for each vertex form
-a parenthesis structure. If we use an open-parenthesis when a vertex is discovered, and a close-parenthesis
-when a vertex is finished, then the result is a properly nested set of parenthesis. Figure 7 shows DFS applied
-to an undirected graph, with the edges labeled in the order they were explored. Below we list the vertices of
-the graph ordered by discover and finish time, as well as show the parenthesis structure. DFS is used as the
-kernel for several other graph algorithms, including topological sort and two of the connected component
-algorithms. It can also be used to detect cycles (see the Cylic Dependencies section of the File Dependency
-Example).
+A depth-first search (DFS) visits all the vertices in a graph. When choosing
+which edge to explore next, this algorithm always chooses to go "deeper" into
+the graph. That is, it will pick the next adjacent unvisited vertex until
+reaching a vertex that has no unvisited adjacent vertices. The algorithm will
+then backtrack to the previous vertex and continue along any as-yet unexplored
+edges from that vertex. After DFS has visited all the reachable vertices from a
+particular source vertex, it chooses one of the remaining undiscovered vertices
+and continues the search. This process creates a set of depth-first trees which
+together form the depth-first forest. A depth-first search categorizes the edges
+in the graph into three categories: tree-edges, back-edges, and forward or
+cross-edges (it does not specify which). There are typically many valid
+depth-first forests for a given graph, and therefore many different (and equally
+valid) ways to categorize the edges.
+
+One interesting property of depth-first search is that the discover and finish
+times for each vertex form a parenthesis structure. If we use an
+open-parenthesis when a vertex is discovered, and a close-parenthesis when a
+vertex is finished, then the result is a properly nested set of parenthesis.
+Figure 7 shows DFS applied to an undirected graph, with the edges labeled in the
+order they were explored. Below we list the vertices of the graph ordered by
+discover and finish time, as well as show the parenthesis structure. DFS is used
+as the kernel for several other graph algorithms, including topological sort and
+two of the connected component algorithms. It can also be used to detect cycles
+(see the Cylic Dependencies section of the File Dependency Example).
[$../images/review_dfs.gif]
@@ -185,68 +218,78 @@
parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)
[h4 Minimum Spanning Tree Problem]
-The minimum-spanning-tree (MST) problem is defined as follows: Given a graph /G=(V,E)/ find an acyclic
-subset /T/ of /E/ that connects all of the vertices in the graph and whose total weight is minimized, where
-the total weight is given by
+The minimum-spanning-tree (MST) problem is defined as follows: Given a graph
+/G=(V,E)/ find an acyclic subset /T/ of /E/ that connects all of the vertices in
+the graph and whose total weight is minimized, where the total weight is given
+by
-/w(T)/ = sum of /w(u,v)/ over all /(u,v)/ in T, where /w(u,v)/ is the weight on the edge /(u,v)/.
+/w(T)/ = sum of /w(u,v)/ over all /(u,v)/ in T, where /w(u,v)/ is the weight on
+the edge /(u,v)/.
-/T/ is called the minimum spanning tree of /G/. It is important to note that a graph may have multiple MSTs.
+/T/ is called the minimum spanning tree of /G/. It is important to note that a
+graph may have multiple MSTs.
[h4 Shortest-Paths Algorithms]
-One of the classic problems in graph theory is to find the shortest path between two vertices in a graph.
-Formally, a path is a sequence of vertices <v0,v1,...,vk> in a graph G = (V, E) such that each vertex is
-connected to the next vertex in the sequence (the edges (vi,vi+1) for i=0,1,...,k-1 are in the edge set E).
-In the shortest-path problem, each edge is given a real-valued weight. We can therefore talk about the weight
-of a path
-
+One of the classic problems in graph theory is to find the shortest path between
+two vertices in a graph. Formally, a path is a sequence of vertices
+<v0,v1,...,vk> in a graph G = (V, E) such that each vertex is connected to the
+next vertex in the sequence (the edges (vi,vi+1) for i=0,1,...,k-1 are in the
+edge set E). In the shortest-path problem, each edge is given a real-valued
+weight. We can therefore talk about the weight of a path
+
/w(p)/ = sum from /i=1..k/ of /w(vi-1,vi)/
-The shortest path weight from vertex /u/ to /v/ is then
+The shortest path weight from vertex /u/ to /v/ is then
-/delta(u,v)/ = min /{ w(p) : u --> v }/ if there is a path from u to v
-/delta(u,v)/ = infinity otherwise.
+/delta(u,v)/ = min /{ w(p) : u --> v }/ if there is a path from u to v
+/delta(u,v)/ = infinity otherwise.
-A shortest path is any path who's path weight is equal to the shortest path weight. So there may be several
-shortest paths within the same graph.
+A shortest path is any path who's path weight is equal to the shortest path
+weight. So there may be several shortest paths within the same graph.
-There are several variants of the shortest path problem. Above we defined the single-pair problem, but there
-is also the single-source problem (all shortest paths from one vertex to every other vertex in the graph),
-the equivalent single-destination problem, and the all-pairs problem. It turns out that there are no
-algorithms for solving the single-pair problem that are asymptotically faster than algorithms that solve
-the single-source problem.
-
-A shortest-paths tree rooted at vertex in graph /G=(V,E)/ is a directed subgraph where /V'/ is a subset of
-/V/ and /E'/ is a subset of /(E, V')/ is the set of vertices reachable from , /G'/ forms a rooted tree with
-root , and for all /v/ in /V'/ the unique simple path from to /v/ in /G'/ is a shortest path from to /v/ in
-/G/. The result of a single-source algorithm is a shortest-paths tree.
+There are several variants of the shortest path problem. Above we defined the
+single-pair problem, but there is also the single-source problem (all shortest
+paths from one vertex to every other vertex in the graph), the equivalent
+single-destination problem, and the all-pairs problem. It turns out that there
+are no algorithms for solving the single-pair problem that are asymptotically
+faster than algorithms that solve the single-source problem.
+
+A shortest-paths tree rooted at vertex in graph /G=(V,E)/ is a directed subgraph
+ where /V'/ is a subset of /V/ and /E'/ is a subset of /(E, V')/ is the set of
+vertices reachable from , /G'/ forms a rooted tree with root , and for all /v/
+in /V'/ the unique simple path from to /v/ in /G'/ is a shortest path from to
+/v/ in /G/. The result of a single-source algorithm is a shortest-paths tree.
[h4 Network Flow Algorithms]
-A flow network is a directed graph /G=(V,E)/ with a source vertex /s/ and a sink vertex /t/. Each edge has
-a positive real valued capacity function c and there is a flow function f defined over every vertex pair.
-The flow function must satisfy three contraints:
+A flow network is a directed graph /G=(V,E)/ with a source vertex /s/ and a sink
+vertex /t/. Each edge has a positive real valued capacity function c and there
+is a flow function f defined over every vertex pair. The flow function must
+satisfy three contraints:
-* /f(u,v) <= c(u,v)/ for all /(u,v)/ in /V/x /V/ (Capacity constraint)
+* /f(u,v) <= c(u,v)/ for all /(u,v)/ in /V/x /V/ (Capacity constraint)
* /f(u,v) = -f(v,u)/ for all /(u,v)/ in /V/ x /V/ (Skew symmetry)
-* sum /v/ in /V/ /f(u,v)/ = 0 for all /u/ in /V/ - /{s,t}/ (Flow conservation)
+* sum /v/ in /V/ /f(u,v)/ = 0 for all /u/ in /V/ - /{s,t}/ (Flow conservation)
-The flow of the network is the net flow entering the sink vertex t (which is equal to the net flow leaving
-the source vertex s).
+The flow of the network is the net flow entering the sink vertex t (which is
+equal to the net flow leaving the source vertex s).
/|f|/ = sum /u/ in /V/ /f(u,t)/ = sum /v/ in /V/ /f(s,v)/
-The residual capacity of an edge is /r(u,v)/ = /c(u,v) - f(u,v)/. The edges with /r(u,v) > 0/ are residual
-edges /Ef/ which induce the residual graph /Gf = (V, Ef)/. An edge with /r(u,v) = 0/ is saturated.
-
-The maximum flow problem is to determine the maximum possible value for |/f/| and the corresponding flow
-values for every vertex pair in the graph. A flow network is shown in Figure 8. Vertex A is the source
-vertex and H is the target vertex.
+The residual capacity of an edge is /r(u,v)/ = /c(u,v) - f(u,v)/. The edges with
+/r(u,v) > 0/ are residual edges /Ef/ which induce the residual graph /Gf = (V,
+Ef)/. An edge with /r(u,v) = 0/ is saturated.
+
+The maximum flow problem is to determine the maximum possible value for |/f/|
+and the corresponding flow values for every vertex pair in the graph. A flow
+network is shown in Figure 8. Vertex A is the source vertex and H is the target
+vertex.
[$../images/review_flow.gif]
-Edges are labeled with the flow and capacity values. There is a long history of algorithms for solving the
-maximum flow problem, with the first algorithm due to Ford and Fulkerson. The best general purpose algorithm
-to date is the push-relabel algorithm of Goldberg which is based on the notion of a preflow introduced by
-Karzanov.
+Edges are labeled with the flow and capacity values. There is a long history of
+algorithms for solving the maximum flow problem, with the first algorithm due to
+Ford and Fulkerson. The best general purpose algorithm to date is the
+push-relabel algorithm of Goldberg which is based on the notion of a preflow
+introduced by Karzanov.
[endsect]
\ No newline at end of file
Copied: trunk/libs/graph/quickbook/guide/tour.qbk (from r55957, /trunk/libs/graph/quickbook/tour.qbk)
==============================================================================
--- /trunk/libs/graph/quickbook/tour.qbk (original)
+++ trunk/libs/graph/quickbook/guide/tour.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -6,6 +6,10 @@
/]
[section A Quick tour of Boost.Graph]
+
+[note This guide is taken from the old BGL documentation and may not reflect
+current or best practice.]
+
The domain of graph data structures and algorithms is in some respects more
complicated than that of containers. The abstract iterator interface used by
STL is not sufficiently rich to encompass the numerous ways that graph
@@ -33,10 +37,6 @@
the example program will also be listed.
[h2 Constructing the Graph]
-
-In this example
-
-[h2 Constructing the Graph]
In this example we will use the [adjacency_list] class to demonstrate the main
ideas in the Boost.Graph interface. The [adjacency_list] class provides a
generalized version of the classic /adjacency list/ data structure. The
@@ -108,20 +108,23 @@
[remove_vertex] functions, also of the [MutableGraph] interface.
[h2 Accessing the Vertex Set]
-Now that we have created a graph, we can use the graph interface to access the graph data in
-different ways. First we can access all of the vertices in the graph using the `vertices()` function
-of the /VertexListGraph/ interface. This function returns a `std::pair<>` of vertex iterators (the first
-iterator points to the "beginning" of the vertices and the second iterator points "past the end").
-Dereferencing a vertex iterator gives a vertex object. The type of the vertex iterator is given by
-the graph_traits class. Note that different graph classes can have different associated vertex
-iterator types, which is why we need the `graph_traits<>` class. Given some graph type, the `graph_traits<>`
+Now that we have created a graph, we can use the graph interface to access the
+graph data in different ways. First we can access all of the vertices in the
+graph using the `vertices()` function of the /VertexListGraph/ interface. This
+function returns a `std::pair<>` of vertex iterators (the first iterator points
+to the "beginning" of the vertices and the second iterator points "past the
+end"). Dereferencing a vertex iterator gives a vertex object. The type of the
+vertex iterator is given by the graph_traits class. Note that different graph
+classes can have different associated vertex iterator types, which is why we
+need the `graph_traits<>` class. Given some graph type, the `graph_traits<>`
class will provide access to the vertex_iterator type.
-The following example prints out the index for each of the vertices in the graph. All vertex and
-edge properties, including index, are accessed via property map objects. The `property_map<>` class is
-used to obtain the property map type for a specific property (specified by `vertex_index_t`, one of the
-Boost.Graph predefined properties) and function call `get(vertex_index, g)` returns the actual
-property map object.
+The following example prints out the index for each of the vertices in the
+graph. All vertex and edge properties, including index, are accessed via
+property map objects. The `property_map<>` class is used to obtain the property
+map type for a specific property (specified by `vertex_index_t`, one of the
+Boost.Graph predefined properties) and function call `get(vertex_index, g)`
+returns the actual property map object.
// ...
@@ -152,14 +155,16 @@
]
[h2 Accessing the Edge Set]
-The set of edges for a graph can be accessed with the edges() function of the /EdgeListGraph/ interface.
-Similar to the `vertices()` function, this returns a pair of iterators, but in this case the iterators
-are edge iterators. Dereferencing an edge iterator gives an edge object. The `source()` and `target()`
-functions return the two vertices that are connected by the edge. Instead of explicitly creating a
-`std::pair<>` for the iterators, this time we will use the `tie()` helper function. This handy function
-can be used to assign the parts of a std::pair into two separate variables, in this case `ei`
-and `ei_end`. This is usually more convenient than creating a `std::pair` and is our method of
-choice for Boost.Graph.
+The set of edges for a graph can be accessed with the edges() function of the
+/EdgeListGraph/ interface. Similar to the `vertices()` function, this returns a
+pair of iterators, but in this case the iterators are edge iterators.
+Dereferencing an edge iterator gives an edge object. The `source()` and
+`target()` functions return the two vertices that are connected by the edge.
+Instead of explicitly creating a `std::pair<>` for the iterators, this time we
+will use the `tie()` helper function. This handy function can be used to assign
+the parts of a std::pair into two separate variables, in this case `ei` and
+`ei_end`. This is usually more convenient than creating a `std::pair` and is our
+method of choice for Boost.Graph.
// ...
int main(int,char*[])
@@ -182,11 +187,12 @@
]
[h2 The Adjacency Structure]
-In the next few examples we will explore the adjacency structure of the graph from the point of
-view of a particular vertex. We will look at the vertices' in-edges, out-edges, and its adjacent
-vertices. We will encapsulate this in an "exercise vertex" function, and apply it to each vertex
-in the graph. To demonstrate the STL-interoperability of Boost.Graph, we will use the STL `for_each()`
-function to iterate through the vertices and apply the function.
+In the next few examples we will explore the adjacency structure of the graph
+from the point of view of a particular vertex. We will look at the vertices'
+in-edges, out-edges, and its adjacent vertices. We will encapsulate this in an
+"exercise vertex" function, and apply it to each vertex in the graph. To
+demonstrate the STL-interoperability of Boost.Graph, we will use the STL
+`for_each()` function to iterate through the vertices and apply the function.
//...
int main(int,char*[])
@@ -196,11 +202,12 @@
return 0;
}
-We use a functor for exercise_vertex instead of just a function because the graph object will be
-needed when we access information about each vertex; using a functor gives us a place to keep a
-reference to the graph object during the execution of the `std::for_each()`. Also we template the
-functor on the graph type so that it is reusable with different graph classes. Here is the start
-of the exercise_vertex functor:
+We use a functor for exercise_vertex instead of just a function because the
+graph object will be needed when we access information about each vertex; using
+a functor gives us a place to keep a reference to the graph object during the
+execution of the `std::for_each()`. Also we template the functor on the graph
+type so that it is reusable with different graph classes. Here is the start of
+the exercise_vertex functor:
template <class Graph> struct exercise_vertex {
exercise_vertex(Graph& g_) : g(g_)
@@ -239,14 +246,16 @@
};
[h3 Out-Edges, In-Edges, and Edge Descriptors]
-The out-edges of a vertex are accessed with the `out_edges()` function of the /IncidenceGraph/
-interface. The out_edges() function takes two arguments: the first argument is the vertex and
-the second is the graph object. The function returns a pair of iterators which provide access
-to all of the out-edges of a vertex (similar to how the vertices() function returned a pair of
-iterators). The iterators are called out-edge iterators and dereferencing one of these iterators
-gives an edge descriptor object. An edge descriptor plays the same kind of role as the vertex
-descriptor object, it is a "black box" provided by the graph type. The following code snippet prints
-the source-target pairs for each out-edge of vertex, v.
+The out-edges of a vertex are accessed with the `out_edges()` function of the
+/IncidenceGraph/ interface. The out_edges() function takes two arguments: the
+first argument is the vertex and the second is the graph object. The function
+returns a pair of iterators which provide access to all of the out-edges of a
+vertex (similar to how the vertices() function returned a pair of iterators).
+The iterators are called out-edge iterators and dereferencing one of these
+iterators gives an edge descriptor object. An edge descriptor plays the same
+kind of role as the vertex descriptor object, it is a "black box" provided by
+the graph type. The following code snippet prints the source-target pairs for
+each out-edge of vertex, v.
template <class Graph>
struct exercise_vertex {
@@ -279,10 +288,11 @@
out-edges: (0,1) (0,2) (0,3) (0,4)
]
-The `in_edges()` function of the BidirectionalGraph interface provides access to all the in-edges
-of a vertex through in-edge iterators. The in_edges() function is only available for the
-`adjacency_list<>` if `bidirectionalS` is supplied for the Directed template parameter. There is an
-extra cost in space when `bidirectionalS` is specified instead of `directedS`.
+The `in_edges()` function of the BidirectionalGraph interface provides access to
+all the in-edges of a vertex through in-edge iterators. The in_edges() function
+is only available for the `adjacency_list<>` if `bidirectionalS` is supplied for
+the Directed template parameter. There is an extra cost in space when
+`bidirectionalS` is specified instead of `directedS`.
template <class Graph> struct exercise_vertex {
// ... continued from above
@@ -311,12 +321,13 @@
]
[h3 Adjacent Vertices]
-Given the out-edges of a vertex, the target vertices of these edges are adjacent to the source
-vertex. Sometimes an algorithm does not need to look at the edges of the graph and only cares
-about the vertices. Therefore the graph interface also includes the `adjacent_vertices()` function
-of the AdjacencyGraph interface which provides direct access to the adjacent vertices. This function
-returns a pair of adjacency iterators. Dereferencing an adjacency iterator gives a vertex descriptor
-for an adjacent vertex.
+Given the out-edges of a vertex, the target vertices of these edges are adjacent
+to the source vertex. Sometimes an algorithm does not need to look at the edges
+of the graph and only cares about the vertices. Therefore the graph interface
+also includes the `adjacent_vertices()` function of the AdjacencyGraph interface
+which provides direct access to the adjacent vertices. This function returns a
+pair of adjacency iterators. Dereferencing an adjacency iterator gives a vertex
+descriptor for an adjacent vertex.
template <class Graph> struct exercise_vertex {
// ... continued from above
@@ -342,41 +353,50 @@
]
[Adding Some Color to your Graph]
-Boost.Graph attempts to be as flexible as possible in terms of accommodating how properties are
-attached to a graph. For instance, a property such as edge weight may need to be used throughout
-a graph object's lifespan and therefore it would be convenient to have the graph object also manage
-the property storage. On the other hand, a property like vertex color may only be needed for the
-duration of a single algorithm, and it would be better to have the property stored separately from
-the graph object. The first kind of property is called an internally stored property while the second
-kind is called an externally stored property. Boost.Graph uses a uniform mechanism to access both kinds of
-properties inside its graph algorithms called the property map interface, described in Section
-Property Map Concepts. In addition, the PropertyGraph concept defines the interface for obtaining
-a property map object for an internally stored property.
-
-The Boost.Graph adjacency_list class allows users to specify internally stored properties through plug-in
-template parameters of the graph class. How to do this is discussed in detail in Section Internal
-Properties. Externally stored properties can be created in many different ways, although they are
-ultimately passed as separate arguments to the graph algorithms. One straightforward way to store
-properties is to create an array indexed by vertex or edge index. In the adjacency_list with `vecS`
-specified for the VertexList template parameter, vertices are automatically assigned indices, which
-can be accessed via the property map for the vertex_index_t. Edges are not automatically assigned
-indices. However the property mechanism can be used to attach indices to the edges which can be
-used to index into other externally stored properties.
-
-In the following example, we construct a graph and apply `dijkstra_shortest_paths()`. The complete
-source code for the example is in examples/dijkstra-example.cpp. Dijkstra's algorithm computes the
-shortest distance from the starting vertex to every other vertex in the graph.
-
-Dijkstra's algorithm requires that a weight property is associated with each edge and a distance
-property with each vertex. Here we use an internal property for the weight and an external property
-for the distance. For the weight property we use the property class and specify int as the type used
-to represent weight values and edge_weight_t for the property tag (which is one of the Boost.Graph
-predefined property tags). The weight property is then used as a template argument for `adjacency_list<>`.
-The listS and vecS types are selectors that determine the data structure used inside the
-`adjacency_list<>` (see Section Choosing the Edgelist and VertexList). The directedS type specifies
-that the graph should be directed (versus undirected). The following code shows the specification of
-the graph type and then the initialization of the graph. The edges and weights are passed to the
-graph constructor in the form of iterators (a pointer qualifies as a /RandomAccessIterator/).
+Boost.Graph attempts to be as flexible as possible in terms of accommodating how
+properties are attached to a graph. For instance, a property such as edge weight
+may need to be used throughout a graph object's lifespan and therefore it would
+be convenient to have the graph object also manage the property storage. On the
+other hand, a property like vertex color may only be needed for the duration of
+a single algorithm, and it would be better to have the property stored
+separately from the graph object. The first kind of property is called an
+internally stored property while the second kind is called an externally stored
+property. Boost.Graph uses a uniform mechanism to access both kinds of
+properties inside its graph algorithms called the property map interface,
+described in Section Property Map Concepts. In addition, the PropertyGraph
+concept defines the interface for obtaining a property map object for an
+internally stored property.
+
+The Boost.Graph adjacency_list class allows users to specify internally stored
+properties through plug-in template parameters of the graph class. How to do
+this is discussed in detail in Section Internal Properties. Externally stored
+properties can be created in many different ways, although they are ultimately
+passed as separate arguments to the graph algorithms. One straightforward way to
+store properties is to create an array indexed by vertex or edge index. In the
+adjacency_list with `vecS` specified for the VertexList template parameter,
+vertices are automatically assigned indices, which can be accessed via the
+property map for the vertex_index_t. Edges are not automatically assigned
+indices. However the property mechanism can be used to attach indices to the
+edges which can be used to index into other externally stored properties.
+
+In the following example, we construct a graph and apply
+`dijkstra_shortest_paths()`. The complete source code for the example is in
+examples/dijkstra-example.cpp. Dijkstra's algorithm computes the shortest
+distance from the starting vertex to every other vertex in the graph.
+
+Dijkstra's algorithm requires that a weight property is associated with each
+edge and a distance property with each vertex. Here we use an internal property
+for the weight and an external property for the distance. For the weight
+property we use the property class and specify int as the type used to represent
+weight values and edge_weight_t for the property tag (which is one of the
+Boost.Graph predefined property tags). The weight property is then used as a
+template argument for `adjacency_list<>`. The listS and vecS types are selectors
+that determine the data structure used inside the `adjacency_list<>` (see
+Section Choosing the Edgelist and VertexList). The directedS type specifies that
+the graph should be directed (versus undirected). The following code shows the
+specification of the graph type and then the initialization of the graph. The
+edges and weights are passed to the graph constructor in the form of iterators
+(a pointer qualifies as a [SgiRandomAccessIterator]).
typedef adjacency_list<listS, vecS, directedS,
no_property, // no additional vertex properties
@@ -395,11 +415,12 @@
Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
-For the external distance property we will use a std::vector for storage. Boost.Graph algorithms treat
-random access iterators as property maps, so we can just pass the beginning iterator of the
-distance vector to Dijkstra's algorithm. Continuing the above example, the following code shows
-the creation of the distance vector, the call to Dijkstra's algorithm (implicitly using the
-internal edge weight property), and then the output of the results.
+For the external distance property we will use a std::vector for storage.
+Boost.Graph algorithms treat random access iterators as property maps, so we can
+just pass the beginning iterator of the distance vector to Dijkstra's algorithm.
+Continuing the above example, the following code shows the creation of the
+distance vector, the call to Dijkstra's algorithm (implicitly using the internal
+edge weight property), and then the output of the results.
// vector for storing distance property
std::vector<int> d(num_vertices(G));
@@ -428,31 +449,36 @@
]
[Extending Algorithms with Visitors]
-Often times an algorithm in a library almost does what you need, but not quite. For example, in
-the previous section we used Dijkstra's algorithm to calculate the shortest distances to each
-vertex, but perhaps we also wanted to record the tree of shortest paths. One way to do this is
-to record the predecessor (parent) for each node in the shortest-paths tree.
-
-It would be nice if we could avoid rewriting Dijkstra's algorithm, and just add that little bit
-extra needed to record the predecessors [1]. In the STL, this kind of extensibility is provided
-by functors, which are optional parameters to each algorithm. In Boost.Graph this role is
-fulfilled by visitors.
-
-A visitor is like a functor, but instead of having just one "apply" method, it has several.
-Each of these methods get invoked at certain well-defined points within the algorithm. The visitor
-methods are explained in detail in Section Visitor Concepts. Boost.Graph provides a number of visitors
-for some common tasks including a predecessor recording visitor. The user is encouraged to write
-his or her own visitors as a way of extending Boost.Graph. Here we will take a quick look at the
-implementation and use of the predecessor recorder. Since we will be using the
-`dijkstra_shortest_paths()` algorithm, the visitor we create must be a Dijkstra Visitor.
-
-The functionality of the record_predecessors visitor is separated into two parts. For the storage
-and access of the predecessor property, we will use a property map. The predecessor visitor will
-then only be responsible for what parent to record. To implement this, we create a
-`record_predecessors` class and template it on the predecessor property map `PredecessorMap`. Since
-this visitor will only be filling in one of the visitor methods, we will inherit from
-`dijkstra_visitor` which will provide empty methods for the rest. The constructor of the
-`predecessor_recorder` will take the property map object and save it away in a data member.
+Often times an algorithm in a library almost does what you need, but not quite.
+For example, in the previous section we used Dijkstra's algorithm to calculate
+the shortest distances to each vertex, but perhaps we also wanted to record the
+tree of shortest paths. One way to do this is to record the predecessor (parent)
+for each node in the shortest-paths tree.
+
+It would be nice if we could avoid rewriting Dijkstra's algorithm, and just add
+that little bit extra needed to record the predecessors [1]. In the STL, this
+kind of extensibility is provided by functors, which are optional parameters to
+each algorithm. In Boost.Graph this role is fulfilled by visitors.
+
+A visitor is like a functor, but instead of having just one "apply" method, it
+has several. Each of these methods get invoked at certain well-defined points
+within the algorithm. The visitor methods are explained in detail in Section
+Visitor Concepts. Boost.Graph provides a number of visitors for some common
+tasks including a predecessor recording visitor. The user is encouraged to write
+his or her own visitors as a way of extending Boost.Graph. Here we will take a
+quick look at the implementation and use of the predecessor recorder. Since we
+will be using the `dijkstra_shortest_paths()` algorithm, the visitor we create
+must be a Dijkstra Visitor.
+
+The functionality of the record_predecessors visitor is separated into two
+parts. For the storage and access of the predecessor property, we will use a
+property map. The predecessor visitor will then only be responsible for what
+parent to record. To implement this, we create a `record_predecessors` class and
+template it on the predecessor property map `PredecessorMap`. Since this visitor
+will only be filling in one of the visitor methods, we will inherit from
+`dijkstra_visitor` which will provide empty methods for the rest. The
+constructor of the `predecessor_recorder` will take the property map object and
+save it away in a data member.
template <class PredecessorMap>
class record_predecessors : public dijkstra_visitor<>
@@ -471,16 +497,18 @@
PredecessorMap m_predecessor;
};
-The job of recording the predecessors is quite simple. When Dijkstra's algorithm relaxes an edge
-(potentially adding it to the shortest-paths tree) we record the source vertex as the predecessor
-of the target vertex. Later, if the edge is relaxed again the predecessor property will be
-overwritten by the new predecessor. Here we use the put() function associated with the
-property map to record the predecessor. The `edge_filter` of the visitor tells the algorithm when
-to invoke the `explore()` method. In this case we only want to be notified about edges in the
-shortest-paths tree so we specify `tree_edge_tag`.
-
-As a finishing touch, we create a helper function to make it more convenient to create predecessor
-visitors. All Boost.Graph visitors have a helper function like this.
+The job of recording the predecessors is quite simple. When Dijkstra's algorithm
+relaxes an edge (potentially adding it to the shortest-paths tree) we record the
+source vertex as the predecessor of the target vertex. Later, if the edge is
+relaxed again the predecessor property will be overwritten by the new
+predecessor. Here we use the put() function associated with the property map to
+record the predecessor. The `edge_filter` of the visitor tells the algorithm
+when to invoke the `explore()` method. In this case we only want to be notified
+about edges in the shortest-paths tree so we specify `tree_edge_tag`.
+
+As a finishing touch, we create a helper function to make it more convenient to
+create predecessor visitors. All Boost.Graph visitors have a helper function
+like this.
template <class PredecessorMap>
record_predecessors<PredecessorMap>
@@ -488,10 +516,11 @@
return record_predecessors<PredecessorMap>(p);
}
-We are now ready to use the `record_predecessors` in Dijkstra's algorithm. Luckily, Boost.Graph's
-Dijkstra's algorithm is already equipped to handle visitors, so we just pass in our new visitor.
-In this example we only need to use one visitor, but Boost.Graph is also equipped to handle the use
-of multiple visitors in the same algorithm (see Section Visitor Concepts).
+We are now ready to use the `record_predecessors` in Dijkstra's algorithm.
+Luckily, Boost.Graph's Dijkstra's algorithm is already equipped to handle
+visitors, so we just pass in our new visitor. In this example we only need to
+use one visitor, but Boost.Graph is also equipped to handle the use of multiple
+visitors in the same algorithm (see Section Visitor Concepts).
using std::vector;
using std::cout;
Modified: trunk/libs/graph/quickbook/introduction.qbk
==============================================================================
--- trunk/libs/graph/quickbook/introduction.qbk (original)
+++ trunk/libs/graph/quickbook/introduction.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -8,10 +8,10 @@
[section Introduction]
Graphs are mathematical abstractions that are useful for solving many types of
problems in computer science. Consequently, these abstractions must also be
-represented in computer programs. A standardized generic interface for
-traversing graphs is of utmost importance to encourage reuse of graph algorithms
-and data structures. Part of the Boost Graph Library is a generic interface that
-allows access to a graph's structure, but hides the details of the implementation.
+represented in computer programs. A standardized generic interface for traversing
+graphs is of utmost importance to encourage reuse of graph algorithms and data
+structures. Part of the Boost Graph Library is a generic interface that allows
+access to a graph's structure, but hides the details of the implementation.
This is an "open" interface in the sense that any graph library that implements
this interface will be interoperable with the BGL generic algorithms and with
other algorithms that also use this interface. The BGL provides some general
Modified: trunk/libs/graph/quickbook/reference/adjacency_list.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/adjacency_list.qbk (original)
+++ trunk/libs/graph/quickbook/reference/adjacency_list.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -7,17 +7,17 @@
[section Adjacency List]
-[warning
-This reference is missing documentation for a number of associated types and
-methods.
-]
-
-[h4 Missing or Incorrect Documentation]
-* `edge_iterator`
-* `clear_in_edges()`
-* `clear_out_edges()`
+ template <
+ typename OutEdgeList = vecS,
+ typename VertexList = vecS,
+ typename Directed = directedS,
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property,
+ typename EdgeList = listS>
+ class adjacency_list;
-The adjacency_list class implements a generalized adjacency list graph structure.
+The `adjacency_list` class implements a generalized adjacency list graph structure.
The template parameters provide many configuration options so that you can pick a
version of the class that best meets your needs. An adjacency-list is basically a
two-dimensional structure, where each element of the first dimension represents a
@@ -38,9 +38,14 @@
directed graph since each edge will appear in both an out-edge and in-edge list.
Figure 2 shows an adjacency list representation of an undirected graph.
-A tutorial on how to use the adjacency_list class is in Section Using adjacency_list.
+A tutorial on how to use the [adjacency_list] class is in Section
+[link boost_graph.guide.the_adjacnecy_list The Adjacency List].
+
+[heading Where Defined]
-[h3 Template Parameters]
+`boost/graph/adjacency_list.hpp`
+
+[heading Template Parameters]
[table
[[Parameter] [Description] [Default]]
[
@@ -69,17 +74,17 @@
[`directedS`]
]
[
- [`VertexProperties`]
+ [`VertexProperty`]
[Specifies internal properties for vertices.]
[`no_property`]
]
[
- [`EdgeProperties`]
+ [`EdgeProperty`]
[Specifies internal properties for edges.]
[`no_property`]
]
[
- [`GraphProperties`]
+ [`GraphProperty`]
[Specifies internal properties for the graph object.]
[`no_property`]
]
@@ -93,38 +98,469 @@
]
]
-[h4 Model of]
-VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable,
-and Serializable.
+[heading Model of]
+All adjacency lists model these concepts: [VertexAndEdgeListGraph], [IncidenceGraph]
+[MutablePropertyGraph], [SgiCopyConstructible], and [SgiAssignable]. If the template
+parameter `Directed` is given as `bidirectionalS`, then the adjacency graph models
+the [BidirectionalGraph] concept as well.
-[h4 Where Defined]
+[heading Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<adjancency_list>::vertex_descriptor`]
+ [The type of vertex descriptors associated with the `adjacency_list`.]
+ ]
+ [
+ [`graph_traits<adjancency_list>::edge_descriptor`]
+ [The type of edge descriptors associated with the `adjacency_list`.]
+ ]
+ [
+ [`graph_traits<adjancency_list>::vertex_iterator`]
+ [
+ The type for iterators returned by `vertices()`. The concept modeled by this
+ type varies with the type of the `VertexList` parameter. If the `VertexList`
+ selector is `vecS`, then this type models the [SgiRandomAccessIterator] concept.
+ In all other cases, it is a model of [SgiBidirectionalIterator].
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::out_edge_iterator`]
+ [
+ The type for iterators returned by `edges()`. The concept modeled by this type
+ depends on the `OutEdgeList` parameter. If the selector is `vecS` then the
+ iterator is a model of [SgiRandomAccessIterator]. If the selector is `slistS`
+ then it is a model of [SgiForwardIterator]. Otherwise, the iterator models
+ [SgiBidirectionalIterator].
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::in_edge_iterator`]
+ [
+ This type is only valid if the `Directed` parameter is given as `bidirectionalS`.
+ The concepts modeled by this type are the same as the `out_edge_iterator`.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::adjacency_iterator`]
+ [
+ The type for iterators returned by `adjacent_vertices()`. The concepts modeled
+ by this type are the same as `out_edge_iterator`. Dereferencing these types,
+ however, will result in vertex descriptors rather than edge descriptors.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::inv_adjacency_iterator`]
+ [
+ The type for iterators returned by `inv_adjacent_vertices()`. The concepts
+ modeled by this type are identical to hose of the `adjacency_iterator`.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::directed_category`]
+ [
+ Provides inforamtion about whether the graph is undirected (`undirected_tag`),
+ directed (`directed_tag`), or bidirectional (`bidirectional_tag`).
+ ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::edge_parallel_category`]
+ [
+ This describes whether the class allows the insertion of parallel edges; those
+ with the same source and target. When `EdgeList` is selected as `setS` or
+ `hash_setS`, this type is set to `disallow_parallel_edge_tag`. Otherwise it
+ is `allow_parallel_edge_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::vertices_size_type`]
+ [The type used for dealing with the number of vertices in the graph. ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::edge_size_type`]
+ [The type used for dealing with the number of edges in the graph. ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::degree_size_type`]
+ [The type used for dealing with the number of edges incident to a vertex in the graph. ]
+ ]
+ [
+ [
+ `property_map<adjacency_list, Property>::type`
-`boost/graph/adjacency_list.hpp`
+ `property_map<adjacency_list, 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<adjacency_list, Property>::type`]
+ [
+ The value type ofor the graph property specified by the `Property` parameter.
+ ]
+ ]
+ [
+ [`adjacency_list::out_edge_list_selector`]
+ [The instantiated type of the `OutEdgeList` template parameter.]
+ ]
+ [
+ [`adjacency_list::vertex_list_selector`]
+ [The instantiated type of the `VertexList` template parameter.]
+ ]
+ [
+ [`adjacency_list::directed_selector`]
+ [The instantiated type of the `Directed` template parameter.]
+ ]
+ [
+ [`adjacency_list::edge_list_selector`]
+ [The instantiated type of the `EdgeList` template parameter.]
+ ]
+]
+
+[heading Member Functions]
+[table
+ [[Member Function] [Description]]
+ [
+ [`adjacency_list(const GraphProperty& p = GraphProperty())`]
+ [
+ The default constructor creates an empty graph with no vertices or edges,
+ optionally assigning the given graph properties `p`.
+ ]
+ ]
+ [
+ [`adjacency_list(const adjacency_list& x)`]
+ [ ]
+ ]
+ [
+ [
+ ``
+ adjacency_list(vertices_size_type n,
+ const GraphProperty& p = GraphProperty())
+ ``
+ ]
+ [ ]
+ ]
+ [
+ [
+ ``
+ template <typename Iter>
+ adjacency_list(Iter f, Iter l,
+ vertices_size_type n, edges_size_type m = 0,
+ const GraphProperty& p = GraphProperty())
+ ``
+ ]
+ [ ]
+ ]
+ [
+ [
+ ``
+ template <typename EdgeIter, typename PropIter>
+ adjacency_list(EdgeIter f, EgeIter l, PropIter p,
+ vertices_size_type n, edges_size_type m = 0,
+ const GraphProperty& p = GraphProperty())
+ ``
+ ]
+ [ ]
+ ]
+ [
+ [`adjacency_list& operator=(adjacency_list const& x)`]
+ [ ]
+ ]
+ [
+ [`void swap(adjacency_list& x)`]
+ [ ]
+ ]
+ [
+ [`void clear()`]
+ [ ]
+ ]
+]
+
+[heading Non-Member Observers]
+[table
+ [[Member Function] [Description]]
+ [
+ [
+ ``
+ vertices_size_type
+ num_vertices(const adjacency_list& g)
+ ``
+ ]
+ [Return the number of vertices in `g`.]
+ ]
+ [
+ [
+ ``
+ edges_size_type
+ num_edges(const adjacency_list& g)
+ ``
+ ]
+ [Return the edges in vertices in `g`.]
+ ]
+ [
+ [
+ ``
+ vertex_descriptor
+ vertex(vertices_size_type n, const adjacency_list& g)
+ ``
+ ]
+ [Return a descriptor to the `n`th vertex in `g`.]
+ ]
+ [
+ [
+ ``
+ pair<edge_descriptor, bool>
+ edge(vertex_descriptor u, vertex_descriptor v,
+ const adjacency_list& g)
+ ``
+ ]
+ [
+ Returns a pair containing a descriptor for the edge connecting vertices
+ `u` and `v` in `g`, and a boolean value that indicates whether the
+ edge exists (`true`) or not (`false`).
+ ]
+ ]
+ [
+ [
+ ``
+ vertex_descriptor
+ source(edge_descriptor e, const adjacency_list& g)
+ ``
+ ]
+ [Return the source vertex of the edge `e` in `g`.]
+ ]
+ [
+ [
+ ``
+ vertex_descriptor
+ target(edge_descriptor e, const adjacency_list& g)
+ ``
+ ]
+ [Return the target vertex of the edge `e` in `g`.]
+ ]
+ [
+ [
+ ``
+ pair<vertex_iterator, vertex_iterator>
+ vertices(const adjacency_list& g)
+ ``
+ ]
+ [Returns an iterator range to the vertex set of `g`.]
+ ]
+ [
+ [
+ ``
+ pair<edge_iterator, edge_iterator>
+ edges(const adjacency_list& g)
+ ``
+ ]
+ [Returns an iterator range to the edge set of `g`.]
+ ]
+ [
+ [
+ ``
+ pair<out_edge_iterator, out_edge_iterator>
+ out_edges(vertex_descriptor v, const adjacency_list& g)
+ ``
+ ]
+ [
+ Returns an iterator range to the out-edge set of the vertex `v` in `g`.
+ If the graph is undirected, the iterator range provides access to all
+ incident edges.
+ ]
+ ]
+ [
+ [
+ ``
+ pair<in_edge_iterator, in_edge_iterator>
+ in_edges(vertex_descriptor v, const adjacency_list& g)
+ ``
+ ]
+ [
+ Returns an iterator range to the in-edge set of the vertex `v` in `g`.
+ If the graph is undirected, this operation is equivalent to `out_edges`.
+ ]
+ ]
+ [
+ [
+ ``
+ pair<adjacency_iterator, adjacency_iterator>
+ adjacent_vertices(vertex_descriptor v, const adjacency_list& g)
+ ``
+ ]
+ [Returns an iterator range providing access to the adjacent vertices of `v` in `g`.]
+ ]
+ [
+ [
+ ``
+ degree_size_type
+ out_degree(vertex_descriptor v, const adjacency_list& g)``
+ ]
+ [
+ Return the out-degree of vertex `v` in `g`.
+
+ *Complexity:* /O(|V|)/
+ ]
+ ]
+ [
+ [
+ ``
+ degree_size_type
+ in_degree(vertex_descriptor v, const adjacency_list& g)
+ ``
+ ]
+ [
+ Return the in-degree of vertex `v` in `g`.
+
+ *Complexity:* /O(|V|)/
+ ]
+ ]
+]
+
+
+[heading Non-Member Mutators]
+[table
+ [[Member Function] [Description]]
+ [
+ [
+ ``
+ pair<edge_descriptor, bool>
+ add_edge(vertex_descriptor u, vertex_descriptor v,
+ adjacency_list& g)
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ pair<edge_descriptor, bool>
+ add_edge(vertex_descriptor u, vertex_descriptor v,
+ EdgeProperty const& p, adjacency_list& g)
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ void remove_edge(vertex_descriptor u, vertex_descriptor v,
+ adjacency_list& g)
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ void remove_edge(edge_descriptor v, adjacency_list& g)
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ void clear_vertex(edge_descriptor v, adjacency_list& g)
+ ``
+ ]
+ []
+ ]
+]
-The serialization functionality is in `boost/graph/adj_list_serialize.hpp`.
+[heading Property Accessors]
+[table
+ [[Member Function] [Description]]
+ [
+ [
+ ``
+ template <typename Property>
+ typename property_map<adjancecy_list, Property>::type
+ get(Property, adjaceny_list& g);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property>
+ typename property_map<adjancecy_list, Property>::const_type
+ get(Property, adjaceny_list const& g);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property, typename X>
+ typename property_traits<
+ property_map<adjancecy_list, Property>::const_type
+ >::value_type
+ get(Property, adjaceny_list const& g, X x);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property, typename X, typename Value>
+ void put(Property, X, adjaceny_list const& g,
+ X x, const Value&);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property>
+ typename graph_property<adjacency_list, Property>::type
+ void get_property(adjaceny_list const& g, Property);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property, typename Value>
+ void set_property(adjaceny_list const& g, Property,
+ const Value&);
+ ``
+ ]
+ []
+ ]
+]
-[h3 Vertex and Edge Properties]
+[heading Vertex and Edge Properties]
Properties such as color, distance, weight, and user-defined properties can be
attached to the vertices and edges of the graph using properties. The property
values can be read from and written to via the property maps provided by the
-graph. The property maps are obtained via the get(property, g) function. How
+graph. The property maps are obtained via the `get(property, g)` function. How
to use properties is described in Section Internal Properties . The property
maps are objects that implement the interface defined in Section Property Map
Concepts or may be bundled properties, which have a more succinct syntax. The
-types of all property values must be Copy Constructible, Assignable, and
-Default Constructible. The property maps obtained from the adjacency_list class
-are models of the Lvalue Property Map concept. If the adjacency_list is const,
-then the property map is constant, otherwise the property map is mutable.
+types of all property values must be [SgiCopyConstructible], [SgiAssignable], and
+[SgiDefaultConstructible]. The property maps obtained from the adjacency_list class
+are models of the [LvaluePropertyMap] concept. If the `adjacency_list` is `const`,
+then the property map is constant, otherwise the property map is mutable.
If the VertexList of the graph is vecS, then the graph has a builtin vertex
indices accessed via the property map for the vertex_index_t property. The
-indices fall in the range [0, num_vertices(g)) and are contiguous. When a
+indices fall in the range \[0, num_vertices(g)) and are contiguous. When a
vertex is removed the indices are adjusted so that they retain these
properties. Some care must be taken when using these indices to access exterior
roperty storage. The property map for vertex index is a model of Readable
Property Map.
-[h3 Iterator and Descriptor Stability/Invalidation]
+[heading Iterator and Descriptor Stability/Invalidation]
Some care must be taken when changing the structure of a graph (via adding or
removing edges). Depending on the type of adjacency_list and on the operation,
some of the iterator or descriptor objects that point into the graph may become
@@ -228,9 +664,7 @@
[[Function] [Vertex Descriptor] [Edge Descriptor] [Vertex Iterator] [Edge Iterator] [Adjacency Iterator]]
[
[`add_edge()`]
- [Valid]
- [Valid]
- [Valid]
+ [Valid] [Valid] [Valid]
[
OEL = `vecS` &&
@@ -249,162 +683,21 @@
`clear_vertex()`
]
- [Valid]
- [Valid]
- [Valid]
+ [Valid] [Valid] [Valid]
[
OEL = `vecS` &&
- Directed = `directedS`]
+ Directed = `directedS`
+ ]
[OEL = `vecS`]
]
[
[`add_vertex()`]
- [Valid]
- [Valid]
- [Valid]
- [Valid]
- [Valid]
+ [Valid] [Valid] [Valid] [Valid] [Valid]
]
[
[`remove_vertex()`]
- [VL = `vecS`]
- [VL = `vecS`]
- [VL = `vecS`]
- [VL = `vecS`]
- [VL = `vecS`]
- ]
-]
-
-[h3 Associated Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<adjancency_list>::vertex_descriptor`]
- [
- The type for the vertex descriptors associated with the `adjacency_list`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::edge_descriptor`]
- [
- The type for the edge descriptors associated with the `adjacency_list`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::vertex_iterator`]
- [
- The type for iterators returned by `vertices()`. The concept modeled by this
- type varies with the type of the `VertexList` parameter. If the `VertexList`
- selector is `vecS`, then this type models the `RandomAccessIterator` concept.
- In all other cases, it is a model of `BidirectionalIterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::out_edge_iterator`]
- [
- The type for iterators returned by `edges()`. The concept modeled by this type
- depends on the `OutEdgeList` parameter. If the selector is `vecS` then the
- iterator is a model of `RandomAccessIterator`. If the selector is `slistS`
- then it is a model of `ForwardIterator`. Otherwise, the iterator models
- `BidirectionalIterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::in_edge_iterator`]
- [
- This type is only valid if the `Directed` parameter is given as `bidirectionalS`.
- The concepts modeled by this type are the same as the `out_edge_iterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::adjacency_iterator`]
- [
- The type for iterators returned by `adjacent_vertices()`. The concepts modeled
- by this type are the same as `out_edge_iterator`. Dereferencing these types,
- however, will result in vertex descriptors rather than edge descriptors.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::inv_adjacency_iterator`]
- [
- The type for iterators returned by `inv_adjacent_vertices()`. The concepts
- modeled by this type are identical to hose of the `adjacency_iterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::directed_category`]
- [
- Provides inforamtion about whether the graph is undirected (`undirected_tag`),
- directed (`directed_tag`), or bidirectional (`bidirectional_tag`).
- ]
- ]
- [
- [`graph_traits<adjacency_list>::edge_parallel_category`]
- [
- This describes whether the class allows the insertion of parallel edges; those
- with the same source and target. When `EdgeList` is selected as `setS` or
- `hash_setS`, this type is set to `disallow_parallel_edge_tag`. Otherwise it
- is `allow_parallel_edge_tag`.
- ]
- ]
- [
- [`graph_traits<adjacency_list>::vertices_size_type`]
- [The type used for dealing with the number of vertices in the graph. ]
- ]
- [
- [`graph_traits<adjacency_list>::edge_size_type`]
- [The type used for dealing with the number of edges in the graph. ]
- ]
- [
- [`graph_traits<adjacency_list>::degree_size_type`]
- [The type used for dealing with the number of edges incident to a vertex in the graph. ]
- ]
- [
- [
- `property_map<adjacency_list, Property>::type`
-
- `property_map<adjacency_list, 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<adjacency_list, Property>::type`]
- [
- The value type ofor the graph property specified by the `Property` parameter.
- ]
- ]
- [
- [`adjacency_list::out_edge_list_selector`]
- [The instantiated type of the `OutEdgeList` template parameter.]
- ]
- [
- [`adjacency_list::vertex_list_selector`]
- [The instantiated type of the `VertexList` template parameter.]
- ]
- [
- [`adjacency_list::directed_selector`]
- [The instantiated type of the `Directed` template parameter.]
- ]
- [
- [`adjacency_list::edge_list_selector`]
- [The instantiated type of the `EdgeList` template parameter.]
- ]
-]
-
-[h3 Member Functions]
-[table
- [[Member Function] [Description]]
- [
- [`adjacency_list(const GraphProperties& = GraphProperties()`]
- [
- The default constructor creates an empty graph with no vertices or edges.
- ]
+ [VL = `vecS`] [VL = `vecS`] [VL = `vecS`] [VL = `vecS`] [VL = `vecS`]
]
]
Added: trunk/libs/graph/quickbook/reference/adjacency_matrix.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/graph/quickbook/reference/adjacency_matrix.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -0,0 +1,478 @@
+[/
+ / Copyright (C) 2007-2009 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 Adjacency Matrix]
+
+ template <
+ typename Directed = directedS,
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property,
+ typename Allocator = std::allocator<...> >
+ class adjacency_matrix;
+
+The `adjacency_matrix` class implements the Boost.Graph interface using the
+traditional adjacency matrix storage format. For a graph with /V/ vertices, a
+/V x V/ matrix is used, where each element ['a[sub ij]] is a boolean flag that
+says whether there is an edge from vertex /i/ to vertex /j/. Figure 1 shows
+the adjacency matrix representation of a graph.
+
+[note TODO: Rebuild image]
+
+The advantage of this matrix format over the adjacency list is that edge insertion
+and removal is constant time. There are several disadvantages. The first is that
+the amount of memory used is ['O(V[sup 2])] instead of /O(V + E)/ (where /E/ is
+the number of edges). The second is that operations that traverse all the out-edges
+of each vertex (such as breadth-first search) run in ['O(V[sup 2])] time instead
+of /O(V + E)/ time for the adjacency list. In short, it is better to use the
+`adjacency_matrix` for dense graphs (where /E/ is close to ['V[sup 2]]) and it is
+better to use [adjacency_list] for sparse graphs (where /E/ is much smaller than
+['V[sup2]]).
+
+The `adjacency_matrix` class extends the traditional data structure by allowing
+objects to be attached to vertices and edges using the same property template
+parameters supported by [adjacency_list]. These may be
+[link boost_graph.guide.bundled_properties bundled properties]
+or standard (backward-compatible)
+[link boost_graph.guide.interior_properties interior properties].
+The types of all property values must be [StdRegular].
+
+In the case of an undirected graph, the `adjacency_matrix`. class does not use a
+full /V x V/ matrix but instead uses a lower triangle (the diagonal and below)
+since the matrix for an undirected graph is symmetric. This reduces the storage
+to ['(V[sup 2])/2]. Figure 2</a> shows an adjacency matrix representation of an
+undirected graph.
+
+[note TODO: Rebuild image.]
+
+[heading Where Defined]
+`boost/graph/adjacency_matrix.hpp`
+
+[heading Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`Directed`]
+ [
+ A selector to choose whether the graph is directed or undirected.
+ The options are directedS and undirectedS.
+ ]
+ [`directedS`]
+ ]
+ [
+ [`VertexProperties`]
+ [Specifies internal properties for vertices.]
+ [`no_property`]
+ ]
+ [
+ [`EdgeProperties`]
+ [Specifies internal properties for edges.]
+ [`no_property`]
+ ]
+ [
+ [`GraphProperties`]
+ [Specifies internal properties for the graph object.]
+ [`no_property`]
+ ]
+ [
+ [`Alloator`]
+ [
+ The allocator type for the adjacency matrix.
+ ]
+ [`std::allocator<...>`]
+ ]
+]
+
+[heading Model Of]
+[VertexAndEdgeListGraph], [BidirecitonalGraph], [AdjacencyMatrix],
+[MutablePropertyGraph], [SgiCopyConstructible], [SgiAssignable]
+
+[heading Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<adjancency_list>::vertex_descriptor`]
+ [The type of the graph's vertex descriptors.]
+ ]
+ [
+ [`graph_traits<adjancency_list>::edge_descriptor`]
+ [The type of the graph's edge descriptors.]
+ ]
+ [
+ [`graph_traits<adjancency_list>::vertex_iterator`]
+ [
+ The type for iterators returned by `vertices()`, modeling the
+ [SgiRandomAccessIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::edge_iterator`]
+ [
+ The type for iterators returned by `edges()`, modeling the
+ [SgiForwardIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::out_edge_iterator`]
+ [
+ The type for iterators returned by `out_edges()`, modeling the
+ [SgiForwardIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::in_edge_iterator`]
+ [
+ The type for iterators returned by `in_edges()`, modeling the
+ [SgiForwardIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::adjacency_iterator`]
+ [
+ The type for iterators returned by `adjacent_vertices()`, modeling the
+ [SgiForwardIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<adjancency_list>::directed_category`]
+ [
+ Provides inforamtion about whether the graph is undirected (`undirected_tag`),
+ or directed (`directed_tag`).
+ ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::edge_parallel_category`]
+ [
+ Adjacency matrices do not allow the insertion of parallel edges so
+ this type is always `disallow_parallel_edges`.
+ ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::vertices_size_type`]
+ [The type used for dealing with the number of vertices in the graph. ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::edge_size_type`]
+ [The type used for dealing with the number of edges in the graph. ]
+ ]
+ [
+ [`graph_traits<adjacency_list>::degree_size_type`]
+ [The type used for dealing with the number of edges incident to a vertex in the graph.]
+ ]
+ [
+ [
+ `property_map<adjacency_list, Property>::type`
+
+ `property_map<adjacency_list, 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<adjacency_list, Property>::type`]
+ [
+ The value type ofor the graph property specified by the `Property` parameter.
+ ]
+ ]
+]
+
+[heading Member Functions]
+[table
+ [[Member Function] [Description]]
+ [
+ [`adjacency_matrix(vertices_size_type n, const GraphProperties& = GraphProperties()`]
+ [Construct a graph with `n` vertices and no edges.]
+ ]
+ [
+ [
+ ``
+ template <typename Iter>
+ adjacency_matrix(Iter f, Iter l, vertices_size_type n, const GraphProperties& = GraphProperties())
+ ``
+ ]
+ [
+ Construct a graph with `n` vertices and and the edges specified by
+ the iterator range \[f, l). The `value_type` of `Iter` must be a
+ `std::pair` of `int`s whose values are in the range \[0, n), and
+ indicate the given vertex.
+ ]
+ ]
+ [
+ [
+ ``
+ template <typename EdgeIter, typename PropIter>
+ adjacency_matrix(Iter f, Iter l, PropIter p, vertices_size_type n, const GraphProperties& = GraphProperties())
+ ``
+ ]
+ [
+ Construct a graph with `n` vertices and and the edges specified by
+ the iterator range \[f, l), with the edge properties given by the
+ iterator range starting at `p`. The `value_type` of `EdgeIter` must
+ be a `std::pair` of `int`s whose values are in the range \[0, n), and
+ indicate the given vertex. The `value_type` of the `PropIter` must be
+ the same as the template parameter `EdgeProperty`.
+ ]
+ ]
+]
+
+[heading Non-Member Observers]
+[table
+ [[Member Function] [Description]]
+ [
+ [`vertices_size_type num_vertices(const adjacency_matrix& g)`]
+ [Return the number of vertices in `g`.]
+ ]
+ [
+ [`edges_size_type num_edges(const adjacency_matrix& g)`]
+ [Return the edges in vertices in `g`.]
+ ]
+ [
+ [`vertex_descriptor vertex(vertices_size_type n, const adjacency_matrix& g)`]
+ [Return a descriptor to the `n`th vertex in `g`.]
+ ]
+ [
+ [`pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor v, const adjacency_matrix& g)`]
+ [
+ Returns a pair containing a descriptor for the edge connecting vertices
+ `u` and `v` in `g`, and a boolean value that indicates whether the
+ edge exists (`true`) or not (`false`).
+ ]
+ ]
+ [
+ [`vertex_descriptor source(edge_descriptor e, const adjacency_matrix& g)`]
+ [Return the source vertex of the edge `e` in `g`.]
+ ]
+ [
+ [`vertex_descriptor target(edge_descriptor e, const adjacency_matrix& g)`]
+ [Return the target vertex of the edge `e` in `g`.]
+ ]
+ [
+ [`pair<vertex_iterator, vertex_iterator> vertices(const adjacency_matrix& g)`]
+ [Returns an iterator range to the vertex set of `g`.]
+ ]
+ [
+ [`pair<edge_iterator, edge_iterator> edges(const adjacency_matrix& g)`]
+ [Returns an iterator range to the edge set of `g`.]
+ ]
+ [
+ [`pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor v, const adjacency_matrix& g)`]
+ [
+ Returns an iterator range to the out-edge set of the vertex `v` in `g`.
+ If the graph is undirected, the iterator range provides access to all
+ incident edges.
+ ]
+ ]
+ [
+ [`pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const adjacency_matrix& g)`]
+ [
+ Returns an iterator range to the in-edge set of the vertex `v` in `g`.
+ If the graph is undirected, this operation is equivalent to `out_edges`.
+ ]
+ ]
+ [
+ [`pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor v, const adjacency_matrix& g)`]
+ [Returns an iterator range providing access to the adjacent vertices of `v` in `g`.]
+ ]
+ [
+ [`degree_size_type out_degree(vertex_descriptor v, const adjacency_matrix& g)`]
+ [
+ Return the out-degree of vertex `v` in `g`.
+
+ *Complexity:* /O(|V|)/
+ ]
+ ]
+ [
+ [`degree_size_type in_degree(vertex_descriptor v, const adjacency_matrix& g)`]
+ [
+ Return the in-degree of vertex `v` in `g`.
+
+ *Complexity:* /O(|V|)/
+ ]
+ ]
+]
+
+
+[heading Non-Member Mutators]
+[table
+ [[Member Function] [Description]]
+ [
+ [`pair<edge_descriptor, bool> add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_matrix& g)`]
+ []
+ ]
+ [
+ [`pair<edge_descriptor, bool> add_edge(vertex_descriptor u, vertex_descriptor v, EdgeProperty const& p, adjacency_matrix& g)`]
+ []
+ ]
+ [
+ [`void remove_edge(vertex_descriptor u, vertex_descriptor v, adjacency_matrix& g)`]
+ []
+ ]
+ [
+ [`void remove_edge(edge_descriptor v, adjacency_matrix& g)`]
+ []
+ ]
+ [
+ [`void clear_vertex(edge_descriptor v, adjacency_matrix& g)`]
+ []
+ ]
+]
+
+[heading Property Accessors]
+[table
+ [[Member Function] [Description]]
+ [
+ [
+ ``
+ template <typename Property>
+ typename property_map<adjancecy_matrix, Property>::type
+ get(Property, adjaceny_matrix& g);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property>
+ typename property_map<adjancecy_matrix, Property>::const_type
+ get(Property, adjaceny_matrix const& g);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property, typename X>
+ typename property_traits<
+ property_map<adjancecy_matrix, Property>::const_type
+ >::value_type
+ get(Property, adjaceny_matrix const& g, X x);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property, typename X, typename Value>
+ void put(Property, X, adjaceny_matrix const& g, X x, const Value&);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property>
+ void get_property(adjaceny_matrix const& g, Property);
+ ``
+ ]
+ []
+ ]
+ [
+ [
+ ``
+ template <typename Property, typename Value>
+ void set_property(adjaceny_matrix const& g, Property, const Value&);
+ ``
+ ]
+ []
+ ]
+]
+
+
+[heading Example]
+Create the graph of Figure 1.
+
+ enum { A, B, C, D, E, F, N };
+ const char* name = "ABCDEF";
+
+ typedef boost::adjacency_matrix<boost::directedS> Graph;
+ Graph g(N);
+ add_edge(B, C, g);
+ add_edge(B, F, g);
+ add_edge(C, A, g);
+ add_edge(C, C, g);
+ add_edge(D, E, g);
+ add_edge(E, D, g);
+ add_edge(F, A, g);
+
+ std::cout << "vertex set: ";
+ boost::print_vertices(g, name);
+ std::cout << std::endl;
+
+ std::cout << "edge set: ";
+ boost::print_edges(g, name);
+ std::cout << std::endl;
+
+ std::cout << "out-edges: " << std::endl;
+ boost::print_graph(g, name);
+ std::cout << std::endl;
+
+The output is:
+[pre
+ vertex set: A B C D E F
+
+ edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A)
+
+ out-edges:
+ A -->
+ B --> C F
+ C --> A C
+ D --> E
+ E --> D
+ F --> A
+]
+
+Create the graph of Figure 2.
+
+ enum { A, B, C, D, E, F, N };
+ const char* name = "ABCDEF";
+
+ typedef boost::adjacency_matrix<boost::undirectedS> UGraph;
+ UGraph ug(N);
+ add_edge(B, C, ug);
+ add_edge(B, F, ug);
+ add_edge(C, A, ug);
+ add_edge(D, E, ug);
+ add_edge(F, A, ug);
+
+ std::cout << "vertex set: ";
+ boost::print_vertices(ug, name);
+ std::cout << std::endl;
+
+ std::cout << "edge set: ";
+ boost::print_edges(ug, name);
+ std::cout << std::endl;
+
+ std::cout << "incident edges: " << std::endl;
+ boost::print_graph(ug, name);
+ std::cout << std::endl;
+
+The output is:
+
+[pre
+ vertex set: A B C D E F
+
+ edge set: (C,A) (C,B) (E,D) (F,A) (F,B)
+
+ incident edges:
+ A <--> C F
+ B <--> C F
+ C <--> A B
+ D <--> E
+ E <--> D
+ F <--> A B
+]
+
+[endsect]
+
Modified: trunk/libs/graph/quickbook/reference/reference.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/reference.qbk (original)
+++ trunk/libs/graph/quickbook/reference/reference.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -11,20 +11,26 @@
[include undirected_graph.qbk]
[include directed_graph.qbk]
[include adjacency_list.qbk]
+[include adjacency_matrix.qbk]
[include edge_list.qbk]
[endsect]
[section Traits Classes]
-[include exterior_vertex_property.qbk]
+[/
+ / [include graph_traits.qbk]
+ / [include exterior_vertex_property.qbk]
+/]
[endsect]
-[section Event Visitor List Adaptors]
+[section Visitor Adaptors]
[/
[include bfs_visitor.qbk]
[include dfs_visitor.qbk]
[include dijkstra_visitor.qbk]
[include bellman_visitor.qbk]
[include astar_visitor.qbk]
+[include clique_visitor.qbk]
+[inblude cycle_visitor.qbk]
/]
[endsect]
Modified: trunk/libs/graph/quickbook/sgi_concepts.qbk
==============================================================================
--- trunk/libs/graph/quickbook/sgi_concepts.qbk (original)
+++ trunk/libs/graph/quickbook/sgi_concepts.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
@@ -5,37 +5,50 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[/ This file defines templates that expand to links to the STL concepts. /]
+[/ NOTE: This file defines templates that expand to links to standard concepts
+ / that are primarily documented by the SGI site. Note that some concepts have
+ / been added or deprecated since then. Unfortunately, they can't be documented.
+ /
+ / Concepts appearing in the C++0x Draft Standard are prefixed with 'Std'. Those
+ / whose documentation can be found in the SGI docs are prefixed with 'Sgi'.
+ /]
[/ Missing documentation /]
[template NoConcept[x] [^[x]]]
-[template SgiAssignable[] [@http://www.sgi.com/tech/stl/Assignable.html Assignable]]
-[template SgiDefaultConstructible[] [@http://www.sgi.com/tech/stl/DefaultConstructible.html DefaultConstructible]]
-[template SgiCopyConstructible[] [@http://www.sgi.com/tech/stl/CopyConstructible.html CopyConstructible]]
-[template SgiEqualityComparable[] [@http://www.sgi.com/tech/stl/EqualityComparable.html EqualityComparable]]
-[template SgiLessThanComparable[] [@http://www.sgi.com/tech/stl/LessThanComparable.html LessThanComparable]]
-
-[template SgiContainer[] [@http://www.sgi.com/tech/stl/Container.html Container]]
-[template SgiForwardContainer[] [@http://www.sgi.com/tech/stl/ForwardContainer.html ForwardContainer]]
-[template SgiReversibleContainer[] [@http://www.sgi.com/tech/stl/ReversibleContainer.html ReversibleContainer]]
-[template SgiRandomAccessContainer[] [@http://www.sgi.com/tech/stl/RandomAccessContainer.html RandomAccessContainer]]
-
-[template SgiSequence[] [@http://www.sgi.com/tech/stl/Sequence.html Sequence]]
-[template SgiFrontInsertionSequence[] [@http://www.sgi.com/tech/stl/FrontInsertionSequence.html FrontInsertionSequence]]
-[template SgiBackInsertionSequence[] [@http://www.sgi.com/tech/stl/BackInsertionSequence.html BackInsertionSequence]]
-
-[template SgiAssociativeContainer[] [@http://www.sgi.com/tech/stl/AssociativeContainer.html AssociativeContainer]]
-[template SgiSortedAssociativeContainer[] [@http://www.sgi.com/tech/stl/SortedAssociativeContainer.html SortedAssociativeContainer]]
-[template SgiHashedAssociativeContainer[] [@http://www.sgi.com/tech/stl/HashedAssociativeContainer.html HashedAssociativeContainer]]
-
-[template SgiInputIterator[] [@http://www.sgi.com/tech/stl/InputIterator.html BidirectionalIterator]]
-[template SgiOutputIterator[] [@http://www.sgi.com/tech/stl/OutputIterator.html OutputIterator]]
-[template SgiForwardIterator[] [@http://www.sgi.com/tech/stl/ForwardIterator.html ForwardIterator]]
-[template SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html BidirectionalIterator]]
-[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html RandomAccessIterator]]
+[template SgiAssignable[] [@http://www.sgi.com/tech/stl/Assignable.html [^Assignable]]]
+[template SgiDefaultConstructible[] [@http://www.sgi.com/tech/stl/DefaultConstructible.html [^DefaultConstructible]]]
+[template SgiCopyConstructible[] [@http://www.sgi.com/tech/stl/CopyConstructible.html [^CopyConstructible]]]
+[template SgiEqualityComparable[] [@http://www.sgi.com/tech/stl/EqualityComparable.html [^EqualityComparable]]]
+[template SgiLessThanComparable[] [@http://www.sgi.com/tech/stl/LessThanComparable.html [^LessThanComparable]]]
+
+[template StdSemiregular [^Semiregular]]
+[template StdRegular[] [^Regular]]
+
+[template SgiContainer[] [@http://www.sgi.com/tech/stl/Container.html [^Container]]]
+[template SgiForwardContainer[] [@http://www.sgi.com/tech/stl/ForwardContainer.html [^ForwardContainer]]]
+[template SgiReversibleContainer[] [@http://www.sgi.com/tech/stl/ReversibleContainer.html [^ReversibleContainer]]]
+[template SgiRandomAccessContainer[] [@http://www.sgi.com/tech/stl/RandomAccessContainer.html [^RandomAccessContainer]]]
+
+[template SgiSequence[] [@http://www.sgi.com/tech/stl/Sequence.html [^Sequence]]]
+[template SgiFrontInsertionSequence[] [@http://www.sgi.com/tech/stl/FrontInsertionSequence.html [^FrontInsertionSequence]]]
+[template SgiBackInsertionSequence[] [@http://www.sgi.com/tech/stl/BackInsertionSequence.html [^BackInsertionSequence]]]
+
+[template SgiAssociativeContainer[] [@http://www.sgi.com/tech/stl/AssociativeContainer.html [^AssociativeContainer]]]
+[template SgiSimpleAssociativeContainer[] [@http://www.sgi.com/tech/stl/SimpleAssociativeContainer.html [^SimpleAssociativeContainer]]]
+[template SgiPairAssociativeContainer[] [@http://www.sgi.com/tech/stl/PairAssociativeContainer.html [^PairAssociativeContainer]]]
+[template SgiSortedAssociativeContainer[] [@http://www.sgi.com/tech/stl/SortedAssociativeContainer.html [^SortedAssociativeContainer]]]
+[template SgiHashedAssociativeContainer[] [@http://www.sgi.com/tech/stl/HashedAssociativeContainer.html [^HashedAssociativeContainer]]]
+[template SgiUniqueAssociativeContainer[] [@http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html [^UniqueAssociativeContainer]]]
+[template SgiMultipleAssociativeContainer[] [@http://www.sgi.com/tech/stl/MultipleAssociativeContainer.html [^MultipleAssociativeContainer]]]
+
+[template SgiInputIterator[] [@http://www.sgi.com/tech/stl/InputIterator.html [^BidirectionalIterator]]]
+[template SgiOutputIterator[] [@http://www.sgi.com/tech/stl/OutputIterator.html [^OutputIterator]]]
+[template SgiForwardIterator[] [@http://www.sgi.com/tech/stl/ForwardIterator.html [^ForwardIterator]]]
+[template SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html [^BidirectionalIterator]]]
+[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html [^RandomAccessIterator]]]
-[template SgiPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
-[template SgiMonoid[] [@http://www.sgi.com/tech/stl/Monoid.html Monoid]]
+[template SgiPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html [^Predicate]]]
+[template SgiMonoid[] [@http://www.sgi.com/tech/stl/Monoid.html [^Monoid]]]
-[template StdIndexable[] [link boostgraph [^Indexable]]]
+[/ [template StdIndexable[] [link boostgraph [^Indexable]]] /]
Deleted: trunk/libs/graph/quickbook/theory.qbk
==============================================================================
--- trunk/libs/graph/quickbook/theory.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
+++ (empty file)
@@ -1,252 +0,0 @@
-[/
- / 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 Review of Elementary Graph Theory]
-This chapter is meant as a refresher on elementary graph theory. If the reader has some previous
-acquaintance with graph algorithms, this chapter should be enough to get started. If the reader
-has no previous background in graph algorithms we suggest a more thorough introduction such as
-/Introduction to Algorithms/ by Cormen, Leiserson, and Rivest.
-
-[h2 The Graph Abstraction]
-A graph is a mathematical abstraction that is useful for solving many kinds of problems. Fundamentally,
-a graph consists of a set of vertices, and a set of edges, where an edge is something that connects two
-vertices in the graph. More precisely, a graph is a pair (V,E), where V is a finite set and E is a binary
-relation on V. V is called a vertex set whose elements are called vertices. E is a collection of edges,
-where an edge is a pair (u,v) with u,v in V. In a directed graph, edges are ordered pairs, connecting a
-source vertex to a target vertex. In an undirected graph edges are unordered pairs and connect the two
-vertices in both directions, hence in an undirected graph (u,v) and (v,u) are two ways of writing the same
-edge.
-
-This definition of a graph is vague in certain respects; it does not say what a vertex or edge represents.
-They could be cities with connecting roads, or web-pages with hyperlinks. These details are left out of
-the definition of a graph for an important reason; they are not a necessary part of the graph abstraction.
-By leaving out the details we can construct a theory that is reusable, that can help us solve lots of
-different kinds of problems.
-
-Back to the definition: a graph is a set of vertices and edges. For purposes of demonstration, let us
-consider a graph where we have labeled the vertices with letters, and we write an edge simply as a pair
-of letters. Now we can write down an example of a directed graph as follows:
-
- G = (V, E)
- V = {v, b, x, z, a, y }
- E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) }
-
-Figure 1 gives a pictorial view of this graph. The edge (x,x) is called a self-loop. Edges (b,y) and (b,y)
-are parallel edges, which are allowed in a multigraph (but are normally not allowed in a directed or
-undirected graph).
-
-[$../images/review_figure_1.png]
-
-Next we have a similar graph, though this time it is undirected. Figure 2 gives the pictorial view.
-Self loops are not allowed in undirected graphs. This graph is the undirected version(b,y)), meaning it
-has the same vertices and the same edges with their directions removed. Also the self edge has been
-removed, and edges such as (a,z) and (z,a) are collapsed into one edge. One can go the other way,
-and make a directed version of an undirected graph be replacing each edge by two edges, one pointing
-in each direction.
-
- G = (V, E)
- V = {v, b, x, z, a, y }
- E = { (b,y), (y,v), (z,a), (b,x), (x,v) }
-
-[$../images/review_figure_2.png]
-
-Now for some more graph terminology. If some edge (u,v) is in graph , then vertex v is adjacent to vertex u.
-In a directed graph, edge (u,v) is an out-edge of vertex u and an in-edge of vertex v. In an undirected graph
-edge (u,v) is incident on vertices u and v.
-
-In Figure 1, vertex y is adjacent to vertex b (but b is not adjacent to y). The edge (b,y) is an out-edge
-of b and an in-edge of y. In Figure 2, y is adjacent to b and vice-versa. The edge (y,b) is incident on
-vertices y and b.
-
-In a directed graph, the number of out-edges of a vertex is its out-degree and the number of in-edges is
-its in-degree. For an undirected graph, the number of edges incident to a vertex is its degree. In Figure 1,
-vertex b has an out-degree of 3 and an in-degree of zero. In Figure 2, vertex b simply has a degree of 2.
-
-Now a path is a sequence of edges in a graph such that the target vertex of each edge is the source vertex
-of the next edge in the sequence. If there is a path starting at vertex u and ending at vertex v we say
-that v is reachable from u. A path is simple if none of the vertices in the sequence are repeated. The
-path <(b,x), (x,v)> is simple, while the path <(a,z), (z,a)> is not. Also, the path <(a,z), (z,a)> is called
-a cycle because the first and last vertex in the path are the same. A graph with no cycles is acyclic.
-
-A planar graph is a graph that can be drawn on a plane without any of the edges crossing over each other.
-Such a drawing is called a plane graph. A face of a plane graph is a connected region of the plane
-surrounded by edges. An important property of planar graphs is that the number of faces, edges, and
-vertices are related through Euler's formula: |F| - |E| + |V| = 2. This means that a simple planar graph
-has at most O(|V|) edges.
-
-[h2 Graph Data Structures]
-The primary property of a graph to consider when deciding which data structure to use is sparsity - the
-number of edges relative to the number of vertices in the graph. A graph where E is close to V2 is a
-/dense graph/, whereas a graph where E = alpha V and alpha is much smaller than V is a /sparse graph/. For
-dense graphs, the adjacency-matrix representation is usually the best choice, whereas for sparse graphs
-the adjacency-list representation is a better choice. Also the edge-list representation is a space efficient
-choice for sparse graphs that is appropriate in some situations.
-
-[h3 Adjacency Matrix Representation]
-An adjacency-matrix representation of a graph is a 2-dimensional V x V array. Each element in the array
-auv stores a Boolean value saying whether the edge (u,v) is in the graph. Figure 3 depicts an adjacency
-matrix for the graph in Figure 1 (minus the parallel edge (b,y)). The ammount of space required to store
-an adjacency-matrix is O(V2). Any edge can be accessed, added, or removed in O(1) time. To add or remove
-a vertex requires reallocating and copying the whole graph, an O(V2) operation. The `adjacency_matrix<>`
-class implements the Boost.Graph interface in terms of the adjacency-matrix data structure.
-
-[$../images/review_adjacency_matrix.gif]
-
-[h3 Adjacency List Representation]
-An adjacency-list representation of a graph stores an out-edge sequence for each vertex. For sparse
-graphs this saves space since only O(V + E) memory is required. In addition, the out-edges for each
-vertex can be accessed more efficiently. Edge insertion is O(1), though accessing any given edge is
-O(alpha), where alpha is the sparsity factor of the matrix (which is equal to the maximum number of
-out-edges for any vertex in the graph). Figure 4 depicts an adjacency-list representation of the
-graph in Figure 1. The adjacency_list class is an implementation of the adjacency-list representation.
-
-[$../images/review_adjacency_list.gif]
-
-[h3 Edge List Representation]
-An edge-list representation of a graph is simply a sequence of edges, where each edge is represented
-as a pair of vertex ID's. The memory required is only O(E). Edge insertion is typically O(1), though
-accessing a particular edge is O(E) (not efficient). Figure 5 shows an edge-list representation of the
-graph in Figure 1. The edge_list adaptor class can be used to create implementations of the edge-list
-representation.
-
-[$../images/review_edge_list.gif]
-
-[h3 Other Respresentations]
-Add something here to discuss optimized storage options for the graph. Specifically, we might
-mention the compressed-sparse-row graph representation and its possible uses.
-
-[h2 Graph Algorithms]
-Like all data structures, there are numerous algorithms that operate on them to solve various problems.
-In fact, there are often several different approaches to solving the same problem, each with different
-properties and complexities when running on graphs with different properties (e.g., directed vs. undirected
-or sparse vs. dense). The following sections briefly discuss a few such problems and algorithms.
-
-[h3 Graph Search Algorithms]
-Tree edges are edges in the search tree (or forest) constructed (implicitly or explicitly) by running a
-graph search algorithm over a graph. An edge (u,v) is a tree edge if v was first discovered while
-exploring (corresponding to the visitor explore() method) edge (u,v). Back edges connect vertices to
-their ancestors in a search tree. So for edge (u,v) the vertex v must be the ancestor of vertex u. Self
-loops are considered to be back edges. Forward edges are non-tree edges (u,v) that connect a vertex u
-to a descendant v in a search tree. Cross edges are edges that do not fall into the above three categories.
-
-[h4 Breadth-First Search]
-Breadth-first search (BFS) is a traversal through a graph that touches all of the vertices reachable
-from a particular source vertex. In addition, the order of the traversal is such that the algorithm
-will explore all of the neighbors of a vertex before proceeding on to the neighbors of its neighbors.
-One way to think of breadth-first search is that it expands like a wave emanating from a stone dropped
-into a pool of water. Vertices in the same ``wave'' are the same distance from the source vertex. A
-vertex is discovered the first time it is encountered by the algorithm. A vertex is finished after
-all of its neighbors are explored. Here's an example to help make this clear. A graph is shown in
-Figure 6 and the BFS discovery and finish order for the vertices is shown below.
-
-[$../images/review_bfs.gif]
-
- order of discovery: s r w v t x u y
- order of finish: s r w v t x u y
-
-We start at vertex , and first visit r and w (the two neighbors of ). Once both neighbors of are visited,
-we visit the neighbor of r (vertex v), then the neighbors of w (the discovery order between r and w does
-not matter) which are t and x. Finally we visit the neighbors of t and x, which are u and y.
-
-For the algorithm to keep track of where it is in the graph, and which vertex to visit next, BFS needs
-to color the vertices (see the section on Property Maps for more details about attaching properties to
-graphs). The place to put the color can either be inside the graph, or it can be passed into the algorithm
-as an argument.
-
-[h4 Depth-First Search]
-A depth-first search (DFS) visits all the vertices in a graph. When choosing which edge to explore next,
-this algorithm always chooses to go ``deeper'' into the graph. That is, it will pick the next adjacent
-unvisited vertex until reaching a vertex that has no unvisited adjacent vertices. The algorithm will then
-backtrack to the previous vertex and continue along any as-yet unexplored edges from that vertex. After DFS
-has visited all the reachable vertices from a particular source vertex, it chooses one of the remaining
-undiscovered vertices and continues the search. This process creates a set of depth-first trees which together
-form the depth-first forest. A depth-first search categorizes the edges in the graph into three categories:
-tree-edges, back-edges, and forward or cross-edges (it does not specify which). There are typically many
-valid depth-first forests for a given graph, and therefore many different (and equally valid) ways to
-categorize the edges.
-
-One interesting property of depth-first search is that the discover and finish times for each vertex form
-a parenthesis structure. If we use an open-parenthesis when a vertex is discovered, and a close-parenthesis
-when a vertex is finished, then the result is a properly nested set of parenthesis. Figure 7 shows DFS applied
-to an undirected graph, with the edges labeled in the order they were explored. Below we list the vertices of
-the graph ordered by discover and finish time, as well as show the parenthesis structure. DFS is used as the
-kernel for several other graph algorithms, including topological sort and two of the connected component
-algorithms. It can also be used to detect cycles (see the Cylic Dependencies section of the File Dependency
-Example).
-
-[$../images/review_dfs.gif]
-
- order of discovery: a b e d c f g h i
- order of finish: d f c e b a
- parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)
-
-[h4 Minimum Spanning Tree Problem]
-The minimum-spanning-tree (MST) problem is defined as follows: Given a graph /G=(V,E)/ find an acyclic
-subset /T/ of /E/ that connects all of the vertices in the graph and whose total weight is minimized, where
-the total weight is given by
-
-/w(T)/ = sum of /w(u,v)/ over all /(u,v)/ in T, where /w(u,v)/ is the weight on the edge /(u,v)/.
-
-/T/ is called the minimum spanning tree of /G/. It is important to note that a graph may have multiple MSTs.
-
-[h4 Shortest-Paths Algorithms]
-One of the classic problems in graph theory is to find the shortest path between two vertices in a graph.
-Formally, a path is a sequence of vertices <v0,v1,...,vk> in a graph G = (V, E) such that each vertex is
-connected to the next vertex in the sequence (the edges (vi,vi+1) for i=0,1,...,k-1 are in the edge set E).
-In the shortest-path problem, each edge is given a real-valued weight. We can therefore talk about the weight
-of a path
-
-/w(p)/ = sum from /i=1..k/ of /w(vi-1,vi)/
-
-The shortest path weight from vertex /u/ to /v/ is then
-
-/delta(u,v)/ = min /{ w(p) : u --> v }/ if there is a path from u to v
-/delta(u,v)/ = infinity otherwise.
-
-A shortest path is any path who's path weight is equal to the shortest path weight. So there may be several
-shortest paths within the same graph.
-
-There are several variants of the shortest path problem. Above we defined the single-pair problem, but there
-is also the single-source problem (all shortest paths from one vertex to every other vertex in the graph),
-the equivalent single-destination problem, and the all-pairs problem. It turns out that there are no
-algorithms for solving the single-pair problem that are asymptotically faster than algorithms that solve
-the single-source problem.
-
-A shortest-paths tree rooted at vertex in graph /G=(V,E)/ is a directed subgraph where /V'/ is a subset of
-/V/ and /E'/ is a subset of /(E, V')/ is the set of vertices reachable from , /G'/ forms a rooted tree with
-root , and for all /v/ in /V'/ the unique simple path from to /v/ in /G'/ is a shortest path from to /v/ in
-/G/. The result of a single-source algorithm is a shortest-paths tree.
-
-[h4 Network Flow Algorithms]
-A flow network is a directed graph /G=(V,E)/ with a source vertex /s/ and a sink vertex /t/. Each edge has
-a positive real valued capacity function c and there is a flow function f defined over every vertex pair.
-The flow function must satisfy three contraints:
-
-* /f(u,v) <= c(u,v)/ for all /(u,v)/ in /V/x /V/ (Capacity constraint)
-* /f(u,v) = -f(v,u)/ for all /(u,v)/ in /V/ x /V/ (Skew symmetry)
-* sum /v/ in /V/ /f(u,v)/ = 0 for all /u/ in /V/ - /{s,t}/ (Flow conservation)
-
-The flow of the network is the net flow entering the sink vertex t (which is equal to the net flow leaving
-the source vertex s).
-
-/|f|/ = sum /u/ in /V/ /f(u,t)/ = sum /v/ in /V/ /f(s,v)/
-
-The residual capacity of an edge is /r(u,v)/ = /c(u,v) - f(u,v)/. The edges with /r(u,v) > 0/ are residual
-edges /Ef/ which induce the residual graph /Gf = (V, Ef)/. An edge with /r(u,v) = 0/ is saturated.
-
-The maximum flow problem is to determine the maximum possible value for |/f/| and the corresponding flow
-values for every vertex pair in the graph. A flow network is shown in Figure 8. Vertex A is the source
-vertex and H is the target vertex.
-
-[$../images/review_flow.gif]
-
-Edges are labeled with the flow and capacity values. There is a long history of algorithms for solving the
-maximum flow problem, with the first algorithm due to Ford and Fulkerson. The best general purpose algorithm
-to date is the push-relabel algorithm of Goldberg which is based on the notion of a preflow introduced by
-Karzanov.
-
-[endsect]
\ No newline at end of file
Deleted: trunk/libs/graph/quickbook/tour.qbk
==============================================================================
--- trunk/libs/graph/quickbook/tour.qbk 2009-09-02 10:23:27 EDT (Wed, 02 Sep 2009)
+++ (empty file)
@@ -1,522 +0,0 @@
-[/
- / 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 A Quick tour of Boost.Graph]
-The domain of graph data structures and algorithms is in some respects more
-complicated than that of containers. The abstract iterator interface used by
-STL is not sufficiently rich to encompass the numerous ways that graph
-algorithms may traverse a graph. Instead, we formulate an abstract interface
-that serves the same purpose for graphs that iterators do for basic containers
-(though iterators still play a large role). Figure 1 depicts the analogy between
-the STL and
-Boost.Graph.
-
-[$../images/tour_analogy.gif]
-
-The graph abstraction consists of a set of vertices (or nodes), and a set of
-edges (or arcs) that connect the vertices. Figure 2 depicts a directed graph
-with five vertices (labeled 0 through 4) and 11 edges. The edges leaving a
-vertex are called the out-edges of the vertex. The edges {(0,1),(0,2),(0,3),(0,4)}
-are all out-edges of vertex 0. The edges entering a vertex are called the in-edges
-of the vertex. The edges {(0,4),(2,4),(3,4)} are all in-edges of vertex 4.
-
-[$../images/tour_graph.png]
-
-In the following sections we will use Boost.Graph to construct this example
-graph and manipulate it in various ways. The complete source code for this
-example can be found in `examples/quick_tour.cpp`. Each of the following
-sections discusses a "slice" of this example file. Excerpts from the output of
-the example program will also be listed.
-
-[h2 Constructing the Graph]
-
-In this example
-
-[h2 Constructing the Graph]
-In this example we will use the [adjacency_list] class to demonstrate the main
-ideas in the Boost.Graph interface. The [adjacency_list] class provides a
-generalized version of the classic /adjacency list/ data structure. The
-[adjacency_list] class is a template class with six template parameters, though
-here we only fill in the first three parameters and use the defaults for the
-remainder. The first two template arguments (`vecS`, `vecS`) determine the data
-structure used to represent the out-edges for each vertex in the graph and the
-data structure used to represent the graph's vertex set (see section Choosing
-the Edgelist and VertexList for information about the tradeoffs of the different
-data structures). The third argument, `bidirectionalS`, selects a directed graph
-that provides access to both out and in-edges. The other options for the third
-argument are `directedS` which selects a directed graph with only out-edges, and
-`undirectedS` which selects an undirected graph.
-
-Once we have the graph type selected, we can create the graph in Figure 2 by
-declaring a graph object and filling in edges using the add_edge() function of
-the MutableGraph interface (which `adjacency_list<>` implements). We use the
-array of pairs edge_array merely as a convenient way to explicitly create the
-edges for this example.
-
- #include <iostream> // for std::cout
- #include <utility> // for std::pair
- #include <algorithm> // for std::for_each
- #include <boost/graph/adjacency_list.hpp>
-
- using namespace std;
- using namespace boost;
-
- int main(int, char*[])
- {
- // create a typedef for the Graph type
- typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
-
- // Make convenient labels for the vertices
- enum { A, B, C, D, E, N };
- const int num_vertices = N;
- const char* name = "ABCDE";
-
- // Create edges as pairs of of intengers
- typedef pair<int, int> Edge;
- Edge edge_array[] = {
- Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
- Edge(C,E), Edge(B,D), Edge(D,E)
- };
- const int num_edges = sizeof(edge_array) / sizeof(edge_array[0]);
-
- // Declare a graph object with N vertices
- Graph g(num_vertices);
-
- // Add the edges to the graph
- for (int i = 0; i < num_edges; ++i) {
- add_edge(edge_array[i].first, edge_array[i].second, g);
- }
-
- // ... continue below
- return 0;
- }
-
-Instead of calling the `add_edge()` function for each edge, we could use the
-edge iterator constructor of the graph. This is typically more efficient than
-using `add_edge()`. Pointers to the `edge_array` can be viewed as iterators, so
-we can call the iterator constructor by passing pointers to the beginning and
-end of the array.
-
- Graph g(edges, edges + sizeof(edge_array) / sizeof(edge_array[0]), num_vertices);
-
-Instead of creating a graph with a certain number of vertices to begin with, it
-is also possible to add and remove vertices with the [add_vertex] and
-[remove_vertex] functions, also of the [MutableGraph] interface.
-
-[h2 Accessing the Vertex Set]
-Now that we have created a graph, we can use the graph interface to access the graph data in
-different ways. First we can access all of the vertices in the graph using the `vertices()` function
-of the /VertexListGraph/ interface. This function returns a `std::pair<>` of vertex iterators (the first
-iterator points to the "beginning" of the vertices and the second iterator points "past the end").
-Dereferencing a vertex iterator gives a vertex object. The type of the vertex iterator is given by
-the graph_traits class. Note that different graph classes can have different associated vertex
-iterator types, which is why we need the `graph_traits<>` class. Given some graph type, the `graph_traits<>`
-class will provide access to the vertex_iterator type.
-
-The following example prints out the index for each of the vertices in the graph. All vertex and
-edge properties, including index, are accessed via property map objects. The `property_map<>` class is
-used to obtain the property map type for a specific property (specified by `vertex_index_t`, one of the
-Boost.Graph predefined properties) and function call `get(vertex_index, g)` returns the actual
-property map object.
-
-
- // ...
- int main(int,char*[])
- {
- // ... continued from above
-
- // Get the property map for vertex indices
- typedef property_map<Graph, vertex_index_t>::type IndexMap;
- IndexMap index = get(vertex_index, g);
-
- cout << "vertices(g) = ";
- typedef graph_traits<Graph>::vertex_iterator vertex_iter;
- pair<vertex_iter, vertex_iter> vp;
- for(vp = vertices(g); vp.first != vp.second; ++vp.first) {
- cout << index[*vp.first] << " ";
- }
- cout << "\n";
-
- // ...
- return 0;
- }
-
-The output is:
-
-[pre
- vertices(g) = 0 1 2 3 4
-]
-
-[h2 Accessing the Edge Set]
-The set of edges for a graph can be accessed with the edges() function of the /EdgeListGraph/ interface.
-Similar to the `vertices()` function, this returns a pair of iterators, but in this case the iterators
-are edge iterators. Dereferencing an edge iterator gives an edge object. The `source()` and `target()`
-functions return the two vertices that are connected by the edge. Instead of explicitly creating a
-`std::pair<>` for the iterators, this time we will use the `tie()` helper function. This handy function
-can be used to assign the parts of a std::pair into two separate variables, in this case `ei`
-and `ei_end`. This is usually more convenient than creating a `std::pair` and is our method of
-choice for Boost.Graph.
-
- // ...
- int main(int,char*[])
- {
- // ... continued from above
- cout << "edges(g) = ";
- graph_traits<Graph>::edge_iterator ei, ei_end;
- for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
- cout << "(" << index[source(*ei, g)] << "," << index[target(*ei, g)] << ") ";
- }
- cout << "\n";
-
- // ...
- return 0;
- }
-
-The output is:
-[pre
- edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0) (3,1) (3,4) (4,0) (4,1)
-]
-
-[h2 The Adjacency Structure]
-In the next few examples we will explore the adjacency structure of the graph from the point of
-view of a particular vertex. We will look at the vertices' in-edges, out-edges, and its adjacent
-vertices. We will encapsulate this in an "exercise vertex" function, and apply it to each vertex
-in the graph. To demonstrate the STL-interoperability of Boost.Graph, we will use the STL `for_each()`
-function to iterate through the vertices and apply the function.
-
- //...
- int main(int,char*[])
- {
- // ...
- for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g));
- return 0;
- }
-
-We use a functor for exercise_vertex instead of just a function because the graph object will be
-needed when we access information about each vertex; using a functor gives us a place to keep a
-reference to the graph object during the execution of the `std::for_each()`. Also we template the
-functor on the graph type so that it is reusable with different graph classes. Here is the start
-of the exercise_vertex functor:
-
- template <class Graph> struct exercise_vertex {
- exercise_vertex(Graph& g_) : g(g_)
- { }
-
- // ...
-
- Graph& g;
- };
-
-[h3 Vertex Descriptors]
-The first thing we need to know in order to write the operator() method of the functor is the type
-for the vertex objects of the graph. The vertex type will be the parameter to the `operator()`
-method. To be precise, we do not deal with actual vertex objects, but rather with vertex descriptors.
-Many graph representations (such as adjacency lists) do not store actual vertex objects, while
-others do (e.g., pointer-linked graphs). This difference is hidden underneath the "black-box"
-of the vertex descriptor object. The vertex descriptor is something provided by each graph type
-that can be used to access information about the graph via the `out_edges()`, `in_edges()`,
-`adjacent_vertices()`, and property map functions that are described in the following sections. The
-vertex_descriptor type is obtained through the graph_traits class. The typename keyword used below
-is necessary because the type on the left hand side of the scope :: operator (the `graph_traits<Graph>`
-type) is dependent on a template parameter (the `Graph` type). Here is how we define the functor's
-apply method:
-
- template <class Graph> struct exercise_vertex {
- // ... continued from above
-
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- void operator()(const Vertex& v) const
- {
- // ... this is where we will "exercise" the vertex
- }
-
- // ...
- };
-
-[h3 Out-Edges, In-Edges, and Edge Descriptors]
-The out-edges of a vertex are accessed with the `out_edges()` function of the /IncidenceGraph/
-interface. The out_edges() function takes two arguments: the first argument is the vertex and
-the second is the graph object. The function returns a pair of iterators which provide access
-to all of the out-edges of a vertex (similar to how the vertices() function returned a pair of
-iterators). The iterators are called out-edge iterators and dereferencing one of these iterators
-gives an edge descriptor object. An edge descriptor plays the same kind of role as the vertex
-descriptor object, it is a "black box" provided by the graph type. The following code snippet prints
-the source-target pairs for each out-edge of vertex, v.
-
- template <class Graph>
- struct exercise_vertex {
- //... continued from above
-
- void operator()(const Vertex& v) const
- {
- typedef graph_traits<Graph> GraphTraits;
- typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
- IndexMap index = get(vertex_index, g);
-
- cout << "out-edges: ";
- typename GraphTraits::out_edge_iterator out_i, out_end;
- typename GraphTraits::edge_descriptor e;
- for(tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) {
- e = *out_i;
- Vertex src = source(e, g), tgt = target(e, g);
- cout << "(" << index[src] << "," << index[targ] << ") ";
- }
- std::cout << "\n";
-
- // ...
- }
-
- // ...
- };
-
-For vertex 0 the output is:
-[pre
- out-edges: (0,1) (0,2) (0,3) (0,4)
-]
-
-The `in_edges()` function of the BidirectionalGraph interface provides access to all the in-edges
-of a vertex through in-edge iterators. The in_edges() function is only available for the
-`adjacency_list<>` if `bidirectionalS` is supplied for the Directed template parameter. There is an
-extra cost in space when `bidirectionalS` is specified instead of `directedS`.
-
- template <class Graph> struct exercise_vertex {
- // ... continued from above
-
- void operator()(const Vertex& v) const
- {
- // ...
- cout << "in-edges: ";
- typedef typename graph_traits<Graph> GraphTraits;
- typename GraphTraits::in_edge_iterator in_i, in_end;
- for (tie(in_i, in_end) = in_edges(v,g); in_i != in_end; ++in_i) {
- e = *in_i;
- Vertex src = source(e, g), targ = target(e, g);
- cout << "(" << index[src] << "," << index[targ] << ") ";
- }
- cout << "\n";
- // ...
- }
-
- // ...
- };
-
-For vertex 0 the output is:
-[pr
- in-edges: (2,0) (3,0) (4,0)
-]
-
-[h3 Adjacent Vertices]
-Given the out-edges of a vertex, the target vertices of these edges are adjacent to the source
-vertex. Sometimes an algorithm does not need to look at the edges of the graph and only cares
-about the vertices. Therefore the graph interface also includes the `adjacent_vertices()` function
-of the AdjacencyGraph interface which provides direct access to the adjacent vertices. This function
-returns a pair of adjacency iterators. Dereferencing an adjacency iterator gives a vertex descriptor
-for an adjacent vertex.
-
- template <class Graph> struct exercise_vertex {
- // ... continued from above
-
- void operator()(Vertex v) const
- {
- //...
- cout << "adjacent vertices: ";
- typename graph_traits<Graph>::adjacency_iterator ai;
- typename graph_traits<Graph>::adjacency_iterator ai_end;
- for(tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end; ++ai) {
- std::cout << index[*ai] << " ";
- }
- std::cout << "\n";
- }
-
- //...
- };
-
-For vertex 4 the output is:
-[pre
- adjacent vertices: 0 1
-]
-
-[Adding Some Color to your Graph]
-Boost.Graph attempts to be as flexible as possible in terms of accommodating how properties are
-attached to a graph. For instance, a property such as edge weight may need to be used throughout
-a graph object's lifespan and therefore it would be convenient to have the graph object also manage
-the property storage. On the other hand, a property like vertex color may only be needed for the
-duration of a single algorithm, and it would be better to have the property stored separately from
-the graph object. The first kind of property is called an internally stored property while the second
-kind is called an externally stored property. Boost.Graph uses a uniform mechanism to access both kinds of
-properties inside its graph algorithms called the property map interface, described in Section
-Property Map Concepts. In addition, the PropertyGraph concept defines the interface for obtaining
-a property map object for an internally stored property.
-
-The Boost.Graph adjacency_list class allows users to specify internally stored properties through plug-in
-template parameters of the graph class. How to do this is discussed in detail in Section Internal
-Properties. Externally stored properties can be created in many different ways, although they are
-ultimately passed as separate arguments to the graph algorithms. One straightforward way to store
-properties is to create an array indexed by vertex or edge index. In the adjacency_list with `vecS`
-specified for the VertexList template parameter, vertices are automatically assigned indices, which
-can be accessed via the property map for the vertex_index_t. Edges are not automatically assigned
-indices. However the property mechanism can be used to attach indices to the edges which can be
-used to index into other externally stored properties.
-
-In the following example, we construct a graph and apply `dijkstra_shortest_paths()`. The complete
-source code for the example is in examples/dijkstra-example.cpp. Dijkstra's algorithm computes the
-shortest distance from the starting vertex to every other vertex in the graph.
-
-Dijkstra's algorithm requires that a weight property is associated with each edge and a distance
-property with each vertex. Here we use an internal property for the weight and an external property
-for the distance. For the weight property we use the property class and specify int as the type used
-to represent weight values and edge_weight_t for the property tag (which is one of the Boost.Graph
-predefined property tags). The weight property is then used as a template argument for `adjacency_list<>`.
-The listS and vecS types are selectors that determine the data structure used inside the
-`adjacency_list<>` (see Section Choosing the Edgelist and VertexList). The directedS type specifies
-that the graph should be directed (versus undirected). The following code shows the specification of
-the graph type and then the initialization of the graph. The edges and weights are passed to the
-graph constructor in the form of iterators (a pointer qualifies as a /RandomAccessIterator/).
-
- typedef adjacency_list<listS, vecS, directedS,
- no_property, // no additional vertex properties
- property<edge_weight_t, int> // edges have integer edge weight
- > Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef std::pair<int,int> E;
-
- const int num_nodes = 5;
- E edges[] = { E(0,2),
- E(1,1), E(1,3), E(1,4),
- E(2,1), E(2,3),
- E(3,4),
- E(4,0), E(4,1) };
- int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};
-
- Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
-
-For the external distance property we will use a std::vector for storage. Boost.Graph algorithms treat
-random access iterators as property maps, so we can just pass the beginning iterator of the
-distance vector to Dijkstra's algorithm. Continuing the above example, the following code shows
-the creation of the distance vector, the call to Dijkstra's algorithm (implicitly using the
-internal edge weight property), and then the output of the results.
-
- // vector for storing distance property
- std::vector<int> d(num_vertices(G));
-
- // get the first vertex
- Vertex s = *(vertices(G).first);
-
- // invoke variant 2 of Dijkstra's algorithm
- dijkstra_shortest_paths(G, s, distance_map(&d[0]));
-
- std::cout << "distances from start vertex:" << ;
- graph_traits<Graph>::vertex_iterator vi;
- for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
- std::cout << "distance(" << index(*vi) << ") = "
- << d[*vi] << ;
- std::cout << ;
-
-The output is:
-[pre
- distances from start vertex:
- distance(0) = 0
- distance(1) = 6
- distance(2) = 1
- distance(3) = 4
- distance(4) = 5
-]
-
-[Extending Algorithms with Visitors]
-Often times an algorithm in a library almost does what you need, but not quite. For example, in
-the previous section we used Dijkstra's algorithm to calculate the shortest distances to each
-vertex, but perhaps we also wanted to record the tree of shortest paths. One way to do this is
-to record the predecessor (parent) for each node in the shortest-paths tree.
-
-It would be nice if we could avoid rewriting Dijkstra's algorithm, and just add that little bit
-extra needed to record the predecessors [1]. In the STL, this kind of extensibility is provided
-by functors, which are optional parameters to each algorithm. In Boost.Graph this role is
-fulfilled by visitors.
-
-A visitor is like a functor, but instead of having just one "apply" method, it has several.
-Each of these methods get invoked at certain well-defined points within the algorithm. The visitor
-methods are explained in detail in Section Visitor Concepts. Boost.Graph provides a number of visitors
-for some common tasks including a predecessor recording visitor. The user is encouraged to write
-his or her own visitors as a way of extending Boost.Graph. Here we will take a quick look at the
-implementation and use of the predecessor recorder. Since we will be using the
-`dijkstra_shortest_paths()` algorithm, the visitor we create must be a Dijkstra Visitor.
-
-The functionality of the record_predecessors visitor is separated into two parts. For the storage
-and access of the predecessor property, we will use a property map. The predecessor visitor will
-then only be responsible for what parent to record. To implement this, we create a
-`record_predecessors` class and template it on the predecessor property map `PredecessorMap`. Since
-this visitor will only be filling in one of the visitor methods, we will inherit from
-`dijkstra_visitor` which will provide empty methods for the rest. The constructor of the
-`predecessor_recorder` will take the property map object and save it away in a data member.
-
- template <class PredecessorMap>
- class record_predecessors : public dijkstra_visitor<>
- {
- public:
- record_predecessors(PredecessorMap p)
- : m_predecessor(p)
- { }
-
- template <class Edge, class Graph>
- void edge_relaxed(Edge e, Graph& g) {
- // set the parent of the target(e) to source(e)
- put(m_predecessor, target(e, g), source(e, g));
- }
- protected:
- PredecessorMap m_predecessor;
- };
-
-The job of recording the predecessors is quite simple. When Dijkstra's algorithm relaxes an edge
-(potentially adding it to the shortest-paths tree) we record the source vertex as the predecessor
-of the target vertex. Later, if the edge is relaxed again the predecessor property will be
-overwritten by the new predecessor. Here we use the put() function associated with the
-property map to record the predecessor. The `edge_filter` of the visitor tells the algorithm when
-to invoke the `explore()` method. In this case we only want to be notified about edges in the
-shortest-paths tree so we specify `tree_edge_tag`.
-
-As a finishing touch, we create a helper function to make it more convenient to create predecessor
-visitors. All Boost.Graph visitors have a helper function like this.
-
- template <class PredecessorMap>
- record_predecessors<PredecessorMap>
- make_predecessor_recorder(PredecessorMap p) {
- return record_predecessors<PredecessorMap>(p);
- }
-
-We are now ready to use the `record_predecessors` in Dijkstra's algorithm. Luckily, Boost.Graph's
-Dijkstra's algorithm is already equipped to handle visitors, so we just pass in our new visitor.
-In this example we only need to use one visitor, but Boost.Graph is also equipped to handle the use
-of multiple visitors in the same algorithm (see Section Visitor Concepts).
-
- using std::vector;
- using std::cout;
- using std::endl;
- vector<Vertex> p(num_vertices(G)); //the predecessor array
- dijkstra_shortest_paths(G, s, distance_map(&d[0]).
- visitor(make_predecessor_recorder(&p[0])));
-
- cout << "parents in the tree of shortest paths:" << endl;
- for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
- cout << "parent(" << *vi;
- if (p[*vi] == Vertex())
- cout << ") = no parent" << endl;
- else
- cout << ") = " << p[*vi] << endl;
- }
-
-The output is:
-[pre
- parents in the tree of shortest paths:
- parent(0) = no parent
- parent(1) = 4
- parent(2) = 0
- parent(3) = 2
- parent(4) = 3
-]
-
-[endsect]
\ No newline at end of file
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk