|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-07-11 10:41:51
Author: asutton
Date: 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
New Revision: 7406
URL: http://svn.boost.org/trac/boost/changeset/7406
Log:
Added reference material for some specific event visitor classes.
Finished writing concept docs for various visitors.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distance_recorder.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/predecessor_recorder.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/property_writer.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/time_stamper.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/sgi_concepts.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk | 76 +++++++++++++++++------------------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk | 2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk | 83 +++++++++++++++++++++++----------------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk | 6 +-
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk | 22 +++++-----
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk | 3 +
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk | 76 +-----------------------------------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk | 7 +++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk | 14 ++++--
10 files changed, 125 insertions(+), 168 deletions(-)
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,37 @@
+[/
+ / 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)
+ /]
+
+[/
+ / This file contains Boost-defined concepts
+ /]
+
+[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
+
+[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
+[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
+[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
+
+[template BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor Descriptor]]
+[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
+[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
+[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
+[template BoostVertexListGraph[] [link boost_graph.concepts.graph_concepts.vertex_list_graph VertexListGraph]]
+[template BoostEdgeListGraph[] [link boost_graph.concepts.graph_concepts.edge_list_graph EdgeListGraph]]
+[template BoostAdjacencyGraph[] [link boost_graph.concepts.graph_concepts.adjacency_graph AdjacencyGraph]]
+[template BoostAdjacencyMatrix[] [link boost_graph.concepts.graph_concepts.adjacency_matrix AdjacencyMatrix]]
+[template BoostMutableGraph[] [link boost_graph.concepts.graph_concepts.mutable_graph MutableGraph]]
+[template BoostPropertyGraph[] [link boost_graph.concepts.graph_concepts.property_graph PropertyGraph]]
+[template BoostMutablePropertyGraph[] [link boost_graph.concepts.graph_concepts.mutable_property_graph MutablePropertyGraph]]
+
+[template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
+[template BoostBFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
+[template BoostDFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
+[template BoostDijkstraVisitor[] [link boost_graph.concepts.visitor_concepts.dijksta_visitor DijkstraVisitor]]
+[template BoostBellmanfordVisitor[] [link boost_graph.concepts.visitor_concepts.bellmanford_visitor BellmanFordVisitor]]
+[template BoostAStarVisitor[] [link boost_graph.concepts.visitor_concepts.a_star_visitor A\*Visitor]]
+[template BoostEventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
+[template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,37 @@
+[/
+ / 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)
+ /]
+
+[/
+ / This file contains references to Boost.Graph reference docs
+ /]
+
+[/ Graph traits and types /]
+[template boost_graph_traits[] [link boost_graph.reference_guide.traits_classes.graph_traits [^graph_traits]]]
+[template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph [^undirected_graph]]]
+[template boost_directed_graph[] [link boost_graph.reference_guide.graph_types.directed_graph [^directed_graph]]]
+[template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list [^adjacecncy_list]]]
+[template boost_edge_list[] [link boost_graph.reference_guide.graph_types.edge_list [^edge_list]]]
+
+[/ Visitor types /]
+[template boost_null_visitor[] [link boost_graph.reference_guide.visitor_types.null_visitor [^null_visitor]]]
+[template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor [^bfs_visitor]]]
+[template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor [^dfs_visitor]]]
+[template boost_predecessor_recorder[] [link boost.graph_reference_guide.event_visitors.predecessor_recorder [^predecessor_recorder]]]
+[template boost_distance_recorder[] [link boost.graph_reference_guide.event_visitors.distance_recorder [^distance_recorder]]]
+[template boost_time_stamper[] [link boost.graph_reference_guide.event_visitors.time_stamper [^time_stamper]]]
+[template boost_property_writer[] [link boost.graph_reference_guide.event_visitors.property_writer [^property_writer]]]
+
+[/ Core algorithms /]
+[template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search [^breadth_first_search()]]]
+[template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search [^depth_first_search()]]]
+
+[/ Path algorithms /]
+[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths [^dijkstra_shortest_paths()]]]
+[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths [^bellman_ford_shortest_paths()]]]
+
+
+[template boost_connected_components[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -5,68 +5,66 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Graph]
-The Graph concept contains a few requirements that are common to all the graph concepts.
-These include some associated types for vertex_descriptor, edge_descriptor, etc. One
-should note that a model of Graph is not required to be a model of Assignable, so algorithms
-should pass graph objects by reference (or `const` reference).
+[section Bellman Ford Visitor]
+This concept defines the visitor interface for [boost_bellman_ford_shortest_paths]. Users
+can define a class with the Bellman Ford Visitor interface and pass and object of the
+class to [boost_bellman_ford_shortest_paths], thereby augmenting the actions taken during the
+graph search.
-[h4 Associated Types]
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
[table
- [[Type] [Description]]
- [
- [`graph_traits<G>::vertex_descriptor`]
- [
- A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
- must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
- descriptors are almost always passed by value.
- ]
- ]
+ [[Expression] [Description]]
[
- [`graph_traits<G>::edge_descriptor`]
+ [`vis.examine_edge(v,g)`]
[
- An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
- must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
- are almost always passed by value.
+ This is invoked on every out-edge of each vertex after it is discovered.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::directed_category`]
+ [`vis.edge_relaxed(e,g)`]
[
- This type shall be convertible to `directed_tag` or `undirected_tag`.
+ If the relaxation predicate holds for this given edge then this method is invoked.
+ See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::edge_parallel_category`]
+ [`vis.edge_not_relaxed(e,g)`]
[
- This describes whether the graph class allows the insertion of parallel edges
- (multiple edges between the same source and target vertices). The two tags are
- `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+ If the relaxation predicate does not hold for this edge, then this method is invoked.
+ See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::traversal_category`]
+ [`vis.edge_minimized(e,g)`]
[
- This describes the ways in which the vertices and edge of the graph can be visited.
- The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
- `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+ After the `num_vertices(g)` iterators through the edge det of the graph is complete,
+ one last iteration is made to test whether each edge was minimized. If the edge is
+ minimized then this function is invoked.
+
+ *Returns* `void`
]
]
-]
-
-[h4 Valid Expressions]
-[table
- [[Expression] [Description]]
[
- [`graph_traits<G>::null_vertex()`]
+ [`vis.edge_relaxed(e,g)`]
[
- Returns a special `vertex_descriptor` which does not refer to any vertex for graphs
- of type `G`. Note that default initialization of `vertex_descriptors` are /not/
- guaranteed to be equal to then `null_vertex()`.
+ If the edge is not minimized then this function is invoked. This happens when there
+ is a negative weight cycle in the graph.
- *Returns* `vertex_descriptor`
+ *Returns* `void`
]
]
]
+[h4 Models]
+* [boost_bellman_ford_visitor]
+
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -36,7 +36,7 @@
[`vis.examine_vertex(v,g)`]
[
This is invoked on a vertex as it is popped from the queue. This happens immediately
- before `examine_edge(v,g)` s invoked on each of the out-edges of vertex `u`.
+ before `examine_edge(v,g)` s invoked on each of the out-edges of vertex `v`.
*Returns* `void`
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -5,68 +5,83 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Graph]
-The Graph concept contains a few requirements that are common to all the graph concepts.
-These include some associated types for vertex_descriptor, edge_descriptor, etc. One
-should note that a model of Graph is not required to be a model of Assignable, so algorithms
-should pass graph objects by reference (or `const` reference).
+[section Dijkstra Visitor]
+This concept defines the visitor interface for [boost_dijkstra_shortest_paths] and related
+algorithms. The user can create a class that matches this interface, and then pass objects
+of the class into [boost_dijkstra_shortest_paths] to augment the actions taken during the
+search.
-[h4 Associated Types]
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
[table
- [[Type] [Description]]
+ [[Expression] [Description]]
[
- [`graph_traits<G>::vertex_descriptor`]
+ [`vis.initialize_vertex(v,g)`]
[
- A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
- must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
- descriptors are almost always passed by value.
+ This is invoked on every vertex of the graph before the start of the graph search.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::edge_descriptor`]
+ [`vis.discover_vertex(v,g)`]
[
- An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
- must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
- are almost always passed by value.
+ This is invoked when a vertex is encountered for the first time. This happens immediately
+ before `examine_edge()` is invoked on each of the out-edges of `v`.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::directed_category`]
+ [`vis.examine_vertex(v,g)`]
[
- This type shall be convertible to `directed_tag` or `undirected_tag`.
+ This is invoked on a vertex as it is popped from the queue. This happens immediately
+ before `examine_edge(v,g)` s invoked on each of the out-edges of vertex `v`.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::edge_parallel_category`]
+ [`vis.examine_edge(v,g)`]
[
- This describes whether the graph class allows the insertion of parallel edges
- (multiple edges between the same source and target vertices). The two tags are
- `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+ This is invoked on every out-edge of each vertex after it is discovered.
+
+ *Returns* `void`
]
]
[
- [`graph_traits<G>::traversal_category`]
+ [`vis.edge_relaxed(e,g)`]
[
- This describes the ways in which the vertices and edge of the graph can be visited.
- The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
- `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+ If the relaxation predicate holds for this given edge then this method is invoked.
+ See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+ *Returns* `void`
]
]
-]
+ [
+ [`vis.edge_not_relaxed(e,g)`]
+ [
+ If the relaxation predicate does not hold for this edge, then this method is invoked.
+ See [boost_dijkstra_shortest_paths] for more information on relaxation.
-[h4 Valid Expressions]
-[table
- [[Expression] [Description]]
+ *Returns* `void`
+ ]
+ ]
[
- [`graph_traits<G>::null_vertex()`]
+ [`vis.finish_vertex(v,g)`]
[
- Returns a special `vertex_descriptor` which does not refer to any vertex for graphs
- of type `G`. Note that default initialization of `vertex_descriptors` are /not/
- guaranteed to be equal to then `null_vertex()`.
+ This is invoked on a vertex after all of its out edges have been added to the search
+ tree and all of the adjacent vertices have been discovered (but before their out edgs)
+ have been examined).
- *Returns* `vertex_descriptor`
+ *Returns* `void`
]
]
]
+[h4 Models]
+* [boost_dijkstra_visitor]
+
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -13,7 +13,7 @@
and how to use an algorithm's visitor adaptor class.
Suppose we would like to print out the parenthesis structure of the discover/finish times
-of vertices in a depth-first search. We can use the Boost.Graph algorithm `depth_first_search()`
+of vertices in a depth-first search. We can use the Boost.Graph algorithm [boost_depth_first_search]
and two event visitors to accomplish this. The complete source code for the following example
is in `examples/dfs_parenthesis.cpp`. First we define the two event visitors. We use
`on_discover_vertex` and `on_finish_vertex` as the event points, selected from the list of
@@ -47,14 +47,14 @@
make_pair(open_paren(), close_paren());
-Next we want to pass this list into `depth_first_search()`, but `depth_first_search()` is
+Next we want to pass this list into [boost_depth_first_search], but it is
expecting a [BoostDFSVisitor], not a [EventVisitorList]. We therefore use the [boost_dfs_visitor]
adaptor which turns an [BoostEventVisitor] list into a [BoostDFSVisitor]. Like all of the visitor
adaptors, [dfs_visitor] has a creation function called [boost_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 [boost_depth_first_search] as follows.
depth_first_search(
G,
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -35,42 +35,42 @@
[table
[[Expression] [Return Type or Description]]
- [[*[BoostGraph]*]]
+ [[[*[BoostGraph]]]]
[[`graph_traits<G>::vertex_descriptor`] [The type for vertex representative objects.]]
[[`graph_traits<G>::edge_descriptor`] [The type for edge representative objects.]]
[[`graph_traits<G>::directed_category`] [Graph is directed or undirected?]]
[[`graph_traits<G>::edge_parallel_category`] [Graph allows parallel edges?]]
[[`graph_traits<G>::traversal_category`] [The ways in which the vertices and edges can be traversed.]]
- [[*[BoostIncidenceGraph]* refines Graph]]
- [[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
+ [[[*[BoostIncidenceGraph]]]]
+ [[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
[[`graph_traits<G>::out_edge_iterator`] [Type for iterating over out edges.]]
[[`out_edges(v,g)`] [`std::pair<out_edge_iterator, out_edge_iterator>`]]
[[`out_degree(v,g)`] [`degree_size_type`]]
[[`source(e,g)`] [`vertex_descriptor`]]
[[`target(e,g)`] [`vertex_descriptor`]]
- [[*[BoostBidirectional Graph]* refines IncidenceGraph]]
+ [[[*[BoostBidirectionalGraph]]]]
[[`graph_traits<G>::in_edge_iterator`] [Type for iterating over in edges.]]
[[`in_edges(v,g)`] [`std::pair<in_edge_iterator,in_edge_iterator>`]]
[[`in_degree(v,g)`] [`degree_size_type`]]
[[`degree(v,g)`] [`degree_size_type`]]
- [[*[BoostAdjacencyGraph]* refines Graph]]
+ [[[*[BoostAdjacencyGraph]]]]
[[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
[[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
- [[*[BoostVertexListGraph]* refines Graph]]
+ [[[*[BoostVertexListGraph]]]]
[[`graph_traits<G>::vertex_iterator`] [Type for iterating over vertices.]]
[[`graph_traits<G>::vertices_size_type`] [Unsigned integer type for the number of vertices.]]
[[`vertices(g)`] [`std::pair<vertex_iterator,vertex_iterator>`]]
[[`num_vertices(g)`] [`vertices_size_type`]]
- [[*[BoostEdgeListGraph]* refines Graph]]
+ [[[*[BoostEdgeListGraph]]]]
[[`graph_traits<G>::edge_iterator`] [Type for iterating over edges.]]
[[`graph_traits<G>::edges_size_type`] [Unsigned integer type for the number of edges.]]
[[`edges(g)`] [`std::pair<edge_iterator, edge_iterator>`]]
[[`num_edges(g)`] [`edges_size_type`]]
[[`source(e,g)`] [`vertex_descriptor`]]
[[`target(e,g)`] [`vertex_descriptor`]]
- [[*[BoostAdjacencyMatrix]* refines Graph]]
+ [[[*[BoostAdjacencyMatrix]]]]
[[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
- [[*[BoostMutableGraph]* refines Graph]]
+ [[[*[BoostMutableGraph]]]]
[[`add_vertex(g)`] [`vertex_descriptor`]]
[[`clear_vertex(v,g)`] [`void`]]
[[`clear_out_edges(v,g)`] [`void`]]
@@ -82,13 +82,13 @@
[[`remove_edge_if(pred,g)`] [`void`]]
[[`remove_out_edge_if(v,pred,g)`] [`void`]]
[[`remove_in_edge_if(v,pred,g)`] [`void`]]
- [[*[BoostPropertyGraph]* refines Graph]]
+ [[[*[BoostPropertyGraph]]]]
[[`property_map<G,Property>::type`] [Type for a mutable property map.]]
[[`property_map<G,Property>::const_type`] [Type for a non-mutable property map.]]
[[`get(p,g)`] [Function to get a property map.]]
[[`get(p,g,x)`] [Get the property value for vertex or edge `x`]]
[[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
- [[*[BoostMutablePropertyGraph]* refines Graph]]
+ [[[*[BoostMutablePropertyGraph]]]]
[[`add_vertex(vp,g)`] [`vertex_descriptor`]]
[[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -19,6 +19,9 @@
[include visitor.qbk]
[include bfs_visitor.qbk]
[include dfs_visitor.qbk]
+[include dijkstra_visitor.qbk]
+[include bellman_ford_visitor.qbk]
[include event_visitor.qbk]
+[include event_visitor_list.qbk]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -26,79 +26,9 @@
[template super[x] '''<superscript>'''[x]'''</superscript>''']
[template sub[x] '''<subscript>'''[x]'''</subscripts>''']
-[/ Missing documentation /]
-[template NoConcept[x] [x]]
-
-[/ SGI Concept Documentation /]
-[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 SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html BidirectionalIterator]]
-[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html RandomAccessIterator]]
-
-[template SgPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
-
-
-[/ Boost Concept Documentation /]
-[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
-
-[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
-[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
-
-[template BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor Descriptor]]
-[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
-[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
-[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
-[template BoostVertexListGraph[] [link boost_graph.concepts.graph_concepts.vertex_list_graph VertexListGraph]]
-[template BoostEdgeListGraph[] [link boost_graph.concepts.graph_concepts.edge_list_graph EdgeListGraph]]
-[template BoostAdjacencyGraph[] [link boost_graph.concepts.graph_concepts.adjacency_graph AdjacencyGraph]]
-[template BoostAdjacencyMatrix[] [link boost_graph.concepts.graph_concepts.adjacency_matrix AdjacencyMatrix]]
-[template BoostMutableGraph[] [link boost_graph.concepts.graph_concepts.mutable_graph MutableGraph]]
-[template BoostPropertyGraph[] [link boost_graph.concepts.graph_concepts.property_graph PropertyGraph]]
-[template BoostMutablePropertyGraph[] [link boost_graph.concepts.graph_concepts.mutable_property_graph MutablePropertyGraph]]
-
-[template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
-[template BoostBFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
-[template BoostDFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
-[template BoostEventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
-[template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
-
-[/ Boost Reference Documentation]
-[template boost_graph_traits[] [link boost_graph.reference_guide.traits_classes.graph_traits `graph_traits`]]
-[template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph `undirected_graph`]]
-[template boost_directed_graph[] [link boost_graph.reference_guide.graph_types.directed_graph `directed_graph`]]
-[template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list `adjacecncy_list`]]
-[template boost_edge_list[] [link boost_graph.reference_guide.graph_types.edge_list `edge_list`]]
-
-[template boost_null_visitor[] [link boost_graph.reference_guide.visitor_types.null_visitor `null_visitor`]]
-[template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor `bfs_visitor`]]
-[template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor `dfs_visitor`]]
-[template boost_predecessor_recorder[] [link boost.graph_reference_guide.event_visitors.predecessor_recorder `predecessor_recorder`]]
-[template boost_distance_recorder[] [link boost.graph_reference_guide.event_visitors.distance_recorder `distance_recorder`]]
-[template boost_time_stamper[] [link boost.graph_reference_guide.event_visitors.time_stamper `time_stamper`]]
-[template boost_property_writer[] [link boost.graph_reference_guide.event_visitors.property_writer `property_writer`]]
-
-[template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search `breadth_first_search()`]]
-[template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search `depth_first_search()`]]
-[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths `dijkstra_shortest_paths()`]]
-[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths `bellman_ford_shortest_paths()`]]
-[template boost_connected_components[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components `connected_components()`]]
+[include sgi_concepts.qbk]
+[include boost_concepts.qbk]
+[include boost_reference.qbk]
[/ Contents ]
[include introduction.qbk]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -15,8 +15,8 @@
The `connectivity()` algorithm is essentially a wrapper around the
[boost_connected_components] algorithm, but provides additional (and optional)
-functionality for working with connected components. The parameters are, with
-the exeption of `_components`, have the same purpose and requirements as
+functionality for working with connected components. The parameters have, with
+the exeption of `_components`, the same purpose and requirements as
documented in [boost_connected_components].
If specified, the `_components` argument is populated with the vertices that
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distance_recorder.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distance_recorder.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,99 @@
+[/
+ / 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 Distance Recorder]
+
+ template <class DistanceMap, class EventTag>
+ class distance_recorder;
+
+This is an [BoostEventVisitor] that records the distance of a vertex (using a property
+map) from some source vertex during a graph search. When applied to edge /e = (u,v)/,
+the distance of /v/ is recorded to be one more than the distance of /u/. The distance
+recorder is typically used with the `on_tree_edge` or `on_relax_edge` events, and cannot
+be used with vertex events.
+
+The [boost_distance_recorder] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also,
+this event visitor can be combined with other event visitors using `std::pair` to form
+an [BoostEventVisitorList].
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`DistanceMap`]
+ [
+ A [BoostWritablePropertyMap] where the key type is of type `vertex_descriptor`
+ and the value type is numeric (usually an integer or the same type as the
+ edge weight).
+ ]
+ ]
+ [
+ [`EventTag`]
+ [
+ A tag used to specify when the recorder should be applied during the graph
+ algorithm. `EventTag` must be an edge event.
+ ]
+ ]
+]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`distance_recorder::event_filter`]
+ [
+ This type will be the same as the template parameter `EventTag`.
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [`distance_recorder(DistanceMap pa)`]
+ [Construct a distance recorder object with a predecessor property map `pa`.]
+ ]
+ [
+ [
+``
+template <class Edge, class Graph>
+void operator()(Edge e, const Graph& g)
+``
+ ]
+ [
+ Given edge `e` as /(u,v)/, this records the distance of `v` as one
+ plus the distance of `u`.
+ ]
+ ]
+]
+
+[h4 Non-Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class DistanceMap, class EventTag>
+distance_recorder<DistanceMap, EventTag>
+record_distances(DistanceMap pa, EventTag)
+``
+ ]
+ [
+ A convenience function for creating [boost_distance_recorder] instances.
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/predecessor_recorder.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/predecessor_recorder.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,103 @@
+[/
+ / 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 Predecessor Recorder]
+
+ template <class PredecessorMap, class EventTag>
+ class predecessor_recorder;
+
+This is an [BoostEventVisitor] that records the predecessor (or parent) of a vertex in
+a predecessor property map. This is particularly useful in graph search algorithms where
+recording the predecessors is an efficient way to encode the search tree that was traversed
+during the search. The predecessor recorder is typically used with the `on_tree_edge` or
+`on_relax_edge events`, and cannot be used with vertex events.
+
+[boost_predecessor_recorder] can be used with graph algorithms by wrapping it with the
+algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also, this
+event visitor can be combined with other event visitors using `std::pair` to form an [BoostEventVisitorList].
+
+Algorithms such as Dijkstra's and breadth-first search will not assign a predecessor
+to the source vertex (which is the root of the search tree). Often times it is useful to
+initialize the source vertex's predecessor to itself, thereby identifying the root vertex
+as the only vertex which is its own parent. When using an algorithm like depth-first search
+that creates a forest (multiple search trees), it is useful to intialize the predecessor
+of every vertex to itself, so that all the root nodes can be distinguished.
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`PredecessorMap`]
+ [
+ A [BoostWritablePropertyMap] where the key type and value type are of type
+ `vertex_descriptor`.
+ ]
+ ]
+ [
+ [`EventTag`]
+ [
+ A tag used to specify when the recorder should be applied during the graph
+ algorithm. `EventTag` must be an edge event.
+ ]
+ ]
+]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`predecessor_recorder::event_filter`]
+ [
+ This type will be the same as the template parameter `EventTag`.
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [`predecessor_recorder(PredecessorMap pa)`]
+ [Construct a predecessor recorder object with a predecessor property map `pa`.]
+ ]
+ [
+ [
+``
+template <class Edge, class Graph>
+void operator()(Edge e, const Graph& g)
+``
+ ]
+ [
+ Given edge `e` as /(u,v)/, this records `u` as the predecessor (parent) of `v`.
+ ]
+ ]
+]
+
+[h4 Non-Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class PredecessorMap, class EventTag>
+predecessor_recorder<PredecessorMap, EventTag>
+record_predecessors(PredecessorMap pa, EventTag)
+``
+ ]
+ [
+ A convenience function for creating [boost_predecessor_recorder] instances.
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/property_writer.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/property_writer.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,103 @@
+[/
+ / 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 Property Writer]
+
+ template <class PropertyMap, class OutputIterator, class EventTag>
+ class property_writer;
+
+This is an [BoostEventVisitor] that can be used to output the property of a vertex
+or edge at some event-point within an algorithm.
+
+The [boost_property_writer] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor].
+Also, this event visitor can be combined with other event visitors using `std::pair` to
+form an [BoostEventVisitorList].
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`PropertyMap`]
+ [
+ A [BoostReadablePropertyMap] where the `key_type` is of type `vertex_descriptor`
+ of `edge_descriptor` (depending on the event tag) and the `value_type` type is
+ of the property is convertible to the `value_type` of the `OutputIterator`.
+ ]
+ ]
+ [
+ [`OutputIterator`]
+ [
+ The iterator type used to write the property values must be a model of
+ [SgiOutputIterator].
+ ]
+ ]
+ [
+ [`EventTag`]
+ [
+ A tag used to specify when the property writer should be applied during the graph
+ algorithm.
+ ]
+ ]
+]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`property_writer::event_filter`]
+ [
+ This type will be the same as the template parameter `EventTag`.
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [`property_writer(PropertyMap pa, OutputIterator out)`]
+ [Construct a property writer object with a property map `pa` and an output iterator `out`.]
+ ]
+ [
+ [
+``
+template <class X, class Graph>
+void operator()(X x, const Graph& g)
+``
+ ]
+ [
+ This writes the property value for `x` to the output iterator. Specifically,
+ `*out++ = get(pa, x)`.
+ ]
+ ]
+]
+
+[h4 Non-Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class PropertyMap, class OutputIterator, class EventTag>
+time_stamper<PropertyMap, OutputIterator, EventTag>
+stamp_times(Property pa, OutputIterator out, EventTag)
+``
+ ]
+ [
+ A convenience function for creating [boost_property_writer] instances.
+ ]
+ ]
+]
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -16,6 +16,13 @@
[section Traits Classes]
[endsect]
+[section Event Visitors]
+[include predecessor_recorder.qbk]
+[include distance_recorder.qbk]
+[include time_stamper.qbk]
+[include property_writer.qbk]
+[endsect]
+
[section Algorithms]
[section Core Algorithms]
[include breadth_first_search.qbk]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/time_stamper.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/time_stamper.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,104 @@
+[/
+ / 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 Time Stamper]
+
+ template <class TimeMap, class TimeT, class EventTag>
+ class time_stamper;
+
+This is an [BoostEventVisitor] that can be used to "stamp" a time at some event-point
+within an algorithm. An example of this is recording the discover or finish time of
+a vertex during a graph search.
+
+The [boost_time_stamper] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also,
+this event visitor can be combined with other event visitors using `std::pair` to
+form an [BoostEventVisitorList].
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`TimeMap`]
+ [
+ A [BoostWritablePropertyMap] where the key type is of type `vertex_descriptor`
+ of `edge_descriptor` (depending on the event tag) and `TimeT` must be convertible
+ to the value type.
+ ]
+ ]
+ [
+ [`TimeT`]
+ [
+ The type of the time counter, which should be convertible to the `value_type` of
+ TimeMap.
+ ]
+ ]
+ [
+ [`EventTag`]
+ [
+ A tag used to specify when the time stamper should be applied during the graph
+ algorithm.
+ ]
+ ]
+]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`time_stamper::event_filter`]
+ [
+ This type will be the same as the template parameter `EventTag`.
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [`time_stamper(Timemap pa, TimeT& t)`]
+ [Construct a time stamper object with a timestamp property map `pa` and time counter `t`.]
+ ]
+ [
+ [
+``
+template <class X, class Graph>
+void operator()(X x, const Graph& g)
+``
+ ]
+ [
+ This records the current timestamp for the edge or vertex in the property map
+ and increments the time count.
+ ]
+ ]
+]
+
+[h4 Non-Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class TimeMap, class TimeT, class EventTag>
+time_stamper<TimeMap, EventTag>
+stamp_times(TimeMap pa, TimeT& t, EventTag)
+``
+ ]
+ [
+ A convenience function for creating [boost_time_stamper] instances.
+ ]
+ ]
+]
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -6,6 +6,10 @@
/]
[section Undirected Graph]
+
+ template <class VertexProperties, class EdgeProperties, class GraphProperties>
+ class undirected_graph;
+
This section provides detailed information about the `undirected_graph` class,
its associated types, member functions and non-member interface. An undirected graph
is one in which edges have no direction - this is to say that edges can be "traveled"
@@ -113,6 +117,10 @@
for both directed and undirected graphs, it is better to use the `out_degree(g)`
function to access out-edges since it is guaranteed by every other graph class.
+[h5 Model Of]
+[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
+[BoostMutableGraph], and [BoostPropertyGraph].
+
[h4 Template Parameters]
There are only three parameters to the `undirected_graph` class.
[table
@@ -134,15 +142,11 @@
]
]
-[h5 Model Of]
-[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
-[BoostMutableGraph], and [BoostPropertyGraph].
-
Additionally, the `undirected_graph` class provides a non-constant time implementation
of the [BoostAdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
the concept.
-[h5 Where Defined]
+[h4 Where Defined]
`boost/graph/undirected_graph.hpp`
[h4 Associated Types]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/sgi_concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/sgi_concepts.qbk 2007-07-11 10:41:48 EDT (Wed, 11 Jul 2007)
@@ -0,0 +1,41 @@
+[/
+ / 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)
+ /]
+
+[/
+ / This file defines templates that expand to links to the SGI-defined
+ / STL concepts.
+ /]
+
+[/ 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 SgPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
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