
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070719 09:59:24
Author: asutton
Date: 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
New Revision: 7482
URL: http://svn.boost.org/trac/boost/changeset/7482
Log:
Moved all docs up one level and got rid of some cruft
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/doc/bibliography.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/a_star_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dfs_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/incidence_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/guide/
sandbox/SOC/2007/graphs/libs/graph/doc/guide/adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/guide/directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/guide/guide.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/guide/undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/history.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/introduction.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/
sandbox/SOC/2007/graphs/libs/graph/doc/reference/adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/connected_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/edge_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/strong_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/theory.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/tour.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/tutorial.qbk
Added: sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,79 @@
+
+# Copyright John Maddock 2005. Use, modification, and distribution are
+# subject to the Boost Software License, Version 1.0. (See accompanying
+# file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+using quickbook ;
+
+xml graph : graph.qbk ;
+
+boostbook standalone
+ :
+ graph
+ :
+ # HTML options first:
+ # Use graphics not text for navigation:
+ <xsl:param>navig.graphics=1
+ # How far down we chunk nested sections, basically all of them:
+ <xsl:param>chunk.section.depth=10
+ # Don't put the first section on the same page as the TOC:
+ <xsl:param>chunk.first.sections=1
+ # How far down sections get TOC's
+ <xsl:param>toc.section.depth=10
+ # Max depth in each TOC:
+ <xsl:param>toc.max.depth=4
+ # How far down we go with TOC's
+ <xsl:param>generate.section.toc.level=10
+ # Logo location:
+ <xsl:param>boost.logo=../boost.png
+ <xsl:param>annotation.support=1
+
+ # The page style
+ <xsl:param>page.style="'website'"
+ # Show chapters select box
+ <xsl:param>grouped.links.chapters.show="'true'"
+ # GroupedLinks xml definition chapters location
+ <xsl:param>grouped.links.chapters.xml="'boost_libs_grouped_links.xml'"
+ # Select the base url for the chapters GroupedLinks
+ <xsl:param>grouped.links.chapters.url="'http://www.boost.org/libs/'"
+ # Show sections select box
+ <xsl:param>grouped.links.sections.show="'true'"
+ # GroupedLinks xml definition sections location
+ <xsl:param>grouped.links.sections.xml="'sections_grouped_links.xml'"
+ # Select the base url for the chapters GroupedLinks
+ <xsl:param>grouped.links.sections.url="'./'"
+ # Show the Google Search Box
+ <xsl:param>search.box.show="'true'"
+ # Location of the cse defintion
+ <xsl:param>search.box.cse.definition.src="'http://www.drivehq.com/web/matias.capeletto/bimap/doc/html/context8.xml'"
+
+ # PDF Options:
+ # TOC Generation: this is needed for FOP0.9 and later:
+ # <xsl:param>fop1.extensions=1
+ <xsl:param>xep.extensions=1
+ # TOC generation: this is needed for FOP 0.2, but must not be set to zero for FOP0.9!
+ <xsl:param>fop.extensions=0
+ # No indent on body text:
+ <xsl:param>body.start.indent=0pt
+ # Margin size:
+ <xsl:param>page.margin.inner=0.5in
+ # Margin size:
+ <xsl:param>page.margin.outer=0.5in
+ # Yes, we want graphics for admonishments:
+ <xsl:param>admon.graphics=1
+ # Set this one for PDF generation *only*:
+ # default pnd graphics are awful in PDF form,
+ # better use SVG's instead:
+ #<xsl:param>admon.graphics.extension=".svg"
+ ;
+
+
+
+
+
+
+
+
+
+
+
Added: sandbox/SOC/2007/graphs/libs/graph/doc/bibliography.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/bibliography.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,19 @@
+[/
+ / 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)
+ /]
+
+[bibliography]
+
+[bibentry
+ [authors [Sutter, Herb], [Alexandrescu, Andrei]]
+ [title C++ Coding Standards: 101 Rules, Guidelines, and Best Practices]
+ [book
+ [publisher Addison Wesley]
+ [copyright 1985 Pearson Education, Inc.]
+ [pages 220]
+]
+
+[endbib]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk 20070719 09:59:20 EDT (Thu, 19 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 contains Boostdefined 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]]
+
+[/ A bunch of miscellaneus concepts]
+[template BoostColorValue[] [link boost_graph.concepts.miscellaneous_concepts.color_value ColorValue]]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk 20070719 09:59:20 EDT (Thu, 19 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()]]]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/a_star_visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/a_star_visitor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,72 @@
+[/
+ / 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 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).
+
+[h4 Associated Types]
+[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.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_descriptor`]
+ [
+ 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.
+ ]
+ ]
+ [
+ [`graph_traits<G>::directed_category`]
+ [
+ This type shall be convertible to `directed_tag` or `undirected_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_parallel_category`]
+ [
+ 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`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ 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`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`graph_traits<G>::null_vertex()`]
+ [
+ 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()`.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,69 @@
+[/
+ / 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 Adjacency Graph]
+The AdjacencyGraph concept provides and interface for efficient access of the adjacent vertices
+to a vertex in a graph. This is quite similar to the IncidenceGraph concept (the target of an
+outedge is an adjacent vertex). Both concepts are provided because in some contexts there is only
+concern for the vertices, whereas in other contexts the edges are also important.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `adjacency_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::adjacency_iterator`]
+ [
+ An adjacency iterator for a vertex v provides access to the vertices adjacent to v.
+ As such, the value type of an adjacency iterator is the vertex descriptor type of its
+ graph. An adjacency iterator must meet the requirements of [BoostMultiPassInputIterator].
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`adjacent_vertices(v,g)`]
+ [
+ Returns an iteratorrange providing access to the vertices adjacent to vertex `v` in
+ the graph `g`.
+
+ *Returns* `std::pair<adjacency_iterator, adjacency_iterator>`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `adjacent_vertices(v,g)` function must return in constant time.
+
+[h4 Design Rationale]
+The AdjacencyGraph concept is somewhat frivolous since [BoostIncidenceGraph] really covers the same
+functionality (and more). The AdjacencyGraph concept exists because there are situations when
+`adjacent_vertices()` is more convenient to use than `out_edges()`. If you are constructing a graph
+class and do not want to put in the extra work of creating an adjacency iterator, have no fear. There
+is an adaptor class named `adjacency_iterator` that you can use to create an adjacency iterator out
+of an outedge iterator.
+
+[h4 Notes]
+The case of a /multigraph/ (where multiple edges can connect the same two vertices) brings up an issue
+as to whether the iterators returned by the `adjacent_vertices()` function access a range that includes
+each adjacent vertex once, or whether it should match the behavior of the `out_edges()` function, and
+access a range that may include an adjacent vertex more than once. For now the behavior is defined to
+match that of `out_edges()`, though this decision may need to be reviewed in light of more experience
+with graph algorithm implementations.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,50 @@
+[/
+ / 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 Adjacency Matrix]
+The AdjacencyMatrix concept refines `Graph` concept and adds the requirement for efficient access
+to any edge in the graph given the source and target vertices. No Boost.Graph algorithms currently
+use this concept. However there are algorithms not yet implemented such as FloydWarshall that
+would require this concept.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `adjacency_matrix_tag`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`edge(u,v,g)`]
+ [
+ Returns a pair consisting of a flag saying whether there exists an edge between `u` and
+ `v` in graph g, and consisting of the edge descriptor if the edge was found.
+
+ *Returns* `std::pair<edge_iterator, bool>`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `edge(u,v,g)` function must return in constant time.
+
+[h4 Notes]
+A number of graph classes (notably [boost_undirected_graph], [boost_directed_graph] and
+[boost_adjacency_list]) provide nonconstant time implementations of this interface. Although
+the function exists, none of these classes are documented as modeling this concept.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,70 @@
+[/
+ / 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 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 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis.examine_edge(v,g)`]
+ [
+ This is invoked on every outedge of each vertex after it is discovered.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.edge_relaxed(e,g)`]
+ [
+ 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.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.edge_minimized(e,g)`]
+ [
+ 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`
+ ]
+ ]
+ [
+ [`vis.edge_relaxed(e,g)`]
+ [
+ If the edge is not minimized then this function is invoked. This happens when there
+ is a negative weight cycle in the graph.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_bellman_ford_visitor]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,105 @@
+[/
+ / 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 BreadthFirst Search Visitor]
+This concept defines the visitor interface for [booost_breadth_first_search] algorithm. Users
+can define a class with the BFS Visitor interface and pass and object of the class to
+[boost_breadth_first_search], thereby augmenting the actions taken during the graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis.initialize_vertex(v,g)`]
+ [
+ This is invoked on every vertex of the graph before the start of the graph search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.discover_vertex(v,g)`]
+ [
+ This is invoked when a vertex is encountered for the first time.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`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 outedges of vertex `v`.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_edge(e,g)`]
+ [
+ This is invoked on every outedge of each vertex after it is discovered.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.tree_edge(e,g)`]
+ [
+ This is invoked on each edge as it becomes a member of the eges that the form the
+ search tree.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.non_tree_edge(v,g)`]
+ [
+ This is invoked on back or cross edges for directed graphs and cross edges
+ for undirected graphs.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.gray_target(e,g)`]
+ [
+ This is invoked on the subset of nontreeedges who's target vertex is colored gray
+ at the time of examination. The color gray indicates that the vertex is currently
+ in the queue.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.black_target(v,g)`]
+ [
+ This is invoked on the subset of nontree edges who's target vertex is colored black
+ at the time of examination. The color black indicates that the vertex has been removed
+ from the queue.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.finish_vertex(v,g)`]
+ [
+ This is invoked on a vertex after all of its out edges have been added to the search
+ tree and all of the adjacenct vertices have been discovered, but before the outedges
+ of the adjacent vertices have been examined.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_bfs_visitor]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,76 @@
+[/
+ / 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 Bidirectional Graph]
+The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient
+access to the inedges of each vertex. This concept is separated from IncidenceGraph because for
+directed graphs efficient access to inedges typically requires more storage space, and many
+algorithms do not require access to inedges. For undirected graphs this is not an issue, since
+the in_edges() and out_edges() functions are the same, they both return the edges incident to
+the vertex.
+
+[heading Refinement Of]
+[BoostIncidenceGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `bidirectional_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::in_edge_iterator`]
+ [
+ An inedge iterator for a vertex v provides access to the inedges of a vertex. As
+ such, the value type of an inedge iterator is the edge descriptor type of its graph.
+ An inedge iterator must meet the requirements of MultiPassInputIterator.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`in_edges(v,g)`]
+ [
+ Returns an iterator range providing access to the inedges (for directed graphs)
+ or the incident edges (for undirected graphs). The target vertex of an edge obtained
+ via an inedge iterator is guaranteed to be the vertex `v` in the call to
+ `in_edges(v,g)`, and the source vertex must be adjacenct to `v`.
+
+ *Returns* `std::pair<in_edge_iterator, in_edge_iterator>`
+ ]
+ ]
+ [
+ [`in_degree(v,g)`]
+ [
+ Returns the number of inedges (for directed graphs) or the number of incident
+ edges (for undirected graphs) of the vertex `v`.
+
+ *Returns* `degree_size_type`.
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list] with the `Directed` template parameter as `bidirectionalS` or
+`undirectedS`.
+
+[h4 Complexity Guarantees]
+The `in_edges(g)` function is required to return in constant time.
+
+The `in_degree()` and `degree()` functions must be linear in the number of inedges (for
+directed graph) or incident edges (for undirected graphs).
+
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,36 @@
+[/
+ / 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 Concepts]
+This section provides a detailed listing of the type concepts in the Boost.Graph
+library.
+
+[heading Notation]
+For the following sections, we use the following notional convents:
+
+[table
+ [[Object] [Type]]
+ [[G] [A type that is a model of a [BoostGraph] (or refinement thereof)]]
+ [[g] [An object of type G]]
+ [[u,v] [Objects of type `graph_traits<G>::vertex_descriptor`]]
+ [[e] [An object of type `graph_traits<G>::edge_descriptor`]]
+ [[vi] [An object of type `graph_traits<G>::vertex_iterator`]]
+ [[ei] [An object of type `graph_traits<G>::edge_iterator`]]
+ [[vp] [An object of type `G::vertex_property_type`]]
+ [[ep] [An object of type `G::edge_property_type`]]
+ [[Property] [A type used to specify a vertex or edge property. Also called a /tag/.]]
+ [[p] [An object of type Property]]
+ [[Predicate] [A function that, given an argument, returns true or false]]
+ [[pred] [An object of type [SgiPredicate]]]
+ [[V] [A type that is a model of a [BoostVisitor] (or refinement thereof)]]
+ [[vis] [An object of type V]]
+]
+
+[include graphs.qbk]
+[include visitors.qbk]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,28 @@
+[/
+ / 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 Descriptor]
+The Descriptor concept describes requirements common to vertex and edge descriptors of
+all graph types.
+
+[heading Refinement Of]
+[SgiDefaultConstructible], [SgiCopyConstructible], [SgiAssignable], [SgiEqualityComparable],
+and [SgiLessThanComparable].
+
+[heading Associated Types]
+There are no associated types of a Descriptor.
+
+[heading Valid Expressions]
+Beyond the requirements of the refined concepts, the descriptor does not require any
+additional valid expressions.
+
+[heading Notes]
+Note that because both model the [SgiLessThanComparable] concept, they can be used as
+keys in any associative container modeling the [SgiAssociativeContainer] concepte
+(e.g., `std::map`, `std::set`, etc).
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dfs_visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dfs_visitor.qbk 20070719 09:59:20 EDT (Thu, 19 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 DepthFirst Search Visitor]
+This concept defines the visitor interface for [booost_depth_first_search] algorithm. Users
+can define a class with the DFS Visitor interface and pass and object of the class to
+[boost_depth_first_search], thereby augmenting the actions taken during the graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis.initialize_vertex(v,g)`]
+ [
+ This is invoked on every vertex of the graph before the start of the graph search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.start_vertex(v,g)`]
+ [
+ This is invoked on the source veretx once before the start of the search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.discover_vertex(v,g)`]
+ [
+ This is invoked when a vertex is encountered for the first time.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_edge(e,g)`]
+ [
+ This is invoked on every outedge of each vertex after it is discovered.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.tree_edge(e,g)`]
+ [
+ This is invoked on each edge as it becomes a member of the eges that the form the
+ search tree.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.back_edge(v,g)`]
+ [
+ This is invoked on the back edges of the graph. For an unidrected graph there
+ is some ambiguity between tree edges and back edges since the edge /(u,v)/
+ and /(v,u)/ are the same edge, but both `tree_edge(v,g)` and `back_edge(v,g)`
+ will be invoked. One way to resolve this ambiguity is to record the tree
+ edges and then disregard the back edges that are already marked as tree edges.
+ An easy way to record tree edges is to record predecessors at the `tree_edge`
+ event point.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.forward_or_cross_edge(e,g)`]
+ [
+ This is invoked on forward or cross edges in the graph. In an undirected graph,
+ this method is never called.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.finish_vertex(v,g)`]
+ [
+ This is invoked on a vertex after all `finish_vertex(x,g)` has been invoked for
+ all vertices in the search tree rooted at `v` (i.e., after all its children
+ have finished). If `v` is a leaf in the search tree, `finish_vertex(v,g)` is
+ called after all its outedges have been examined.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_dfs_visitor]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,87 @@
+[/
+ / 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 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 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis.initialize_vertex(v,g)`]
+ [
+ This is invoked on every vertex of the graph before the start of the graph search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.discover_vertex(v,g)`]
+ [
+ This is invoked when a vertex is encountered for the first time. This happens immediately
+ before `examine_edge()` is invoked on each of the outedges of `v`.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`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 outedges of vertex `v`.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_edge(v,g)`]
+ [
+ This is invoked on every outedge of each vertex after it is discovered.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.edge_relaxed(e,g)`]
+ [
+ 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.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.finish_vertex(v,g)`]
+ [
+ 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* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_dijkstra_visitor]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,98 @@
+[/
+ / 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 Edge List Graph]
+The EdgeListGraph concept refines the [BoostGraph] concept, and adds the requirement
+for efficient access to all the edges in a graph.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `edge_list_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_iterator`]
+ [
+ An edge iterator (obtained via edges(g)) provides access to all of the edges
+ in a graph. An edge iterator type must meet the requirements of
+ [BoostMultiPassInputIterator]. The value type of the edge iterator must be the
+ same as the edge descriptor of the graph.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edges_size_type`]
+ [
+ The unsigned integer type used to represent the number of edges in the graph.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`edges(g)`]
+ [
+ Returns an iterator range providing access to all the edges in the graph `g`.
+
+ *Returns* `std::pair<edge_iterator, edge_iterator>`
+ ]
+ ]
+ [
+ [`num_edges(g)`]
+ [
+ Returns the number of edges in the graph `g`.
+
+ *Returns* `edges_size_type`
+ ]
+ ]
+ [
+ [`source(e,g)`]
+ [
+ If `e` is an edge /(u,v)/ in `g`, this function returns the source vertex `u`.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+ [
+ [`target(e,g)`]
+ [
+ If `e` is an edge /(u,v)/ in `g`, this function returns the target vertex `v`.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list]
+* [boost_edge_list]
+
+[h4 Complexity Guarantees]
+The `edges(g)`, `source(e,g)`, and `target(e,g)` functions must return in constant time.
+
+[h4 Design Rationale]
+One issue in the design of this concept is whether to include the refinement from the
+[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+of a graph is orthogonal to traversing outedges, so it would make sense to have a edgeListGraph
+concept that only includes edge traversal. However, such a concept would no longer really be a
+graph, but would just be a set, and the STL already has concepts for dealing with such things.
+However, there are many BGL algorithms that need to traverse the vertices and outedges of a graph,
+so for convenience a concept is needed that groups these requirements together, hence the edgeListGraph
+concept.
+
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,175 @@
+[/
+ / 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 Event Visitor]
+This concept defines the interface for singleevent visitors. An EventVisitor has an
+/apply/ member function (`operator()`) which is invoked within the graph algorithm
+at the eventpoint specified by the `event_filter` typedef within the type modeling
+the EventVisitor concept. EventVisitors can be combined into an [BoostEventVistorList].
+
+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 [BoostBFSVisitor] of [boost_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.
+
+[h4 Event Tags]
+[table
+ [[Type] [Description]]
+ [
+ [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]
+ [
+ In algorithms that without explicit starting points, this event tag
+ corresponds to the selection of a starting vertex. The parameter
+ type associated with this event is `vertex_descriptor`.
+ ]
+ ]
+ [
+ [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
+ `vertex_descriptor`.
+ ]
+ ]
+ [
+ [on_examine_edge]
+ [
+ An event tag that corresponds to the examination of edges for recently
+ discovered vertices. The parameter type associated with this event
+ is `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_tree_edge]
+ [
+ For algorithms whose iterations of a vertex set implicitly define a
+ tree (such as [boost_breadth_first_search] or [boost_depth_first_search]),
+ this event tag corresponds to the identification of an edge that acts
+ as an edge in the search tree. The parameter type associated with this
+ event is `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_cycle_edge]
+ [
+ For algorithms capable of detecting cycles in graphs such as
+ [boost_depth_first_search], this event tag is associated with discovery
+ of an edge that creates a cycle within the graph. The parameter type
+ associated with this event is `edge_descriptor`.
+ ]
+ ]
+ [
+ [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., [boost_depth_first_search]).
+ This event tag corresponds to the identification of such an edge by
+ the algorithm. The parameter type associated with this event is
+ `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_back_edge]
+ [
+ Back edges refer to types of edges that can be found by different types
+ of searches on a graph (e.g., [boost_breadth_first_search] and
+ [boost_depth_first_search]). This event tag corresponds to the identification
+ of such an edge by the algorithm. The parameter type associated with this
+ event is `edge_descriptor`.
+ ]
+ ]
+ [
+ [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
+ vertex. The parametet type associated with this event is `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_edge_relaxed]
+ [
+ For algorithms implementing edge relaxation (e.g.,
+ [boost_dijkstra_shortest_paths]), this event corresponds to the case
+ where an edge is relaxed. The parameter type associated with this event
+ is `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_edge_not_relaxed]
+ [
+ For algorithms implementing edge relaxation (e.g.,
+ [boost_dijkstra_shortest_paths]), this event corresponds to the case
+ where an edge is not relaxed. The parameter type associated with this
+ event is `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_edge_minimized]
+ [
+ For algorithms implementing edge minimization (e.g.,
+ [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+ where an edge is minimized. The parameter type associated with this event
+ is `edge_descriptor`.
+ ]
+ ]
+ [
+ [on_edge_not_minimized]
+ [
+ For algorithms implementing edge minimization (e.g.,
+ [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+ where an edge is not minimized. The parameter type associated with this
+ event is `edge_descriptor`.
+ ]
+ ]
+]
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`V::event_filter`]
+ [
+ A tag to specify on which even the visitor should be invoked.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis(x,g)`]
+ [
+ Invokes the `operator()` member function of an object `vis` of type
+ `V`. The parameter `x` is either a vertex or edge of the graph `g`. The
+ specific type of parameter depends on `V::event_filter`.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_predecessor_recorder]
+* [boost_distance_recorder]
+* [boost_time_stamper]
+* [boost_property_writer]
+* [boost_null_visitor]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,70 @@
+[/
+ / 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 Event Visitor List]
+An EventVisitorList is either an [BoostEventVisitor], or a list of [BoostEventVisitor]
+combined using `std::pair`. Each graph algorithm defines visitor adaptors that convert an
+EventVisitorList into the particular kind of visitor needed by the algorithm. In the
+following example we will show how to combine event visitors into a list using `std::pair`
+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 depthfirst 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
+event points specified in [BoostDFSVisitor].
+
+ struct open_paren : public base_visitor<open_paren>
+ {
+ typedef on_discover_vertex event_filter;
+
+ template <class Vertex, class Graph>
+ void operator ()(Vertex v, Graph& G)
+ {
+ cout << "(" << v;
+ }
+ };
+
+
+ struct close_paren : public base_visitor<clsoe_paren>
+ {
+ typedef on_discover_vertex event_filter;
+
+ template <class Vertex, class Graph>
+ void operator ()(Vertex v, Graph& G)
+ {
+ cout << v << ")";
+ }
+ };
+
+Next, we create two event visitor objects and combine them so the resultant type models
+the EventVisitorList concept.
+
+ make_pair(open_paren(), close_paren());
+
+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 [boost_depth_first_search] as follows.
+
+ depth_first_search(
+ G,
+ make_dfs_visitor(make_pair(open_paren(), close_paren())));
+
+For creating a list of more than two event visitors, nest calls to `make_pair` in the following way
+to recursively produce an EventVisitorList.
+
+ make_pair(visitor1,
+ make_pair(visitor2, ...
+ make_pair(visitorN  1, visitorN)...))
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,72 @@
+[/
+ / 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 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).
+
+[h4 Associated Types]
+[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.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_descriptor`]
+ [
+ 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.
+ ]
+ ]
+ [
+ [`graph_traits<G>::directed_category`]
+ [
+ This type shall be convertible to `directed_tag` or `undirected_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_parallel_category`]
+ [
+ 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`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ 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`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`graph_traits<G>::null_vertex()`]
+ [
+ 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()`.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,234 @@
+[/
+ / 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 Graph Concepts]
+The heart of the Boost Graph Library (BGL) is the interface, or concepts (in the
+parlance of generic programming), that define how a graph can be examined and
+manipulated in a datastructure neutral fashion. In fact, the BGL interface need
+not even be implemented using a datastructure, as for some problems it is easier
+or more efficient to define a graph implicitly based on some functions.
+
+The Boost.Graph interface does not appear as a single graph concept. Instead it is
+factored into much smaller peices. The reason for this is that the purpose of a
+concept is to summarize the requirements for particular algorithms. Any one algorithm
+does not need every kind of graph operation, typically only a small subset. Furthermore,
+there are many graph datastructures that can not provide efficient implementations of
+all the operations, but provide highly efficient implementations of the operations
+necessary for a particular algorithm . By factoring the graph interface into many smaller
+concepts we provide the graph algorithm writer with a good selection from which to choose
+the concept that is the closest match for their algorithm.
+
+Figure 1 shows the refinements relations between the graph concepts. The reason for
+factoring the graph interface into so many concepts is to encourage algorithm interfaces
+to require and use only the minimum interface of a graph, thereby increasing the
+usability of the algorithm.
+
+[$images/concepts/graph_concepts.png]
+
+Table 1 gives a summary of the valid expressions and associated types for the graph
+concepts and provides links to the detailed descriptions of each of the concepts.
+The notation used in the table is as follows.
+
+[table
+ [[Expression] [Return Type or Description]]
+ [[[*[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]]]]
+ [[`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`]]
+ [[[*[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]]]]
+ [[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
+ [[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
+ [[[*[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]]]]
+ [[`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]]]]
+ [[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
+ [[[*[BoostMutableGraph]]]]
+ [[`add_vertex(g)`] [`vertex_descriptor`]]
+ [[`clear_vertex(v,g)`] [`void`]]
+ [[`clear_out_edges(v,g)`] [`void`]]
+ [[`clear_in_edges(v,g)`] [`void`]]
+ [[`add_edge(u,v,g)`] [`std::pair<edge_descriptor,bool>`]]
+ [[`remove_edge(u,v,g)`] [`void`]]
+ [[`remove_edge(e,g)`] [`void`]]
+ [[`remove_edge(ei,g)`] [`void`]]
+ [[`remove_edge_if(pred,g)`] [`void`]]
+ [[`remove_out_edge_if(v,pred,g)`] [`void`]]
+ [[`remove_in_edge_if(v,pred,g)`] [`void`]]
+ [[[*[BoostPropertyGraph]]]]
+ [[`property_map<G,Property>::type`] [Type for a mutable property map.]]
+ [[`property_map<G,Property>::const_type`] [Type for a nonmutable 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]]]]
+ [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
+ [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
+]
+
+[include descriptor.qbk]
+[include graph.qbk]
+[include incidence_graph.qbk]
+[include bidirectional_graph.qbk]
+[include adjacency_graph.qbk]
+[include vertex_list_graph.qbk]
+[include edge_list_graph.qbk]
+[include adjacency_matrix.qbk]
+[include mutable_graph.qbk]
+[include property_graph.qbk]
+[include mutable_property_graph.qbk]
+
+[h3 PseudoConcepts]
+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 pseudoconcepts with which we can also describe graph objects.
+
+[h4 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 outedges and inedges 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;
+ typedef ... UndirectedGraph;
+ UndirectedGraph graph(V);
+
+ std::cout << "the edges incident to v: ";
+ boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
+ boost::graph_traits<UndirectedGraph>::vertex_descriptor s = vertex(0, graph);
+ for(tie(e, e_end) = out_edges(s, graph); e != e_end; ++e) {
+ std::cout << "(" << source(*e, graph)
+ << "," << target(*e, graph)
+ << ")" << 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.
+
+ typedef ... DirectedGraph;
+ typedef ... UndirectedGraph;
+
+ DirectedGraph digraph(V);
+ UndirectedGraph graph(V)
+
+ {
+ boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
+ u = vertex(0, digraph);
+ v = vertex(1, digraph);
+ add_edge(digraph, u, v, Weight(1.2));
+ add_edge(digraph, v, u, Weight(2.4));
+ boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
+ bool found;
+ tie(e1, found) = edge(u, v, digraph);
+ tie(e2, found) = edge(v, u, digraph);
+ std::cout << "in a directed graph is ";
+ std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+ property_map<DirectedGraph, edge_weight_t>::type
+ weight = get(edge_weight, digraph);
+ cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+ cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+ }
+
+ {
+ boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
+ u = vertex(0, graph);
+ v = vertex(1, graph);
+ add_edge(graph, u, v, Weight(3.1));
+ boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
+ bool found;
+ tie(e1, found) = edge(u, v, graph);
+ tie(e2, found) = edge(v, u, graph);
+ std::cout << "in an undirected graph is ";
+ std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+ property_map<UndirectedGraph, edge_weight_t>::type
+ weight = get(edge_weight, graph);
+ cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+ cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+ }
+
+The output is:
+
+[pre
+in a directed graph is (u,v) == (v,u) ? 0
+weight\[(u,v)\] = 1.2
+weight\[(v,u)\] = 2.4
+in an undirected graph is (u,v) == (v,u) ? 1
+weight\[(u,v)\] = 3.1
+weight\[(v,u)\] = 3.1
+]
+
+[h4 Multigraphs]
+A /multigraph/ is a graph (either directed or undirected) that has parallel edges
+between vertices. The Boost.Graph types are mostly unrestrictive about the addition
+of parallel edges, meaning that it is fairly easy to actually create multigraphs
+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 [boost_adjacency_list] models an
+associative container, then the graph cannont be a multigraph.
+
+*Document this a little better*
+
+[h3 Indexed Graphs]
+Although not explicitly documented (yet), there's a concept of a VertexIndexed graph
+that has some valid expressions related specifically to operations on vertex index
+property of the graph. The [boost_undirected_graph] class has some addiitonal methods
+that can also be ported.
+
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/incidence_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/incidence_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,95 @@
+[/
+ / 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 Incidence Graph]
+The IncidenceGraph concept provides an interface for efficient access to the outedges
+(for directed graphs) or incident edges (for undirected graphs) of each vertex in
+the graph.
+
+[h4 Refinement Of]
+[BootGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `incidence_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::degree_size_type`]
+ [
+ The unsigned integral type used for representing the number of edges incident
+ to a vertex. The `degree_size_type` must meet the requirements of the
+ UnsignedIntegral concept.
+ ]
+ ]
+ [
+ [`graph_traits<G>::out_edge_iterator`]
+ [
+ An outedge iterator for a vertex /v/ provides access to the outedges of the
+ vertex. As such, the value type of an outedge iterator is the `edge_descriptor`
+ type of the graph. An outedge iterator must meet the requirements of
+ MultiPassInputIterator.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`source(e,g)`]
+ [
+ If `e` represents the edge /(u,v)/, this function returns the vertex descriptor
+ for /u/.
+
+ *Returns* `vertex_descriptor`.
+ ]
+ ]
+ [
+ [`target(e,g)`]
+ [
+ If `e` represents the edge /(u,v)/, this function returns the vertex descriptor
+ for /v/.
+
+ *Returns* `vertex_descriptor`.
+ ]
+ ]
+ [
+ [`out_edges(v,g)`]
+ [
+ Returns an iterator range providing access to the outedges (for directed graphs)
+ or the incident edges (for undirected graphs). The source vertex of an edge obtained
+ via an outedge iterator is guaranteed to be the vertex `v` in the call to
+ `out_edges(v,g)`, and the target vertex must be adjacenct to `v`.
+
+ *Returns* `std::pair<out_edge_iterator, out_edge_iterator>`
+ ]
+ ]
+ [
+ [`out_degree(v,g)`]
+ [
+ Returns the number of outedges (for directed graphs) or the number of incident
+ edges (for undirected graphs) of the vertex `v`.
+
+ *Returns* `degree_size_type`.
+ ]
+ ]
+]
+
+[h4 Notes]
+For undirected graphs, the edge /(u,v)/ is the same as edge /(v,u)/, so without some extra
+guarantee an implementation would be free use any ordering for the pair of vertices in an
+outedge. For example, if you call `out_edges(u, g)`, and `v` is one of the vertices adjacent
+to `u`, then the implementation would be free to return /(v,u)/ as an outedge which would be
+nonintuitive and cause trouble for algorithms. Therefore, the extra requirement is added that
+the outedge connecting `u` and `v` must be given as /(u,v)/ and not /(v,u)/.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,174 @@
+[/
+ / 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 Mutable Graph]
+A MutableGraph can be changed via the addition or removal of edges and vertices.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`add_edge(u,v,g)`]
+ [
+ Add a new vertex to the graph. The `vertex_descriptor` for the new vertex is returned.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+ [
+ [`clear_vertex(v,g)`]
+ [
+ Removes all edges incident (both inedges and outedges for directed graphs) to the
+ vertex `v`.
+
+ *Returns* `void`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+ *Postcondition* `u` does not appear as a source or target of any edge in `g`.
+ ]
+ ]
+ [
+ [`clear_out_edges(v,g)`]
+ [
+ Removes all edges outedges of the vertex `v`. For undirected graphs this is functionally
+ equivalent to `clear_vertex(v,g)`.
+
+ *Returns* `void`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+ *Postcondition* `u` does not appear as a source of any edge in `g`.
+ ]
+ ]
+ [
+ [`clear_in_edges(v,g)`]
+ [
+ Removes all edges inedges of the vertex `v`. For undirected graphs this is functionally
+ equivalent to `clear_vertex(v,g)`.
+
+ *Returns* `void`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+ *Postcondition* `u` does not appear as a target of any edge in `g`.
+ ]
+ ]
+ [
+ [`remove_vertex(v,g)`]
+ [
+ Remove the vertex `v` from the vertex set of the graph. Note that undefined behavior may
+ result if there are edges remaining in the graph who's target is `u`. The `clear_vertex(v,g)`
+ function should be called first to ensure the preconditions.
+
+ *Returns* `vertex_descriptor`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g` and does not appear as the source
+ or target of any edge in `g`.
+
+ *Postcondition* `u` is not longer in the vertex set of `g`, nor is `u` a valid descriptor.
+ ]
+ ]
+ [
+ [`add_edge(u,v,g)`]
+ [
+ Inserts the edge /(u,v)/ into the graph, and returns an edge descriptor pointing to the new edge.
+ If the graph disallows parallel edges, and the edge /(u,v)/ is already in the graph, then the boolean
+ flag returned is false and the returned edge descriptor points to the already existing edge. Note
+ that for undirected graphs, /(u,v)/ is the same edge as /(v,u)/, so after a call to the function
+ `add_edge(u,v,g)`, this implies that edge /(u,v)/ will appear in the outedges of `u` and /(u,v)/
+ (or equivalently /(v,u)/) will appear in the outedges of `v`. Put another way, `v` will be adjacent
+ to `u` and `u` will be adjacent to `v`.
+
+ *Returns* `vertex_descriptor`
+
+ *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+ *Postcondition* The returned `edge_descriptor` points to a valid edge in `g`.
+ ]
+ ]
+ [
+ [`remove_edge(u,v,g)`]
+ [
+ Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences
+ of /(u,v)/.
+
+ *Returns* `void`
+
+ *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+ *Postcondition* The edge /(u,v)/ is no longer in the edge set of `g`.
+ ]
+ ]
+ [
+ [`remove_edge(e,g)`]
+ [
+ Remove the edge `e` from the graph.
+
+ *Returns* `void`
+
+ *Precondition* `e` is an edge in the graph.
+
+ *Postcondition* The edge `e` is no longer in the edge set of `g`.
+ ]
+ ]
+ [
+ [`remove_edge(ei,g)`]
+ [
+ Remove the edge pointed to by the edge iterator `ei` from the graph. This expression is only required
+ when `g` also models [BoostIncidenceGraph].
+
+ *Returns* `void`
+
+ *Precondition* `*ei` is an edge in the graph.
+
+ *Postcondition* The edge `*ei` is no longer in the edge set of `g`.
+ ]
+ ]
+ [
+ [`remove_edge_if(pred,g)`]
+ [
+ Remove all edges from the graph `g` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`remove_out_edge_if(v,pred,g)`]
+ [
+ Remove all outedges of the vertex `v` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`remove_in_edge_if(v,pred,g)`]
+ [
+ Remove all inedges of the vertex `v` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+* Vertex insertion is guaranteed to be amortized constant time.
+* Clearing avertex is /O(E + V)/.
+* Vertex removal is /O(E + V)/.
+* Edge insertion must be either amortized constant time of it can be /O(log(E/V))/ if the insertion checks
+to prevent the addition of parallel edges (which is a "feature" of some graph types).
+* Edge removal is guaranteed to be /O(E)/.
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,64 @@
+[/
+ / 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 Mutable Property Graph]
+A MutablePropertyGraph is a [BoostMutableGraph] with properties attached internally to the
+vertices and edges. When adding vertices and edges the value of the properties can be given.
+
+[h4 Refinement Of]
+[BoostMutableGraph] and [BoostPropertyGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::vertex_property_type`]
+ [
+ The property type associated with vertices in the graph `G`. This type is not
+ guaranteed to be the same as the `VertexProperties` template parameter.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_property_type`]
+ [
+ The property type associated with edges in the graph `G`. This type is not
+ guaranteed to be the same as the `EdgeProperties` template parameter.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`add_vertex(vp,g)`]
+ [
+ Add a new vertex to the graph and copy vertex properties `vp` into the property
+ for the new vertex. The `vertex_descriptor` is returned.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+ [
+ [`add_edge(u,v,ep,g)`]
+ [
+ Inserts the edge /(u,v)/ into the graph, and copies object `ep` into the property
+ for that edge.
+
+ *Returns* `property_traits<property_map<G,Property>::const_type>::value_type`
+
+ *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+ *Postcondition* The returned `edge_descriptor` points to a valid edge in `g`.
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `get(p,g)` function must return in constant time.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,86 @@
+[/
+ / 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 Graph]
+A PropertyGraph is a graph that has some property associated with each of the vertices or edges
+in the graph. As a given graph may have several properties associated with each vertex or edge,
+a /tag/ is used to identity which property is being accessed. The graph provides a function which
+returns a property map object and also the value corresponding to a vertex or edge and its
+indicated property.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`property_map<G, Property>::type`]
+ [
+ The type of the property map for the property specified by `Property`. This type must
+ be a model of [BoostReadWritePropertyMap] with a key type the same as the graph's
+ `vertex_descriptor` or `edge_descriptor` types.
+ ]
+ ]
+ [
+ [`property_map<G, Property>::const_type`]
+ [
+ The type of the property map for the property specified by `Property`. This type must
+ be a model of [BoostReadablePropertyMap] with a key type the same as the graph\'s
+ `vertex_descriptor` or `edge_descriptor` types.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`get(p,g)`]
+ [
+ Returns the property map specified by the property identified by the tag `p`. The parameter
+ `p` is only used to convey type information and has no value.
+
+ *Returns* `property_map<G,Property>::type` if `g` is mutable and
+ `property_map<G,Property>::const_type` otherwise.
+ ]
+ ]
+ [
+ [`get(p,g,x)`]
+ [
+ Returns the property /value/ specified by the type of property tag `p` for the given
+ vertex or edge descriptor `x`. The object `p` is only used to convey type information
+ and has no value. This function is equivalent to `get(get(p,g),x)`.
+
+ *Returns* `property_traits<property_map<G,Property>::const_type>::value_type`
+ ]
+ ]
+ [
+ [`put(p,g,x,v)`]
+ [
+ Set the property /value/ specified by the type of property tag `p` for the given
+ vertex or edge descriptor `x` to the value `v`. The object `p` is only used to
+ convey type information and has no value.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`out_degree(v,g)`]
+ [
+ Returns the number of outedges (for directed graphs) or the number of incident
+ edges (for undirected graphs) of the vertex `v`.
+
+ *Returns* `degree_size_type`.
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `get(p,g)` function must return in constant time.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,75 @@
+[/
+ / 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 Vertex List Graph]
+The VertexListGraph concept refines the [BoostGraph] concept, and adds the requirement
+for efficient traversal of all the vertices in a graph.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `vertex_list_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::vertex_iterator`]
+ [
+ A vertex iterator (obtained via vertices(g)) provides access to all of the vertices in
+ a graph. A vertex iterator type must meet the requirements of [BoostMultiPassInputIterator].
+ The value type of the vertex iterator must be the vertex descriptor of the graph.
+ ]
+ ]
+ [
+ [`graph_traits<G>::vertices_size_type`]
+ [
+ The unsigned integer type used to represent the number of vertices in the graph.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vertices(g)`]
+ [
+ Returns an iterator range providing access to all the vertices in the graph `g`.
+
+ *Returns* `std::pair<vertex_iterator, vertex_iterator>`
+ ]
+ ]
+ [
+ [`num_vertices(g)`]
+ [
+ Returns the number of vertices in the graph `g`.
+
+ *Returns* `vertices_size_type`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `vertices(g)` function must return in constant time.
+
+[h4 Design Rationale]
+One issue in the design of this concept is whether to include the refinement from the
+[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+of a graph is orthogonal to traversing outedges, so it would make sense to have a VertexListGraph
+concept that only includes vertex traversal. However, such a concept would no longer really be a
+graph, but would just be a set, and the STL already has concepts for dealing with such things.
+However, there are many BGL algorithms that need to traverse the vertices and outedges of a graph,
+so for convenience a concept is needed that groups these requirements together, hence the VertexListGraph
+concept.
+
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitor.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,20 @@
+[/
+ / 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 Visitor]
+This 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 copyconstructible, which is how they are
+passed to different graph algorithms.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,27 @@
+[/
+ / 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 Visitor Concepts]
+The visitor concepts plays the same role in Boost.Graph as functors play in the STL.
+Functors provide a mechanism for extending an algorithm; for customizing what is done
+at each step of the algorithm. Visitors allow the user to insert their own operations
+at various steps within a graph algorithm. Unlike the STL algorithms, graph algorithms
+typically have multiple event points where one may want to insert a callback via a
+functor. Therefore visitors do not have a single operator() method like a functor, but
+instead have several methods that correspond to the various event points. Each
+algorithm has a different set of event points, which are described by the following
+visitor concepts:
+
+[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
Added: sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,55 @@
+[/
+ / 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)
+ /]
+
+[library Boost.Graph
+ [quickbook 1.3]
+ [authors [Siek, Jeremy], [Lee, LieQuan], [Lumsdaine, Andrew]]
+ [copyright 2000 2001 Jeremy Siek, LieQuan Lee, Andrew Lumsdaine]
+ [category graph]
+ [id graph]
+ [dirname graph]
+ [purpose
+ Graph data structures and algorithms.
+ ]
+ [license
+ 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])
+ ]
+]
+
+[/ Templates /]
+[template super[x] '''<superscript>'''[x]'''</superscript>''']
+[template sub[x] '''<subscript>'''[x]'''</subscripts>''']
+
+[template figure[path caption]
+'''
+<mediaobject>
+ <imageobject>
+ <imagedata fileref="'''[path]'''" align="center"/>
+ </imageobject>
+ <caption>
+ <para style="textalign: center">'''[caption]'''</para>
+ </caption>
+</mediaobject>
+'''
+]
+
+
+
+[include sgi_concepts.qbk]
+[include boost_concepts.qbk]
+[include boost_reference.qbk]
+
+[/ Contents ]
+[include introduction.qbk]
+[include history.qbk]
+[include guide/guide.qbk]
+[include concepts/concepts.qbk]
+[include reference/reference.qbk]
+
+[/ [include bibliography.qbk] /]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/adjacency_list.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/adjacency_list.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,480 @@
+[/
+ / 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 The Adjacency List]
+As mentioned in the Tour, the `adjacency_list` has seven template parameters. Three are
+used to select storage types for the vertex list, the edge list and the out edge list,
+and the remaining three define the interior properties of vertices, edges, and the
+graph itself.
+
+[h2 Choosing the Edgelist and VertexList]
+This section focuses on how to decide which version of the `adjacency_list` class to use in different
+situations. The adjacency_list is like a swissarmy knife in that it can be configured in many ways.
+The parameters that we will focus on in this section are `OutEdgeList` and `VertexList`, which control
+the underlying data structures that will be used to represent the graph. The choice of `OutEdgeList` and
+`VertexList` affects the time complexity of many of the graph operations and the space complexity of the
+graph object.
+
+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 (outedges and inedges) of the graph. There are several
+selector types that are used to specify the choice of container for `OutEdgeList` and `VertexList`.
+
+* `vecS` selects `std::vector`.
+* `listS` selects `std::list`.
+* `slistS` selects `std::slist`.
+* `setS` selects `std::set`.
+* `multisetS` selects `std::multiset`.
+* `hash_setS` selects `std::hash_set`.
+
+[h3 Choosing the VertexList Type]
+The VertexList parameter determines what kind of container will be used to represent the vertex set, or
+twodimensional structure of the graph. The container must model /Sequence/ or /RandomAccessContainer/. In
+general, listS is a good choice if you need to add and remove vertices quickly. The price for this is extra
+space overhead compared to choosing `vecS`.
+
+[h4 Space Complexity of the VertexList]
+The `std::list` has a higher pervertex space overhead than the `std::vector`, storing three extra pointers
+per vertex.
+
+[h4 Time Complexity of the VertexList]
+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
+ outedges 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 outedges (and
+possibly inedges) for each vertex in the graph. The containers used for edge lists must either satisfy
+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 multigraph).
+If you want this enforced then use the setS or hash_setS selectors. If you want to represent a
+multigraph, 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.
+
+[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`.
+
+[h4 Time Complexity of the OutEdgeList]
+In the following description of the time complexity for various operations, we use E/V inside of the "bigO"
+notation to express the length of an outedge list. Strictly speaking this is not accurate because E/V merely
+gives the average number of edges per vertex in a random graph. The worstcase number of outedges for a vertex
+is V (unless it is a multigraph). For sparse graphs E/V is typically much smaller than V and can be considered
+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 sequencebased OutEdgeList.
+ The `add_edge()` for the sequencebased 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 sequencebased OutEdgeList types this operation is implemented with `std::remove_if()`
+ which means the average time is E/V. For setbased 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 sequencebased 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]
+The `adjacency_list` class can be used to represent both directed and undirected graphs, depending on the
+argument passed to the Directed template parameter. Selecting `directedS` or `bidirectionalS` choose a directed
+graph, whereas `undirectedS` selects the representation for an undirected graph. See Section Undirected Graphs
+for a description of the difference between directed and undirected graphs in Boost.Graph. The `bidirectionalS`
+selector specifies that the graph will provide the `in_edges()` function as well as the `out_edges()` function.
+This imposes twice as much space overhead per edge, which is why `in_edges()` is optional.
+
+[h2 Internal Properties]
+Properties can be attached to the vertices or edges of an `adjacency_list` graph via the property interface.
+The template parameters VertexProperty and EdgeProperty of the `adjacency_list` class are meant to be filled
+by these interior properties.
+
+[note The Boost Graph Library supports two interchangeable methods for specifying interior properties:
+bundled properties and property lists. The former is easier to use and requires less effort, whereas the
+latter is compatible with older, broken compilers and is backwardcompatible with Boost versions prior to
+1.32.0. If you absolutely require these compatibility features, read on to learn about property lists.
+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.
+
+ template <class PropertyTag, class T, class NextProperty = no_property> struct property;
+
+The PropertyTag template parameter is a tag class that simply identifies or gives a unique name to the property.
+There are several predefined tags, and it is easy to add more.
+
+ struct vertex_index_t { };
+ struct vertex_index1_t { };
+ struct vertex_index2_t { };
+ struct edge_index_t { };
+ struct graph_name_t { };
+ struct vertex_name_t { };
+ struct edge_name_t { };
+ struct edge_weight_t { };
+ struct edge_weight2_t { };
+ struct edge_capacity_t { };
+ struct edge_residual_capacity_t { };
+ struct edge_reverse_t { };
+ struct vertex_distance_t { };
+ struct vertex_root_t { };
+ struct vertex_all_t { };
+ struct edge_all_t { };
+ struct graph_all_t { };
+ struct vertex_color_t { };
+ struct vertex_rank_t { };
+ struct vertex_predecessor_t { };
+ struct vertex_isomorphism_t { };
+ struct vertex_invariant_t { };
+ struct vertex_invariant1_t { };
+ struct vertex_invariant2_t { };
+ struct vertex_degree_t { };
+ struct vertex_out_degree_t { };
+ struct vertex_in_degree_t { };
+ struct vertex_discover_time_t { };
+ struct vertex_finish_time_t { };
+
+The T template parameter of property specifies the type of the property values. The type T must be Default
+Constructible, Assignable, and Copy Constructible. Like the containers of the C++ Standard Library, the
+property objects of type T are held byvalue 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.
+
+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.
+
+ // 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,
+ VertexProperty, EdgeProperty> Graph;
+
+ // instantiate the graph with N (a compiletime constant integer) vertices
+ Graph g(N);
+
+The property values are then read from and written to using property maps. See Section Interior Properties
+for a description of how to obtain property maps from a graph, and read Section Property Maps for how to use
+property maps.
+
+[h3 Builtin Vertex and Edge Properties]
+Even if a graph type is instantiated without any userspecified properties, Boost.Graph will define a few
+default properties for both vertices and edges. These are always available in algorithms through the
+property map interfaces.
+
+Vertices have the following properties:
+
+Edges have the following properties:
+
+[h3 Custom Edge Properties]
+Creating your own property types and properties is easy; just define a tag class for your new property.
+The property tag class will need to define num with a unique integer ID, and kind which should be either
+edge_property_tag, vertex_property_tag, or graph_property_tag.
+
+ struct flow_t {
+ typedef edge_property_tag kind;
+ };
+
+ 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.
+
+ enum edge_flow_t { edge_flow };
+ enum edge_capacity_t { edge_capacity };
+
+ namespace boost {
+ BOOST_INSTALL_PROPERTY(edge, flow);
+ 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.
+
+ 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.
+
+ 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.
+
+[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.
+
+ struct first_name_t {
+ typedef vertex_property_tag kind;
+ };
+
+Now we can use the new tag in the property class and use that in the assembly of a graph type. The following
+code shows creating the graph type, and then creating the graph object. We fill in the edges and also assign
+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,
+ 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(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);
+ }
+
+ property_map<MyGraphType, first_name_t>::type name = get(first_name_t(), G);
+
+ boost::put(name, 0, "Jeremy");
+ boost::put(name, 1, "Rich");
+ boost::put(name, 2, "Andrew");
+ boost::put(name, 3, "Jeff");
+ name[4] = "Kinis"; // you can also use the operator[] too
+
+ who_owes_who(edges(G).first, edges(G).second, G);
+
+The `who_owes_who()` function written for this example was implemented in a generic style. The input is
+templated so we do not know the actual graph type. To find out the type of the property map for our
+firstname 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.
+
+ template <class EdgeIter, class Graph>
+ void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
+ {
+ // Access the propety acessor type for this graph
+ typedef typename property_map<Graph, first_name_t>::const_type NameMap;
+ typedef typename boost::property_traits<NameMap>::value_type NameType;
+
+ NameMap name = get(first_name, G);
+ NameType src_name, targ_name;
+
+ while (first != last) {
+ src_name = boost::get(name, source(*first, G));
+ targ_name = boost::get(name, target(*first, G));
+ cout << src_name << " owes "
+ << targ_name << " some money" << "\n";
+ ++first;
+ }
+ }
+
+The output is:
+
+ Jeremy owes Rich some money
+ Jeremy owes Andrew some money
+ Jeremy owes Jeff some money
+ Jeremy owes Kinis some money
+ Andrew owes Jeremy some money
+ Andrew owes Kinis some money
+ Jeff owes Jeremy some money
+ Jeff owes Rich some money
+ Jeff owes Kinis some money
+ 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.
+
+[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
+vertices in the graph, and another type of container for the outedge list (and potentially inedge list)
+for each vertex. Boost.Graph provides selector classes that allow the user to choose between several of the
+containers from the STL. It is also possible to use your own container types. When customizing the VertexList
+you need to define a container generator as described below. When customizing the OutEdgeList you will need
+to define a container generator and the parallel edge traits. The file container_gen.cpp has an example of
+how to use a custom storage type.
+
+[h4 Container Generator]
+The `adjacency_list` class uses a traits class called `container_gen` to map the OutEdgeList and VertexList
+selectors to the actual container types used for the graph storage. The default version of the traits class
+is listed below, along with an example of how the class is specialized for the listS selector.
+
+ namespace boost {
+ template <class Selector, class ValueType>
+ struct container_gen { };
+
+ template <class ValueType>
+ struct container_gen<listS, ValueType> {
+ typedef std::list<ValueType> type;
+ };
+ }
+
+To use some other container of your choice, define a selector class and then specialize the `container_gen`
+for your selector.
+
+ struct custom_containerS { }; // your selector
+
+ namespace boost {
+ // the specialization for your selector
+ template <class ValueType>
+ struct container_gen<custom_containerS, ValueType> {
+ typedef custom_container<ValueType> type;
+ };
+ }
+
+There may also be situations when you want to use a container that has more template parameters than
+just ValueType. For instance, you may want to supply the allocator type. One way to do this is to
+hardcode 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`.
+
+ template <class Allocator>
+ struct list_with_allocatorS { };
+
+ namespace boost {
+ template <class Alloc, class ValueType>
+ struct container_gen<list_with_allocatorS<Alloc>, ValueType>
+ {
+ typedef typename Alloc::template rebind<ValueType>::other Allocator;
+ typedef std::list<ValueType, Allocator> type;
+ };
+ }
+
+ // 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]
+You must also tell the `adjacency_list` how elements can be efficiently added and removed from the
+custom container. This is accomplished by overloading the `push()` and `erase()` functions for the custom
+container type. The `push()` function should return an iterator pointing to the newly inserted element
+and a bool flag saying whether the edge was inserted.
+
+ template <class T>
+ std::pair<typename custom_container<T>::iterator, bool>
+ push(custom_container<T>& c, const T& v)
+ {
+ // this implementation may need to change for your container
+ c.push_back(v);
+ return std::make_pair(boost::prior(c.end()), true);
+ }
+
+ template <class T>
+ void erase(custom_container<T>& c, const T& x)
+ {
+ // this implementation may need to change for your container
+ c.erase(std::remove(c.begin(), c.end(), x), c.end());
+ }
+
+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).
+
+ template <>
+ struct parallel_edge_traits<custom_containerS> {
+ typedef allow_parallel_edge_tag type;
+ };
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/directed_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/directed_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,371 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section Directed Graphs]
+Like the previous section, here we take a look at how to solve different
+types graph problems using the Boost.Graph library. In this case however,
+the problems being addressed are better modeled with directed graphs. A
+directed graph (also a /digraph/) is one in which edges can only be traversed
+in a specific direction.
+
+In this section we are concerned with /dependency graphs/. A dependency graph
+describes a relationship between two entities in which one (/source/) requires
+a second (/target/). The source is said to be dependant upon the target.
+Dependency graphs arise in many, many realworld situations such as source
+code analysis, software installation, "techtrees" in computer games, etc.
+In this example, we will look at a common dependency graph: dependencies
+between software documents and build targets.
+
+[h3 File Dependencies]
+If you've ever typed `make` and wondered how the program decides the order
+tasks to build, then this tutorial is for you. The make software relies on
+dependency information explicitly encoded into Makefiles. Binaries (executable
+programs and libraries) depend on sets of source files. Source files, which
+implement program features, depend on header files, which expose type and
+function declarations. These, in turn, might depend on generated source files
+generated by `lex`, `yacc` or any other of an assortment of codegenerating
+tools. These dependencies can be modeled with a directed graph.
+
+For this example, we're actually going to use some of the files that actually
+implement the examples described in this user's guide. Their dependencies are
+shown in figure 1. Path names have been omitted for readability.
+
+[$images/guide/files.png]
+
+From this graph, it should be relatively easy to see that the build should
+start at the bottom and proceed "upwards" with the executable programs being
+built last  maybe. There are actually two different approaches to bulding
+these programs:
+
+* One at a time. This is probably what you're used to seeing. The compiler
+builds file A, followed by file B, and finally file C.
+* In parallel. If you're lucky enough to have a multiprocessor computer
+available to you we might be able to process (compile) a number of different
+files at the same time by distributing the tasks to different processors.
+
+The solution to both of these problems is addressed by topologically sorting
+the graph. This provies the schedule of files to be processed by ordering
+the vertices based on their dependencies.
+
+A third problem we might encounter is that of cycles in the dependency
+graph. Cycles are bad since topological sorts will not work in their presence.
+
+[h4 Makefiles and Graphs]
+The first step in implementing a makeordering for source files is acquiring
+some data. For this example, we our program will parse files in a stripped down,
+Makefilelike format. The input looks something like something like this.
+
+[pre
+undirected_graph.hpp : adjacency_list.hpp
+directed_graph.hpp : adjacency_list.hpp
+movies.hpp : undirected_graph.hpp
+movies.cpp : movies.hpp tokenizer.hpp
+kevin_bacon.cpp : movies.hpp visitors.hpp breadth_first_search.hpp
+kevin_bacon.exe : movies.cpp kevin_bacon.cpp
+build_order.cpp : directed_graph.hpp topological_sort.hpp
+build_order.exe : build_order.cpp
+]
+
+Obviously, we're going to have to build a parser for this input format. Just as
+before our program starts by defining aliases for commonly used template types.
+
+ struct Target;
+
+ typedef boost::directed_graph<Target> Graph;
+ typedef Graph::vertex_descriptor Vertex;
+ typedef Graph::edge_descriptor Edge;
+
+In this graph, vertex properties are encapsulated in a `Target` structure. For
+this application, a target is any named file that might appear in the dependency
+graph. Unlike the previous example, we really don't have any need for edge propreties,
+so we can simply omit that template parameter. The `Target` is defined as:
+
+ struct Target
+ {
+ int index;
+ std::string name;
+ };
+
+[note
+If you think you're seeing some similarities between the previous example, and this
+one... just wait. There are a number of common properties and tasks in many graph
+related problems such as indexing vertices, providing name labels, etc. Pay special
+attention to the method of adding vertices to the graph  the mapping of a unique
+name to a vertex is nearly ubiquitous in the setup of graph problems.
+]
+
+Likewise, we'll go ahead and predefine a property map that will be used later.
+We also need a mapping of target name to vertex so we don't duplicate vertices
+and have a convenient lookup tool later on.
+
+ typedef boost::property_map<Graph::type, int Target::*>::type TargetIndexMap;
+ typedef std::map<std::string, Vertex> TargetMap;
+
+We can now start building a program to parse the input data and build a dependency
+graph.
+
+ using namespace std;
+ using namespace boost;
+
+ int main()
+ {
+ typedef char_separator<char> separator;
+ typedef tokenizer<separator> tokenizer;
+
+ Graph grapg;
+ TargetMap targets;
+
+ for(string line; getline(cin, line); ) {
+ // skip comment and blank lines
+ if(line[0] == '#'  line.empty()) {
+ continue;
+ }
+
+ // split the string on the dependency
+ size_t index = line.find_first_of(':');
+ if(index == string::npos) {
+ continue;
+ }
+ string target = trim_copy(line.substr(0, index));
+ string deps = trim_copy(line.substr(index + 1));
+
+ // add the target to the build graph
+ Vertex u = add_target(graph, targets, target);
+
+ // tokenize the dependencies
+ separator sep(" \t");
+ tokenizer tok(deps, sep);
+ tokenizer::iterator i = tok.begin(), j = tok.end();
+ for( ; i != j; ++i) {
+ string dep = *i;
+
+ // add this dependency as a target
+ Vertex v = add_target(graph, targets, dep);
+
+ // add the edge
+ add_dependency(graph, u, v);
+ }
+ }
+
+ // ...to be continued...
+
+This is a fairly large chunk of code that implements input parsing and graph construction
+with the help of the `add_target()` and `add_dependency()` functions. Essentially, this
+snippet creates a vertex (target) for each file named in the input file. A dependency
+edge is added between the first target (preceeding the ':' character) and each subsequent
+target (white space separated list following the ':'). The `add_target()` and `add_dependency()`
+method are implemented as:
+
+ Vertex add_target(Graph& graph, TargetMap& targets, const string& name)
+ {
+ Vertex v;
+ TargetMap::iterator it;
+ bool inserted;
+ tie(it, inserted) = targets.insert(make_pair(name, Vertex()));
+ if(inserted) {
+ v = add_vertex(graph);
+ it>second = v;
+
+ graph[v].index = num_vertices(graph)  1;
+ graph[v].name = name;
+ }
+ else {
+ v = it>second;
+ }
+ return v;
+ }
+
+You may notice that the `add_target()` function is nearly lineforline identical to the
+`add_actor()` function in the previous example. This is no coincidence  both functions
+do exactly the same thing. They associate a vertex with a unique name and assign it an
+index that we can use later for various graph algorithms.
+
+ Edge add_dependency(Graph& graph, Vertex u, Vertex v)
+ {
+ return add_edge(v, u, graph).first;
+ }
+
+The `add_dependency()` method is considerably more terse than its undirected counter part,
+but essentially does the same thing. There is one very important difference, however:
+the direction of the edge is reversed to create a subtly different graph. Although
+the method is called to indicate that vertex `u` dependes on vertex `v`, the added edge
+actually indicates that vertex `v` satisfies the dependency of vertex `u`. In fact, this
+is the reverse of the original graph and is shown in Figure 2.
+
+[$images/guide/reverse.png]
+
+[h4 Obtaining the Make Order]
+We are now ready to compute the make order by running a topological sort. Thanks to a
+canned implementation, this is trivial.
+
+ int main()
+ {
+ // ...continued from above...
+
+ TargetIndexMap indices = get(&Target::index, graph);
+
+ typedef list<Vertex> MakeOrder;
+ MakeOrder order;
+ topological_sort(graph, front_inserter(order), vertex_index_map(indices));
+
+ BuildOrder::iterator i = order.begin(), j = order.end();
+ for( ; i != j; ++i) {
+ cout << graph[*i] << "\n";
+ }
+ }
+
+The `topological_sort()` algorithm takes an output iterator as the second parameter.
+Here, we use a standard front insertion iterator to prepend each target to the make
+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]
+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
+time that a file can be built assuming that an unlimited number of files can be built
+at the same time?". In our simplified example, the only criteria for when a file can
+be built is that it has no dependencies (i.e., in edges). Further simplifiying the
+example, we assume that each file takes the same amount of time to build (1 time unit).
+
+For parallel compilation, we can build all files with zero dependencies in the first
+time unit at the same time. For each file, the time at which it can be built is one
+more than the maximum build time of the files on which it depends. In this example,
+`adjacency_list.hpp` is one of the files that will compile first (in parallel).
+The `directed_graph.hpp` file will compile in the second time step, and `build_order.cpp`
+in the third.
+
+To implement this, we need a vector that represents the time slots in which each vertex
+will be built. By visiting the vertices in topological order, we ensure that we can
+assigned the correct time slot to each vertex since values "propogate" down the ordering.
+Just for fun, we'll merge the time ordering with the output so we can see a) the order
+in which each file is built and b) the time slot it could be built in.
+
+ int main()
+ {
+ // ...continued from above...
+ vector<int> time(num_vertices(graph), 0);
+ BuildOrder::iterator i = order.begin(), j = order.end();
+ for( ; i != j; ++i) {
+ int slot = 1;
+ Graph::in_edge_iterator j, k;
+ for(tie(j, k) = in_edges(*i, graph); j != k; ++j) {
+ Vertex v = source(*j, graph);
+ slot = std::max(time[graph[v].index], slot);
+ }
+ time[g[*i].index] = slot + 1;
+
+ cout << g[*i].name << "\t[" << time[g[*i].index] << "]\n";
+ }
+ }
+
+This is a code may be a little dense, but demonstrates two important aspects of
+the Boost.Graph library. First this demonstrates the importantance of vertex
+indices. Despite their instability with mutable graphs, many (most?) graph algorithms
+use vertex indices to efficiently associate extra data with a vertex. In fact, this
+approach is so ubiquitous in the examples that it leads many to believe the
+`vertex_descriptor` is always the index of a vertex.
+
+[warning
+A `vertex_descriptor` is *not* its index in the graphs container of vectors!
+]
+
+The second important aspect this demonstrates is the construction of an /external
+property/ for vertices. Although we don't use the `time` vector in any additional
+computations, we could easily turn it into a property map for use with other
+algorithms.
+
+The output might something like this:
+
+[pre
+$ ./make_order < files
+topological_sort.hpp [0]
+breadth_first_search.hpp [0]
+visitors.hpp [0]
+tokenizer.hpp [0]
+adjacency_list.hpp [0]
+directed_graph.hpp [1]
+build_order.cpp [2]
+build_order.exe [3]
+undirected_graph.hpp [1]
+movies.hpp [2]
+kevin_bacon.cpp [3]
+movies.cpp [3]
+kevin_bacon.exe [4]
+]
+
+Although it probably won't since I doctored the tabbing for display purposes.
+
+[h4 Finding Cycles]
+Admittedly, cycles in dependency graphs for software probably don't occur so often
+that we need to develop special software to find them. However, if the dependency
+graph is big (think about all the source code, binaries, data files and thier
+dependencies that constitute a typical Linux distribution), then its possible that
+cycles creep into the graph. It might be nice to determine if there is such a cycle
+before actually trying to build it.
+
+To do this, we are going to provide a customized visitor for a depthfirst search (DFS).
+Just like the custom visitors in our undirected graph examples, we overload a visitor
+event (here, the `back_edge` event) to indicate that a cycle has been found. Using the
+same setup as before, our visitor follows:
+
+ struct CycleDetector : public dfs_visitor<>
+ {
+ CycleDetector(bool& c)
+ : has_cycle(c)
+ {}
+
+ template <class Edge, class Graph>
+ void back_edge(Edge, Graph&)
+ {
+ has_cycle = true;
+ }
+
+ bool& has_cycle;
+ };
+
+ CycleDetector detect_cycles(bool& c)
+ { return CycleDetector(c); }
+
+That's it... When the `back_edge()` method is called, we know that a cycle exists
+in the graph. This literally indicates that there is an edge to a vertex that we
+have already visited, hence: a cycle. We also provide a helper function that
+instantiates the visitor.
+
+Using the cycledetecting visitor is just as easy as before. After constructing the
+graph, we would find the following in the `main()` program.
+
+ int main()
+ {
+ // ...continued from above...
+
+ TargetIndexMap indices = get(&Target::index, g);
+
+ bool cycle = false;
+ depth_first_search(g,
+ vertex_index_map(indices).
+ visitor(detect_cycles(cycle)));
+ cout << "has cycle: " << cycle << "\n";
+ }
+
+Unfortunately, our test input file doesn't currently contain any cycles  a sign of
+good engineering  so we'll have to add one. Add the following lines to the input
+to create a completely superfluous cycle.
+
+[pre
+movies.exe : kevin_bacon.exe
+kevin_bacon.exe : movies.exe
+]
+
+Running the program on the modified input should yield:
+
+[pre
+$ ./cycle < files
+has cycle: 1
+]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/guide.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/guide.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,14 @@
+[/
+ / 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 User's Guide]
+
+[include undirected_graph.qbk]
+[include directed_graph.qbk]
+[include adjacency_list.qbk]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/undirected_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/undirected_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,473 @@
+[/
+ / 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 Undirected Graphs]
+In this section, our example revolves around a particular type of /social network/.
+A social network is a graph that models the relationships between people. Specifically,
+in this example we are looking at a graph that connects costars of films.
+
+[h3 CoStar Graphs]
+The first example problem we want to look at is the "Six Degrees of Kevin Bacon"
+problem. In this problem, two actors are related if they appear in the same movie,
+which can be trivially represented using an undirected graph.
+
+For the Six Degrees problem, we define a citation graph such that each vertex in
+the graph represents an actor, and each edge connects two actors if and only if
+they appear in the same movie. Consider the example in Figure 1. Here we have
+ten relatively wellknown actors and the movies in which they appear together 
+and yes, Kevin Bacon is actually in /Animal House/ (he plays a snotty Omega pledge
+in his film debut).
+
+[$images/guide/movie.png]
+
+Although this is a relatively simple graph, it isn't hard to imagine that it
+scales up fairly quickly. Consider what would happen if we added all of Kevin
+Bacon's costars from major motion picture in which he starred  and all of
+their costars. It's not hard to imagine that only three iterations might
+actually encompass all of Hollywood and beyond (Bollywood?). So what can we do
+with these graphs?
+
+For starters, we can identify two different problems of the "Six Degrees".
+
+* How far is every actor in the graph from Kevin Bacon? This gives us the number
+of steps between Mr. Bacon and any other actor. The distances from a central actor
+can give clues to the size (especially the diameter) of a graph.
+* What is the "fastest" way to travel along the costar graph from Kevin Bacon
+to any other actor? This is more commonly known as the "Six Degrees of Kevin
+Bacon Game".
+
+These are actually two different instances of the same problem and can be solved
+using the same algorithm  a simple breadthfirst search (BFS).
+
+[note
+The term "six degrees of separation" refers to the total distance one must travel
+in a social network to get from one's self to any other person in the network.
+This notion is supported through a number of social experiments, namely that of
+Stanley Milgram who coined the term "small world" with respect to social networks.
+His experiment showed that Americans are connected, on average by six friendships.
+The notion of a "small world" social network is now nearly synonymous with a
+graph having an average degree of connectivity (formally known as its /mean geodesic
+distance/) of just six steps.
+
+On a side note, the name "Six Degrees of Kevin Bacon" can be attributed to a
+producer on /The Jon Stewart Show/ when the creators (students from Abright
+College) made an appearence to discuss and demonstrate the concept.
+]
+
+[h4 Actors, Movies, and Graphs]
+
+Our program begins by inlcuding required headers and creating some convenient
+type aliases.
+
+ #include <string>
+ #include <map>
+ #include <boost/graph/undirected_graph.hpp>
+ #include <boost/graph/breadth_first_search.hpp>
+
+ struct Actor;
+ struct Movie;
+
+ typedef boost::undirected_graph<Actor, Movie> Graph;
+ typedef Graph::vertex_descriptor Vertex;
+ typedef Graph::edge_descriptor Edge;
+
+In this snippet, our `Actor` structure is going to represent the properties of each
+vertex in the graph while the `Movie` structure encapsulates edge information (i.e.,
+the movie that two actors appear in).
+
+The graph itself is defined by the type `boost::undirected_graph<Actor, Movie>`.
+Essentially, this states that each vertex will have properties given in the `Actor`
+structure, and that edges will have properties in the `Movie` structure. We also
+create some aliases for the graph's vertex and edge descriptors.
+
+[important
+Many of the examples in the Boost Graph Library treat vertex descriptors as the
+index of a vertex within the graph. It must be noted however, that this is not
+a reliable approach to indexing vertices and /will not/ work with the `undirected_graph`
+and `directed_graph` classes. Try to get in the habit of thinking of vertex and
+edge descriptors as opaque types and values  they are simply keys that provide
+access to the properties of their respective types.
+]
+
+In order to fully model our problem, we need to finish defining the `Actor` and
+`Movie` structures for our graph.
+
+ struct Actor
+ {
+ int distance;
+ std::string name;
+ };
+
+ struct Movie
+ {
+ std::string name;
+ };
+
+In this example, we are "internalizing" a couple of properties for each vertex.
+The `Actor::distance` property will be used to record the distance from each actor
+to Kevin Bacon. The `Actor::name` and `Movie::name` properties should be fairly
+selfexplanatory. However in this example, we are going to require that all actors
+have unique names. We'll see why in a bit.
+
+We're also going to define a number of other types related to the graphs properties:
+/property maps/. These maps provide a mechanism for accessing the interior and exterior
+properties of vertices and edges in a uniform manner. In this example, all of the
+vertex and edge properties are internal, but we could easily make them external and
+have the program run just as quickly.
+
+ typedef boost::property_map<Graph, int Actor::*>::type ActorDistanceMap;
+
+The first template argument `Graph` defines the type of the graph that
+the property map is going to access. The second template argument with the somewhat
+peculiar syntax is the type of the property. These are pointers to `Actor` member
+variables of type `int`.
+
+Now that the preliminaries are out of the way, we need to concentrate on the construction
+of our graph. For this task, we're going to need another data structure that maps actor
+names to vertices in the graph. We're going to use this to prevent adding mulitple
+vertices for the same actor and later, to find the vertex in the graph that corresponds to
+Kevin Bacon.
+
+This program reads an input file from standard input. The input file is given in an edge
+list format with semicolon separators. Each line corresponds to an edge, giving the two
+actors as the endpoints and the name of the movie they both appear in. For example:
+[pre
+Tim Matheson;Kevin Bacon;Animal House (1978)
+John Belushi;Kevin Bacon;Animal House (1978)
+Carrie Fisher;John Belushi;The Blues Brothers (1980)
+Mark Hamill;Carrie Fisher;Star Wars (1977)
+]
+
+The following function implements the input parser for the graph data.
+
+ #include <boost/tokenizer.hpp>
+
+ // the very important actortovertex mapping
+ typedef std::map<std::string, Vertex> ActorMap;
+
+ using namespace std;
+ using namespace boost;
+
+ void build_costar_graph(istream& is, Graph& graph, ActorMap&)
+ {
+ // pull all of the data from std in.
+ for(string line; getline(is, line); ) {
+ // skip any comment or blank lines
+ if(line[0] == '#'  line.empty()) {
+ continue;
+ }
+
+ // tokenize the string
+ char_delimiters_separator<char> sep(false, "", ";");
+ tokenizer<> tok(line, sep);
+ tokenizer<>::iterator i = tok.begin();
+
+ // grab the names of the two actors and the movie title
+ string first = *i++;
+ string second = *i++;
+ string movie = *i++;
+
+ // get the vertices associated with the actors adding them
+ // to the graph if necessary
+ Vertex
+ u = add_actor(g, actors, first),
+ v = add_actor(g, actors, second);
+
+ // create an edge (movie) linking the actors
+ add_movie(g, u, v, movie);
+ }
+ }
+
+To finish graph construction, we need to implement the `add_actor()` and `add_movie()`
+functions:
+
+ Vertex add_actor(Graph& graph, ActorMap& actors, const string& name)
+ {
+ // try inserting the actors name into the actors map
+ Vertex v;
+ ActorMap::iterator it;
+ bool inserted;
+ tie(it, inserted) = actors.insert(make_pair(name, Vertex()));
+
+ if(inserted) {
+ // if the vertex was inserted into the map, we need to
+ // create a new vertex in the graph and make sure that
+ // the map references the correct vertex
+ v = add_vertex(graph);
+ it>second = v;
+
+ // configure the vertex properties
+ g[v].name = name;
+ }
+ else {
+ // otherwise, the name is already in the map, so
+ // return the vertex associated with it
+ v = it>second;
+ }
+
+ return v;
+ }
+
+ Edge add_movie(Graph& g, Vertex u, Vertex v, const string& movie)
+ {
+ Edge e;
+ bool inserted;
+ tie(e, inserted) = add_edge(u, v, g);
+ if(inserted) {
+ g[e].name = movie;
+ }
+ return e;
+ }
+
+There are several important features of these two functions to pay special attention to.
+The first is the use of the `tie()` constructor. This is arguably one of the most useful
+and most used functions (it's actually a type) in Boost.Graph. It simply takes the
+values returned in a `std::pair` and assigns them to the variables passed to the
+constructor. In this function it is more or less equivalent to:
+
+ std::pair<ActorMap::Iterator, bool> x = actors.insert(...);
+ ActorMap::iterator iter = x.first;
+ bool inserted = x.second;
+
+The second (and most important) is the assignment of the vertex properties. These
+two lines of code use the /bundled properties/ syntax to assign both an index
+and a name to the vertex that was just added to the graph.
+
+Our main program looks like this:
+
+ int main()
+ {
+ Graph graph;
+ ActorMap actors;
+ build_costar_graph(cin, graph, actors);
+
+ // ...to be continued...
+ }
+
+[h4 Distance To Kevin Bacon]
+Now, all we have left to do is assign distances to Kevin Bacon. To do this, we're going
+to use a breadthfirst search (starting from Kevin Bacon) and simply record the "depth"
+of each vertex as the distance from Kevin to every other actor. Fortunately, Boost.Graph
+gives us lots of help in this area so we don't have to write much more code. Let's look
+at the main program.
+
+ int main()
+ {
+ // ...continued from above...
+
+ // find kevin (our starting point)
+ Vertex kevin = actors["Kevin Bacon"];
+
+ // get a property map and zero out kevin's distancetoself
+ ActorDistanceMap distances = get(&Actor::distance, graph)
+ distances[kevin] = 0;
+
+ breadth_first_search(graph, kevin,
+ visitor(
+ make_bfs_visitor(record_distances(distances, on_tree_edge()))
+ )
+ );
+
+ // ...to be continued...
+
+This is actually the "meat" of the solution. First, get a reference to the vertex that
+represents Kevin Bacon  our `ActorMap` is very good at this. Next we have to get the
+property map for our actor's distances so we can set Kevin's distance to zero. In this
+case, the actor's distance is actually a /bundled property/ of the `Actor` structure.
+
+Finally, we invoke the `breadth_first_search()` on `graph` with `kevin` as our starting
+vertex. The `visitor()` function is actually a /named parameter/  a function that assigns
+a value to a parameter of an algorithm. In this case, the parameter is the /visitor/
+parameter (as indicated by the function name). The value is in turn provided by the
+`make_bfs_visitor()` function, which creates visitor object depnding on the parameters.
+The `record_distances()` function creates a `distance_recorder` visitor. The `distances`
+argument is our property map, indicating that the visitor will operate on those values.
+Finally, the `on_tree_edge()` call instructs the `distance_recorder` to record distances
+when a new edge in the BFS tree is encountered. This BFS visitor will effectively compute
+the distance from a root vertex to all other vertices in the graph.
+
+This is a somewhat verbose way of writing the code. We could write it a little more
+succinctly, although it's somewhat less readable:
+
+ graph[kevin].distance = 0;
+ breadth_first_search(graph, kevin,
+ visitor(make_bfs_visitor(record_distances(get(&Actor::distance, graph), on_tree_edge())))
+ );
+
+After finishing, each vertex's distance property will be assigned. All there is left to do
+is display the numbers:
+
+ int main()
+ {
+ // ...continued from above...
+ Graph::vertex_iterator i, j;
+ for(tie(i, j) = vertices(g); i != j; ++i) {
+ cout << graph[*i].distance << " : " << graph[*i].name << "\n";
+ }
+ }
+
+The output should look something like this (note that $ is a shell prompt):
+[pre
+$ ./kevin_bacon < movies
+1 : Chris Penn
+1 : Sarah Jessica Parker
+2 : James Belushi
+2 : David Ogden Stiers
+3 : Mark Hamill
+3 : Dan Akroyd
+1 : John Belushi
+1 : Tim Matheson
+2 : Tom Hulce
+2 : Peter Riegert
+2 : Karen Allen
+2 : Mike Meyers
+2 : Sylvester Stallone
+2 : Eddie Murphy
+]
+
+[h4 The Kevin Bacon Game]
+Using the above algorithm we can find how far away each actor is from Kevin Bacon, but what
+if we want to know how to get there. For example, we know that Dan Akroyd is three steps away
+so what are the movies? We could look at the input file, but that won't really give us any
+advantage. A better solution would be to modify the program to record the shortest paths.
+
+Since the term /shortest paths/ arises in the problem description, we might be tempted to
+use a shortest paths algorithm such as Dijkstra's. However, if we think about the problem a
+little bit, we should realize that there aren't any edge weights  something required for
+Dijkstra's algorithm. We could implicitly treat all edges as having a weight of one, but
+that turns out to be somewhat ineffective. It turns out that we can use the same BFS
+algorithm to record shortest paths instead of (or in addition to) actors' distances to
+Kevin Bacon. Specifically, we can record each the parent of each vertex in the BFS tree
+and simply backtrack from a given actor to Kevin Bacon.
+
+There are only a couple of modifications that we really need to make. First, we want to
+add an extra property for each actor: its parent vertex in the search tree. For convenience,
+we are also going to add a new property map type.
+
+ struct Actor
+ {
+ // ...same as before...
+ Vertex parent;
+ };
+
+ // ...
+ typedef boost::property_map<Graph::type, &Vertex Actor::*>::type ActorParentMap;
+
+The only other changes are going to be in the `main()` program.
+
+ int main(int argc, char *argv[])
+ {
+ string src = "Kevin Bacon";
+ string tgt;
+
+ if(argc < 2) {
+ cerr << "usage: actor_paths actor [actor] < movies";
+ return 1;
+ }
+ else if(argc == 2) {
+ tgt = argv[1];
+ }
+ else {
+ src = argv[1];
+ tgt = argv[2];
+ }
+
+ Graph graph;
+ ActorMap actors;
+ build_costar_graph(cin, graph, actors);
+
+ // ...to be continued...
+
+This program accepts a couple of command line parameters. If one actor is given then
+we find the path to Kevin Bacon. If two actors are given, we find the shortest path
+between the two actors. We can now get the vertices for specified actors, and find
+the paths between them.
+
+ // ...continued from before...
+ Vertex u = find_actor_vertex(g, actors, src);
+ Vertex v = find_actor_vertex(g, actors, tgt);
+ if(u == Graph::null_vertex()) {
+ cerr << "could not find actor " << src << "\n";
+ return 1;
+ }
+ if(v == Graph::null_vertex()) {
+ cerr << "could not find actor " << tgt << "\n";
+ return 1;
+ }
+
+ // get the parents map for later use.
+ ActorParentMap parents = get(&Actor::parent, g);
+
+ breadth_first_search(graph, kevin,
+ visitor(
+ make_bfs_visitor(record_predecessors(distances, on_tree_edge()))
+ )
+ );
+
+ // ...to be continued...
+
+The `find_actor_vertex()` method is relatively trivial. We extracted it as a function
+so the program wouldn't be quite so repetitive.
+
+ Vertex find_actor_vertex(const Graph& g, const ActorMap& actors, const std::string& name)
+ {
+ Vertex v = Graph::null_vertex();
+ ActorMap::const_iterator i = actors.find(name);
+ if(i != actors.end()) {
+ v = i>second;
+ }
+ return v;
+ }
+
+Otherwise, the code is essentially the same as above. In this case, we're constructing
+a `predecessor_recorder` as the visitor to the BFS. In contrast to the `distance_recorder`
+this method stores the parents (or predecessor) of each vertex in the BFS tree. This is
+an important property because it allows us to backtrack from one endpoint in the graph
+to the starting point, showing the path from, say Kevin Bacon to any another actor.
+
+Backtracking is relatively easy.
+
+ int main(...)
+ {
+ // ...continued from before...
+ while(v != u) {
+ Vertex p = parents[v];
+ string from = g[v].name;
+ string to = g[p].name;
+
+ // find the edge so we can print the movie
+ Edge e;
+ bool found;
+ tie(e, found) = edge(v, p, g);
+
+ string movie = g[e].name;
+ cout << from << " starred with " << to << " in '" << movie << "'\n";
+
+ v = p;
+ }
+
+ return 0;
+ }
+
+Althgough we could simply backtrack over the parents and print the actors in a chain,
+we think it's more entertaining to know the movies that each pair costars in. To do
+this we use the `edge()` function to locate the edge corresponding edge connecting
+the two actors who costarred in a movie.
+
+The output might look something like:
+[pre
+$ ./six_degrees "Dan Akroyd" < movies
+Dan Akroyd starred with Carrie Fisher in 'The Blues Brothers (1980)'
+Carrie Fisher starred with Elisabeth Shue in 'Soapdish (1991)'
+Elisabeth Shue starred with Kevin Bacon in 'Hollow Man (2000)'
+]
+
+You now have a completely /unbeatable/ implementation of the "Six Degrees of Kevin
+Bacon" game  provided of course that you add a lot more movie data to the simple
+data set provided with this example.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/history.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/history.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,110 @@
+[/
+ / 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 History]
+
+The Boost Graph Library began its life as the Generic Graph Component Library (GGCL), a software
+project at the Lab for Scientific Computing (LSC) at the University of Notre Dame, under the
+direction of Professor Andrew Lumsdaine. The Lab's research directions include numerical linear
+algebra, parallel computing, and software engineering (including generic programming).
+
+Soon after the Standard Template Library was released, work began at the LSC to apply generic
+programming to scientific computing. The Matrix Template Library (Jeremy Siek's masters thesis)
+was one of the first projects. Many of the lessons learned during construction of the MTL were
+applied to the design and implementation of the GGCL.
+
+Graph algorithms play an important role in sparse matrix computations, so the LSC had a need for
+a good graph library. However, none of the available graph libraries (LEDA, GTL, Stanford GraphBase)
+were written using the generic programming style of the STL, and hence did not fulfill the flexibility
+and highperformance requirements of the LSC. Others were also expressing interest in a generic C++
+graph library. During a meeting with Bjarne Stroustrup we were introduced to several people at AT&T
+who needed such a library. There had also been earlier work in the area of generic graph algorithms,
+including some codes written by Alexander Stepanov, and Dietmar Kuhl's masters thesis.
+
+With this in mind, and motivated by homework assignments in his algorithms class, Jeremy began
+prototyping an interface and some graph classes in the spring on 1998. LieQuan Lee then developed
+the first version of GGCL, which became his masters thesis project.
+
+The following year, Jeremy went to work for SGI with Alexander Stepanov and Matt Austern. During
+this time Alex's disjointsets based connected components algorithm was added to GGCL, and Jeremy
+began working on the concept documentation for GGCL similar to Matt's STL documentation.
+
+While working at SGI, Jeremy heard about Boost and was excited to find a group of people interested
+in creating highquality C++ libraries. At Boost there were several people interested in generic
+graph algorithms, most notably Dietmar Kuhl. Some discussions about generic interfaces for graph
+structures resulted in the a revision of GGCL which closely resembles the current Boost Graph Library
+interface.
+
+On September 4, 2000 GGCL passed the Boost formal review and became the Boost Graph Library (BGL).
+The first release of BGL was September 27, 2000.
+
+[h2 Changes by Revision]
+
+* Version 1.35.0
+ * New algorithms and components
+ * kolmogorov_max_flow, from Stephan Diederich as part of the 2006 Google Summer of Code.
+ * read_dimacs_max_flow and write_dimacs_max_flow for maxflow problems, from Stephan Diederich.
+ * read_graphml and write_graphml for GraphML input/output, from Tiago de Paula Peixoto.
+ * Enhancements
+ * LEDA Adaptor improvements, from Jens Muller.
+
+* Version 1.34.0
+ * New algorithms and components
+ * edmonds_maximum_cardinality_matching, from Aaron Windsor.
+ * lengauer_tarjan_dominator_tree, from JongSoo Park.
+ * compressed_sparse_row_graph, from Jeremiah Willcock and Douglas Gregor of Indiana University.
+ * sorted_erdos_renyi_iterator, from Jeremiah Willcock of Indiana University.
+ * Enhancements
+ * biconnected_components now has a visitor parameter and supports named parameters, from Janusz Piwowarski.
+ * adjacency_matrix now models the Bidirectional Graph concept.
+ * adjacency_list is now Serializable, from Jeremy Siek of Rice University.
+ * Added edges_size_type and vertices_size_type to adjacency_list_traits, from Jeremy Siek of Rice University.
+ * Added operator< , etc. to the edge descriptor of adjacency_list, from Jeremy Siek of Rice University.
+ * Bug Fixes
+ * Fixed a bug that causes the relaxed heap to fail on x86 Linux.
+ * Bundled properties now work with adjacency list I/O.
+ * floyd_warshall_all_pairs_shortest_paths now properly uses its compare, inf, and zero parameters.
+ * johnson_all_pairs_shortest_paths now supports compare, combine, inf, and zero.
+ * Fixed a bug in smallest_last_vertex_ordering.hpp which could cause a vertex to be moved to the wrong bucket during an BucketSorter update.
+
+* Version 1.33.1
+ * Bug Fixes
+ * fruchterman_reingold_force_directed_layout: Fixed enumeration of gridforce pairs, which caused some odd graph formations along grid lines.
+ * king_ordering and cuthill_mckee_ordering: Fixed bug that caused failures with the multicomponent version of these algorithms.
+
+* Version 1.33.0
+ * New algorithms and components
+ * Experimental Python bindings, from Doug Gregor and Indiana University.
+ * floyd_warshall_all_pairs_shortest_paths, from Lauren Foutz and Scott Hill.
+ * astar_search, from Kristopher Beevers and Jufeng Peng.
+ * fruchterman_reingold_force_directed_layout, from Doug Gregor and Indiana University.
+ * biconnected_components and articulation_points, from Indiana University.
+ * gursoy_atun_layout, from Jeremiah Willcock and Doug Gregor of Indiana University.
+ * king_ordering, from D. Kevin McGrath of Indiana University.
+ * erdos_renyi_iterator
+ * plod_iterator
+ * small_world_iterator
+ * Enhancements
+ * bellman_ford_shortest_paths now permits one to specify the starting vertex, so that it will perform its own initialization.
+ * undirected_dfs is now datarecursive, resulting in improved performance in some cases, from Synge Todo.
+ * dijkstra_shortest_paths now uses a relaxed heap [61] as its priority queue, improving its complexity to O(V log V) and improving realworld performance for larger graphs.
+ * read_graphviz now has a new, Spiritbased parser that works for all graph types and supports arbitrary properties on the graph, from Ron Garcia. The old, Bisonbased GraphViz reader has been deprecated and will be removed in a future Boost release.
+ * write_graphviz now supports output of dynamic properties (as read in through the new read_graphviz).
+ * cuthill_mckee_ordering has been recast as an invocation of breadth_first_search and now supports graphs with multiple components.
+ * subgraph now supports bundled properties. get_property now refers to the subgraph property, not the root graph's property.
+ * filtered_graph now supports bundled properties.
+ * reverse_graph now supports bundled properties, set_property, and get_property.
+ * Bug fixes
+ * bellman_ford_shortest_paths now deals with unreachable vertices better.
+ * adjacency_list: parallel edge removal with OutEdgeListS = listS has been fixed. Copying and swapping has been fixed.
+ * Incremental connected components: fixed a bug in the incremental_components routine that may have caused incorrect results.
+ * The remove_out_edge_if function for an undirected adjacency_list has been rewritten and should no longer dereference singular iterators.
+ * write_graphviz now accepts a vertex_id parameter that is used to name the nodes.
+ * read_graphviz now accepts empty attribute lists.
+ * sequential_vertex_coloring has been updated, tested, and documented.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/introduction.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/introduction.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,214 @@
+[/
+ / 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 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. 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 purpose graph classes that conform
+to this interface, but they are not meant to be the ``only'' graph classes; there certainly will
+be other graph classes that are better for certain situations. We believe that the main
+contribution of the The BGL is the formulation of this interface.
+
+The BGL graph interface and graph components are generic, in the same sense as the the Standard
+Template Library (STL). In the following sections, we review the role that generic programming
+plays in the STL and compare that to how we applied generic programming in the context of graphs.
+
+Of course, if you are already are familiar with generic programming, please dive right in! Here's
+the Table of Contents.
+
+The source for the BGL is available as part of the Boost distribution, which you can download
+from here.
+
+[h2 How to Build Boost.Graph]
+[*DON'T!] The Boost Graph Library is a headeronly library and does not need to be built to be used.
+The only exception is the GraphViz input parser.
+
+When compiling programs that use the BGL, be sure to compile with optimization. For instance,
+select "Release" mode with Microsoft Visual C++ or supply the flag O2 or O3 to GCC.
+
+[h2 Genericity in the STL]
+There are three ways in which the STL is generic.
+
+[h3 Algorithm/Data Structure Interoperability in the STL]
+First, each algorithm is written in a datastructure neutral way, allowing a single template
+function to operate on many different classes of containers. The concept of an iterator is the
+key ingredient in this decoupling of algorithms and datastructures. The impact of this technique
+is a reduction in the STL's code size from O(M*N) to O(M+N), where M is the number of algorithms
+and N is the number of containers. Considering a situation of 20 algorithms and 5 datastructures,
+this would be the difference between writing 100 functions versus only 25 functions! And the
+differences continues to grow faster and faster as the number of algorithms and datastructures
+increase.
+
+[h3 Extension Through Function Objects]
+The second way that STL is generic is that its algorithms and containers are extensible. The user
+can adapt and customize the STL through the use of function objects. This flexibility is what makes
+STL such a great tool for solving realworld problems. Each programming problem brings its own set
+of entities and interactions that must be modeled. Function objects provide a mechanism for extending
+the STL to handle the specifics of each problem domain
+
+[h3 Element Type Parameterization]
+The third way that STL is generic is that its containers are parameterized on the element type. Though
+hugely important, this is perhaps the least "interesting" way in which STL is generic. Generic
+programming is often summarized by a brief description of parameterized lists such as `std::list<T>`.
+This hardly scratches the surface!
+
+[h2 Genericity in Boost.Graph]
+Like the STL, there are three ways in which the BGL is generic.
+
+[h3 Algorithm/Data Structure Interoperability in Boost.Graph]
+First, the graph algorithms of the BGL are written to an interface that abstracts away the details
+of the particular graph datastructure. Like the STL, the BGL uses iterators to define the interface
+for datastructure traversal. There are three distinct graph traversal patterns: traversal of all
+vertices in the graph, through all of the edges, and along the adjacency structure of the graph
+(from a vertex to each of its neighbors). There are separate iterators for each pattern of traversal.
+
+This generic interface allows template functions such as breadth_first_search() to work on a large
+variety of graph datastructures, from graphs implemented with pointerlinked nodes to graphs
+encoded in arrays. This flexibility is especially important in the domain of graphs. Graph data
+structures are often custommade for a particular application. Traditionally, if programmers want
+to reuse an algorithm implementation they must convert/copy their graph data into the graph library's
+prescribed graph structure. This is the case with libraries such as LEDA, GTL, Stanford GraphBase;
+it is especially true of graph algorithms written in Fortran. This severely limits the reuse of their
+graph algorithms.
+
+In contrast, custommade (or even legacy) graph structures can be used asis with the generic graph
+algorithms of the BGL, using external adaptation (see Section How to Convert Existing Graphs to the
+BGL). External adaptation wraps a new interface around a datastructure without copying and without
+placing the data inside adaptor objects. The BGL interface was carefully designed to make this
+adaptation easy. To demonstrate this, we have built interfacing code for using a variety of graph
+dstructures (LEDA graphs, Stanford GraphBase graphs, and even Fortranstyle arrays) in BGL graph
+algorithms.
+
+[h3 Extension through Visitors]
+Second, the graph algorithms of the BGL are extensible. The BGL introduces the notion of a visitor,
+which is just a function object with multiple methods. In graph algorithms, there are often several
+key /event points/ at which it is useful to insert userdefined operations. The visitor object has
+a different method that is invoked at each event point. The particular event points and corresponding
+visitor methods depend on the particular algorithm. They often include methods like `start_vertex()`,
+`discover_vertex()`, `examine_edge()`, `tree_edge()`, and `finish_vertex()`.
+
+[h3 Vertex and Edge Property MultiParameterization]
+The third way that the BGL is generic is analogous to the parameterization of the elementtype
+in STL containers, though again the story is a bit more complicated for graphs. We need to
+associate values (called "properties") with both the vertices and the edges of the graph. In
+addition, it will often be necessary to associate multiple properties with each vertex and edge;
+this is what we mean by multiparameterization. The STL `std::list<T>` class has a parameter `T`
+for its element type. Similarly, BGL graph classes have template parameters for vertex and edge
+"properties". A property specifies the parameterized type of the property and also assigns an
+identifying tag to the property. This tag is used to distinguish between the multiple properties
+which an edge or vertex may have. A property value that is attached to a particular vertex or edge
+can be obtained via a property map. There is a separate property map for each property.
+
+Traditional graph libraries and graph structures fall down when it comes to the parameterization
+of graph properties. This is one of the primary reasons that graph datastructures must be
+custombuilt for applications. The parameterization of properties in the BGL graph classes makes
+them well suited for reuse.
+
+[h2 Algorithms]
+Boost.Graph algorithms consist of a core set of algorithm patterns (implemented as generic algorithms)
+and a larger set of graph algorithms. The core algorithm patterns are:
+* Breadth First Search
+* Depth First Search
+* Uniform Cost Search
+
+By themselves, the algorithm patterns do not compute any meaningful quantities over graphs; they are
+merely building blocks for constructing graph algorithms. The graph algorithms in the BGL currently
+include:
+
+* Dijkstra's Shortest Paths
+* BellmanFord Shortest Paths
+* Johnson's AllPairs Shortest Paths
+* Kruskal's Minimum Spanning Tree
+* Prim's Minimum Spanning Tree
+* Connected Components
+* Strongly Connected Components
+* Dynamic Connected Components (using Disjoint Sets)
+* Topological Sort
+* Transpose
+* Reverse Cuthill Mckee Ordering
+* Smallest Last Vertex Ordering
+* Sequential Vertex Coloring
+
+[h2 Data Structures]
+Boost.Graph currently provides two graph classes and an edge list adaptor:
+
+* adjacency_list
+* adjacency_matrix
+* edge_list
+
+The adjacency_list class is the general purpose "swiss army knife" of graph classes. It is highly
+parameterized so that it can be optimized for different situations: the graph is directed or
+undirected, allow or disallow parallel edges, efficient access to just the outedges or also to
+the inedges, fast vertex insertion and removal at the cost of extra space overhead, etc.
+
+The adjacency_matrix class stores edges in a V x V matrix (where V is the number of vertices).
+The elements of this matrix represent edges in the graph. Adjacency matrix representations are
+especially suitable for very dense graphs, i.e., those where the number of edges approaches V2.
+
+The `edge_list` class is an adaptor that takes any kind of edge iterator and implements an
+Edge List Graph.
+
+[h2 Projects Using This Library]
+This section should probably be merged into the global "Who's using me now page". But, for completeness
+here's the list (with links, too):
+
+* [@http://www.cs.rpi.edu/~musser/gsd/ Generic Software Design Course at RPI]
+* [@http://alps.compphys.org/ The ALPS quantum mechanics project]
+* [@http://bioinformatics.icmb.utexas.edu/lgl/ Large Graph Layout at University of Texas]
+* [@http://www.cs.concordia.ca/~gregb/home/c691Rw2004.html Bioinformatics Algorithms at Concordia University]
+* [@http://photon.poly.edu/~hbr/cs903/ Algorithm Course at Polytechnic University in Brooklyn]
+* [@http://www.bioconductor.org/repository/devel/vignette/RBGL.pdf BGL interface for language R]
+* [@http://www.cuj.com/documents/s=8470/cuj0307tan/ CUJ Article about Electronic Design Automation]
+* [@http://rubyforge.org/projects/rgl/ A BGLinspired Ruby Graph Library]
+* [@http://www.codeproject.com/cs/miscctrl/quickgraph.asp A BGLinspired C# Graph Library]
+* [@http://map1.squeakfoundation.org/sm/package/5729d80a822b4bc29420ef7ecaea8553 A BGLinspired Squeak (Smalltalk) Graph Library]
+* [@http://www.datasim.nl/education/coursedetails.asp?coursecategory=CPP&coursecode=ADCPP BGL course at DataSim]
+* [@http://www.vrjuggler.org/ VR Juggler: Virtual Reality Tools]
+* [@http://hyperworx.org Hyperworx Platform Project]
+
+[h2 Publications about this Library]
+* Dr. Dobb's Sept. 2000 Article
+* OOPSLA'99 GGCL Paper
+* LieQuan Lee's Master's Thesis about GGCL(ps) (pdf)
+* Dietmar Kuhl's Master's Thesis: Design Pattern for the Implementation of Graph Algorithms
+* ISCOPE'99 Sparse Matrix Ordering (pdf)
+* C++ Template Workshop 2000, Concept Checking
+
+[h2 Acknowledgements]
+We owe many debts of thanks to a number of individuals who both inspired and encouraged us in
+developing the Boost Graph Library.
+
+A most profound thanks goes to Alexander Stepanov for his pioneering work in generic programming,
+for his encouragement, and for his algorithm contributions to the BGL. We thank Matthew Austern for
+his work on documenting the concepts of STL which provided a foundation for creating the concepts in
+the BGL. We thank Dietmar Kuhl for his work on generic graph algorithms and design patterns;
+especially for the property map abstraction.
+
+Dave Abrahams, Jens Maurer, Beman Dawes, Gary Powell, Greg Colvin, Valentin Bonnard, and the rest
+of the group at Boost provided valuable input to the BGL interface, numerous suggestions for improvement,
+proof reads of the documentation, and help with polishing the code. A special thanks to Dave Abrahams
+for managing the formal review.
+
+We also thank the following BGL users whose questions helped to improve the BGL: Gordon Woodhull,
+Dave Longhorn, Joel Phillips, and Edward Luke.
+
+A special thanks to Jeffrey Squyres for editing and proof reading of the documentation.
+
+Our original work on the Boost Graph Library was supported in part by NSF grant ACI9982205 and by
+the Director, Office of Science, Division of Mathematical, Information, and Computational Sciences of
+the U.S. Department of Energy under contract number DEAC0376SF00098.
+
+In our work we also used resources of the National Energy Research Scientific Computing Center, which
+is supported by the Office of Science of the U.S. Department of Energy.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/adjacency_list.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/adjacency_list.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,411 @@
+[/
+ / 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 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()`
+
+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 adjacencylist is basically a
+twodimensional structure, where each element of the first dimension represents a
+vertex, and each of the vertices contains a onedimensional structure that is its
+edge list. Figure 1 shows an adjacency list representation of a directed graph.
+
+The VertexList template parameter of the adjacency_list class controls what kind
+of container is used to represent the outer twodimensional container. The
+OutEdgeList template parameter controls what kind of container is used to represent
+the edge lists. The choices for OutEdgeList and VertexList will determine the space
+complexity of the graph structure, and will determine the time complexity of the
+various graph operations. The possible choices and tradeoffs are discussed in
+Section Choosing the Edgelist and VertexList.
+
+The Directed template parameter controls whether the graph is directed, undirected,
+or directed with access to both the inedges and outedges (which we call
+bidirectional). The bidirectional graph takes up twice the space (per edge) of a
+directed graph since each edge will appear in both an outedge and inedge 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.
+
+[h3 Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`OutEdgeList`]
+ [
+ The selector for the container used to represent the edgelist for each
+ of the vertices.
+ ]
+ [`vecS`]
+ ]
+ [
+ [`VertexList`]
+ [
+ The selector for the container used to represent the vertexlist of the graph.
+ ]
+ [`vecS`]
+ ]
+ [
+ [`Directed`]
+ [
+ A selector to choose whether the graph is directed, undirected, or
+ directed with bidirectional edge access (access to both outedges
+ and inedges). The options are directedS, undirectedS, and
+ bidirectionalS.
+ ]
+ [`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`]
+ ]
+ [
+ [`EdgeList`]
+ [
+ The selector for the container used to represent the edgelist for
+ the graph.
+ ]
+ [`listS`]
+ ]
+]
+
+[h4 Model of]
+VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable,
+and Serializable.
+
+[h4 Where Defined]
+
+`boost/graph/adjacency_list.hpp`
+
+The serialization functionality is in `boost/graph/adj_list_serialize.hpp`.
+
+[h3 Vertex and Edge Properties]
+Properties such as color, distance, weight, and userdefined 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
+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.
+
+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
+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]
+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
+invalid. For example, the following code will result in undefined (bad)
+behavior:
+
+ typedef adjacency_list<listS, vecS> Graph; // VertexList = vecS
+ Graph G(N);
+
+ // Fill in the graph...
+
+ // Attempt to remove all the vertices. Wrong!
+ graph_traits<Graph>::vertex_iterator vi, vi_end;
+ for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
+ remove_vertex(*vi, G);
+ }
+
+ // Remove all the vertices. This is still wrong!
+ graph_traits<Graph>::vertex_iterator vi, vi_end, next;
+ tie(vi, vi_end) = vertices(G);
+ for(next = vi; vi != vi_end; vi = next) {
+ ++next;
+ remove_vertex(*vi, G);
+ }
+
+The reason this is a problem is that we are invoking remove_vertex(), which
+when used with an adjacency_list where VertexList=vecS, invalidates all
+iterators and descriptors for the graph (such as vi and vi_end), thereby
+causing trouble in subsequent iterations of the loop.
+
+If we use a different kind of `adjacency_list`, with `VertexList` as `listS`,
+then the iterators are not invalidated by calling remove_vertex unless the
+iterator is pointing to the actual vertex that was removed. The following code
+demonstrates this.
+
+ typedef adjacency_list<listS, listS> Graph; // VertexList = listS
+ Graph G(N);
+
+ // Fill in the graph...
+
+ // Attempt to remove all the vertices. Wrong!
+ graph_traits<Graph>::vertex_iterator vi, vi_end;
+ for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
+ remove_vertex(*vi, G);
+ }
+
+ // Remove all the vertices. This is OK.
+ graph_traits<Graph>::vertex_iterator vi, vi_end, next;
+ tie(vi, vi_end) = vertices(G);
+ for(next = vi; vi != vi_end; vi = next) {
+ ++next;
+ remove_vertex(*vi, G);
+ }
+
+The stability issue also affects vertex and edge descriptors. For example,
+suppose you use vector of vertex descriptors to keep track of the parents
+(or predecessors) of vertices in a shortest paths tree (see
+`examples/dijkstraexample.cpp`). You create the parent vector with a call
+to dijkstra_shortest_paths(), and then remove a vertex from the graph.
+Subsequently you try to use the parent vector, but since all vertex descriptors
+have become invalid, the result is incorrect.
+
+ std::vector<Vertex> parent(num_vertices(G));
+ std::vector<Vertex> distance(num_vertices(G));
+
+ dijkstra_shortest_paths(G, s,
+ distance_map(&distance[0])
+ .predecessor_map(&parent[0]));
+
+ remove_vertex(s, G); // Bad idea! Invalidates vertex descriptors in parent vector.
+
+ // The following will produce incorrect results
+ for(tie(vi, vend) = vertices(G); vi != vend; ++vi) {
+ std::cout << p[*vi] << " is the parent of " << *vi << std::endl;
+ }
+
+Note that in this discussion iterator and descriptor invalidation is concerned
+with the invalidation of iterators and descriptors that are not directly
+affected by the operation. For example, performing `remove_edge(u, v, g)` will
+always invalidate any edge descriptor for /(u,v)/ or edge iterator pointing to
+/(u,v)/, regardless of the kind `adjacency_list`. In this discussion of iterator
+and descriptor invalidation, we are only concerned with the affect of
+`remove_edge(u, v, g)` on edge descriptors and iterators that point to other
+edges (not /(u,v)/).
+
+In general, if you want your vertex and edge descriptors to be stable (never
+invalidated) then use listS or setS for the VertexList and OutEdgeList template
+parameters of adjacency_list. If you are not as concerned about descriptor and
+iterator stability, and are more concerned about memory consumption and graph
+traversal speed, use vecS for the VertexList and/or OutEdgeList template
+parameters.
+
+The following table summarizes which operations cause descriptors and iterators
+to become invalid. In the table, OEL is an abbreviation for OutEdgeList and VL
+means VertexList. The "Adjacency Iterator" category includes the `out_edge_iterator`,
+`in_edge_iterator`, and `adjacency_iterator types`. A more detailed description of
+descriptor and iterator invalidation is given in the documentation for each
+operation.
+
+[table
+ [[Function] [Vertex Descriptor] [Edge Descriptor] [Vertex Iterator] [Edge Iterator] [Adjacency Iterator]]
+ [
+ [`add_edge()`]
+ [Valid]
+ [Valid]
+ [Valid]
+ [
+ OEL = `vecS` &&
+
+ Directed = `directedS`]
+ [OEL = `vecS`]
+ ]
+ [
+ [
+ `remove_edge()`
+
+ `remove_edge_if()`
+
+ `remove_out_edge_if()`
+
+ `remove_in_edge_if()`
+
+ `clear_vertex()`
+ ]
+ [Valid]
+ [Valid]
+ [Valid]
+ [
+ OEL = `vecS` &&
+
+ Directed = `directedS`]
+ [OEL = `vecS`]
+ ]
+ [
+ [`add_vertex()`]
+ [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.
+ ]
+ ]
+]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,153 @@
+[/
+ / 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 BreadthFirst Search]
+ template <class Graph, class P, class T, class R>
+ void
+ breadth_first_search(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+ template <class Graph, class Buffer, class Visitor, class P, class T, class R>
+ void
+ breadth_first_search(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ Buffer& q,
+ Visitor vis,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+The `breadth_first_search()` function performs a breadthfirst traversal \[49\] of a directed or
+undirected graph. A breadthfirst traversal visits vertices that are closer to the source before
+visiting vertices that are further away. In this context "distance" is defined as the number of edges
+in the shortest path from the source vertex. The `breadth_first_search()` function can be used to
+compute the shortest path from the source to all reachable vertices and the resulting shortestpath
+distances. For more definitions related to BFS, see section BreadthFirst Search.
+
+BFS uses two data structures to to implement the traversal: a color marker for each vertex and
+a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered
+adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray
+vertices. The algorithm proceeds by removing a vertex /u/ from the queue and examining each outedge
+/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
+queue. After all of the outedges are examined, vertex u is colored black and the process is
+repeated. Pseudocode for the BFS algorithm is a listed below.
+
+[pre
+BFS(G, s)
+ for each vertex u in V\[G\] initialize vertex u
+ color\[u\] := WHITE
+ d\[u\] := infinity
+ p\[u\] := u
+ end for
+
+ color\[s\] := GRAY
+ d\[s\] := 0
+ ENQUEUE(Q, s) discover vertex s
+
+ while not EMPTY(Q)
+ u := DEQUEUE(Q) examine vertex u
+ for each vertex v in adj\[u\] examine edge /(u,v)/
+ if(color\[v\] = WHITE) /(u,v)/ is a tree edge
+ color\[v\] := GRAY
+ d\[v\] := d\[u\] + 1
+ p\[v\] := u
+ ENQUEUE(Q, v) discover vertex v
+ else /(u,v)/ is a nontree edge
+ if (color\[v\] = GRAY) /(u,v)/ has a gray target
+ ...
+ else /(u,v)/ has a black target
+ ...
+ end if
+ end for
+ color\[u\] := BLACK finsih vertex u
+ end while
+ return (d, p)
+]
+
+[heading Where Defined]
+`boost/graph/breadth_first_search.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`Graph& g`]
+ [
+ A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
+ and [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [in] [`vertex_descriptor s`]
+ [
+ The source vertex where the search is started. This must be a valid vertex descriptor of
+ `g`.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`visitor(Visitor vis)`]
+ [
+ A visitor object that is inovked inside the algorithm at event points specified by the
+ [BoostBFSVisitor]. The `vis` object must be model the [BoostBFSVisitor] concept.
+
+ *Default* `bfs_visitor<null_visitor>`.
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VeretxIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [util] [`buffer(Buffer& q)`]
+ [
+ The queue used to determine the order in which vertices will be discovered.
+ If a FIFO queue is used, then the traversal will be according to the usual
+ BFS ordering. Other types of queues can be used, but the traversal order will
+ be different. For example Dijkstra's algorithm can be implemented using a
+ priority queue. The type Buffer must be a model of [NoConcept Buffer].
+
+ The `value_type` of the buffer must be the vertex_descriptor type for the graph.
+
+ *Default* `boost::queue`
+ ]
+ ]
+]
+
+[heading Complexity]
+The time complexity is /O(E + V)/.
+
+[heading Example]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connected_components.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/connected_components.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,94 @@
+[/
+ / 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 Connected Components]
+ template <class Graph, class ComponentMap, class P, class T, class R>
+ typename property_traits<ComponentMap>::value_type
+ connected_components(const Graph &g, ComponentMap c,
+ const bgl_named_params<P,T,R>& params = ``/defaults/``);
+
+
+The connected_components() functions compute the connected components of an undirected
+graph using a DFSbased approach. A connected component of an undirected graph is a
+set of vertices that are all reachable from each other. If the connected components
+need to be maintained while a graph is growing the disjointset based approach of
+function `incremental_components()` is faster. For "static" graphs this DFSbased
+approach is faster \[8\].
+
+The output of the algorithm is recorded in the component property map, which will
+contain numbers giving the component number assigned to each vertex. This algorithm
+returns the total number of connected components in the graph.
+
+[heading Where Defined]
+`boost/graph/connected_components.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`const Graph& g`]
+ [
+ The /undirected/ graph for which connected components are being found.
+ This graph must be a model of VertexListGraph and Incidence Graph.
+ ]
+ ]
+ [
+ [out] [`ComponentMap c`]
+ [
+ The algorithm computes how many connected components are in the graph,
+ and assigning each component an integer label. The algorithm then records
+ which component each vertex in the graph belongs to by recording the
+ component number in the component property map. The ComponentMap type
+ must be a model of WritablePropertyMap. The value type shouch be an
+ integer type, preferably the same as the `vertices_size_type` of the
+ graph. The key type must be the graph's `vertex_descriptor` type.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VertexIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+]
+
+[heading Complexity]
+This algorithm runs in /O(V + E)/.
+
+[heading Notes]
+This algorithm will not compile if passed a /directed/ graph.
+
+[heading Examples]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,207 @@
+[/
+ / 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 Connectivity Measures]
+
+ template <
+ typename Graph,
+ typename Components,
+ typename SizeType,
+ typename ComponentMap,
+ typename ColorMap,
+ typename VertexIndexMap
+ >
+ std::size_t
+ connectivity(
+ const Graph& _graph,
+ Components& _components,
+ SizeType _number = 0,
+ ComponentMap _component_map = ``['nothing]``,
+ ColorMap _color_map = ``['nothing]``,
+ VertexIndexMap _vertex_index_map = get(vertex_index, _graph));
+
+The `connectivity()` algorithm is a wrapper around the [boost_connected_components]
+algorithm that provides convenience for working with the resultant component maps.
+The parameters have, with the exeption of `_components`, the same purpose and requirements
+as documented in [boost_connected_components].
+
+The `_components` parameter will result in a sequence of "components" of the graph
+where each "component" is a sequence of vertices in the graph. After returning,
+the size of the `_components` parameter will be the number of connected components
+in the graph and each element in that sequence will contain a sequence of one or
+more vertices. Each vertex is assigned to only one component. The assignment is
+determined by the `_component_map`, whether passed to the algorithm or not.
+If a vertex `v` is mapped to component id `i` such that `_component_map[v] == i` then
+`v` will appear in the vertex sequence given by `_components[i]`.
+
+To help illustrate the structure and contents of the `_components` parameter,
+suppose, that after running [boost_connected_components], a graph is decomposed
+into two components.
+
+[figure
+ images/reference/connected_components_after.png
+ Figure 1. Components found after running [boost_connected_components]
+]
+
+Assume that we have stored each vertex into a vector, `v`, such that `v[i]`
+denotes the ['i[super th]] vertex in the graph above. The `_component_map` used
+for this decomposition associates each vertex with a component id.
+
+ _component_map[ v[0] ] == 0;
+ _component_map[ v[1] ] == 0;
+ _component_map[ v[2] ] == 0;
+ _component_map[ v[3] ] == 1;
+ _component_map[ v[4] ] == 1;
+
+However, the `_components` parameter associates each component with the vertices that
+comprise that component. Therefore, contents of the output sequence `_components` will
+be (in pseudoC++):
+
+ _components[0] == { v[0], v[1], v[2] };
+ _components[1] == { v[0], v[1], v[2] };
+
+This function returns the number of connected components in the graph.
+
+There are two distinct methods for calling this function: with or without the
+`_component_map` parameter. If the `_component_map` /is not/ given, then the
+algorithm must first compute the connected components of `_graph`. In this case,
+the user may need to supply the `_vertex_index_map` or an alternate `_color_map`.
+Calling the [boost_connectivity] function in this way will not provide access
+to a `_component_map` for the graph.
+
+If the _component_map /is/ given, then the algorithm assumes that connected
+components have already been assigned in the `_component_map`. In this case,
+`_color_map` and `_vertex_index_map` parameters are effectively ignored. Additionally
+the caller may pass the `_number` parameter to the function. If /not/ passed,
+the computation is required to determine the number of components in the graph
+by examining the `_component_map`. Passing `_number` as the return value of
+[boost_connected_components] allows this operation to be bypassed.
+
+[note
+This hasn't been tested very will for directed graphs. In fact, testing
+will probably result in the creation of `strong_connecity` which forwards the
+call to `strong_connected_components`.
+]
+
+[h5 Where Defined]
+`boost/graph/connectivity.hpp`
+
+[h5 Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`Graph _graph`]
+ [
+ The graph object for which the distribution will be computed. If
+ the `_distribution` or `_in_distribution` arguments are supplied
+ when calling this function then `_graph` must be a model of
+ [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+ then `_graph` must be a model of [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [required, out] [`Components _components`]
+ [
+ The components parameter provides storage for the assignment of
+ vertices to components. The `ComponentMap` parameter must be a
+ model of [SgiRandomAccessContainer] whose index type must be convertible
+ to the graphs `vertices_size_type`, and whose `value_type` must be
+ a model of [SgiBackInsertionSequence]. In turn, the `value_type` of
+ this [SgiBackInsertionSequence] must be the `vertex_descriptor` type
+ of `_graph`.
+ ]
+ ]
+ [
+ [optional, in] [`SizeType _number`]
+ [
+ This is the number of components in the graph as returned by a
+ prior call to [boost_connected_components]. The SizeType must
+ be convertible to the `vertices_size_type` of `Graph`.
+
+ *Default* /not given/
+ ]
+ ]
+ [
+ [optional, in] [`ComponentMap _component_map`]
+ [
+ The component map that represents the assignment of vertices to
+ distinct components in the graph. The `ComponentMap` must be
+ a model of [BoostReadablePropertyMap]. The `value_type` should be
+ integral, preferably the same as `vertices_size_type` for the
+ graph. The `key_type` must be the graph's `vertex_descriptor`.
+
+ *Default* /not given/
+ ]
+ ]
+ [
+ [optional, in] [`ColorMap _color_map`]
+ [
+ This is used by the [boost_connected_components] algorithm to keep
+ track of its progress through the graph. The type `ColorMap` must
+ be a model of [BoostReadWritePropertyMap], it's `key_type` must be
+ the `vertex_descriptor` type of `_graph` and its `value_type` must
+ be a model of [BoostColorValue].
+
+ *Default* /not given/
+ ]
+ ]
+ [
+ [optional, in] [`VertexIndexMap _vertex_index_map`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is necessary only `Graph` does not have builtin vertices
+ and/or a correct ordering on them.
+
+ *Default* `get(vertex_index, g)`
+ ]
+ ]
+]
+
+[h5 Return Value]
+This function returns the number of connected components. When the return value of
+this function is equal to `1`, then the graph is a single connected component.
+
+[h5 Complexity]
+This function has time complexity /O(V)/ and space complexity /O(V)/ (since each
+vertex is assigned to a component in the _components_vector).
+
+[h5 Examples]
+
+[note These are going to be expanded...]
+
+When a component map is not provided:
+
+ typedef undirected_graph<> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef vector<Vertex> Component;
+ typedef vector<Component> ComponentList;
+
+ Graph g;
+ // build a graph
+
+ ComponentList components;
+ connected_components(g, components);
+
+ size_t c = 0;
+ BOOST_FOREACH(Component comp, components) {
+ cout << "component: " << c++ << " : ";
+ BOOST_FOREACH(Vertex v, comp) {
+ cout << get(vertex_index, g, v) << " ";
+ }
+ cout << "\n";
+ }
+
+If the component map /is/ available...
+
+ // write some code to that effect.
+
+[h5 Details]
+The signature of this function may change in the future to include a new parameter, `_number`,
+which indicates the number of components computed by [boost_connected_components]. This
+introduces a new calling "profile" that would bypass the computation of the number of components.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,161 @@
+[/
+ / 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 DepthFirst Search]
+ template <class Graph, class P, class T, class R>
+ void
+ depth_first_search(Graph& g,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+ template <class Graph, class Visitor, class ColorMap>
+ void
+ depth_first_search(Graph& g,
+ Visitor vis,
+ ColorMap color,
+ typename graph_traits<Graph>::vertex_descriptor s)
+
+The `depth_first_search()` function performs a depthfirst traversal of the vertices
+in a directed graph. When possible, a depthfirst traversal chooses a vertex adjacent
+to the current vertex to visit next. If all adjacent vertices have already been
+discovered, or there are no adjacent vertices, then the algorithm backtracks to the
+last vertex that had undiscovered neighbors. Once all reachable vertices have been
+visited, the algorithm selects from any remaining undiscovered vertices and continues
+the traversal. The algorithm finishes when all vertices have been visited. Depthfirst
+search is useful for categorizing edges in a graph, and for imposing an ordering on the
+vertices. Section /DepthFirst Search/ describes the various properties of DFS and
+walks through an example.
+
+Similar to BFS, color markers are used to keep track of which vertices have been
+discovered. White marks vertices that have yet to be discovered, gray marks a
+vertex that is discovered but still has vertices adjacent to it that are undiscovered.
+A black vertex is discovered vertex that is not adjacent to any white vertices.
+
+The `depth_first_search()` function invokes userdefined actions at certain eventpoints
+within the algorithm. This provides a mechanism for adapting the generic DFS algorithm
+to the many situations in which it can be used. In the pseudocode below, the event
+points for DFS are indicated in by the triangles and labels on the right. The userdefined
+actions must be provided in the form of a visitor object, that is, an object whose type
+meets the requirements for a [BoostDFSVisitor]. In the pseudocode we show the algorithm
+computing predecessors /p/, discovery time /d/ and finish time /t/. By default, the
+`depth_first_search()` function does not compute these properties, however there are
+predefined visitors such as [boost_predecessor_recorder] and [boost_time_stamper] that
+can be used to do this.
+
+[pre
+DFS(G)
+ for each vertex u in V initialize vertex u
+ color\[u\] := WHITE
+ p\[u\] = u
+ end for
+
+ time := 0
+ if there is a starting vertex s
+ call DFSVISIT(G, s) start vertex /s/
+
+ for each vertex u in V
+ if color\[u\] = WHITE start vertex /u/
+ call DFSVISIT(G, u)
+ end for
+
+ return (p,d_time,f_time)
+
+DFSVISIT(G, u)
+ color\[u\] := GRAY discover vertex /u/
+ d_time\[u\] := time := time + 1
+
+ for each v in Adj\[u\] examine edge /(u,v)/
+ if (color\[v\] = WHITE) /(u,v)/ is a tree edge
+ p\[v\] = u
+ call DFSVISIT(G, v)
+ else if (color\[v\] = GRAY) /(u,v)/ is a back edge
+ ...
+ else if (color\[v\] = BLACK) /(u,v)/ is a cross or forward edge
+ ...
+ end for
+
+ color\[u\] := BLACK finish vertex /u/
+ f_time\[u\] := time := time + 1
+]
+
+[heading Where Defined]
+`boost/graph/depth_first_search.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`Graph& g`]
+ [
+ A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
+ and [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [in] [`vertex_descriptor s`]
+ [
+ This specifies the vertex that the depthfirst search should originate from. Note
+ that this can also be given as a named parameter.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`visitor(Visitor vis)`]
+ [
+ A visitor object that is inovked inside the algorithm at event points specified by the
+ [BoostDFSVisitor]. The `vis` object must be model the [BoostDFSVisitor] concept.
+
+ *Default* `bfs_visitor<null_visitor>`.
+ ]
+ ]
+ [
+ [in] [`root_vertex(vertex_descriptor s)`]
+ [
+ This specifies the vertex that the depthfirst search should originate from.
+
+ *Default* `*vertices(g).first`
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VeretxIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+]
+
+[heading Complexity]
+The time complexity is /O(E + V)/.
+
+[heading Example]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,779 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section Directed Graph]
+This section provides detailed information about the `directed_graph` class,
+its associated types, member functions and nonmember interface. A directed
+graph is one in which edges have distinct direction. Edges flow from a /source/
+vertex to a /target/ and are generally only traversed through the outgoing
+edges of a vertex. However, incoming edges are also accessible. The class
+provides a general purpose implementation of directed graphs and can be
+used with algorithms in the Boost Graph Library.
+
+[h4 Notation]
+The following notation is used in this documentation. The following type names
+are generally meant to mean the following:
+[table
+ [[Used Type] [Actual Type]]
+ [
+ [`directed_graph`]
+ [
+ `directed_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
+ arguments that correspond to userdefined or default verex properties,
+ edge properties, and graph properties.
+ ]
+ ]
+ [
+ [`vertex_descriptor`]
+ [`directed_graph<VP,EP,GP>::vertex_descriptor`]
+ ]
+ [
+ [`edge_descriptor`]
+ [`directed_graph<VP,EP,GP>::edge_descriptor`]
+ ]
+ [
+ [`vertex_iterator`]
+ [`directed_graph<VP,EP,GP>::vertex_iterator`]
+ ]
+ [
+ [`edge_iterator`]
+ [`directed_graph<VP,EP,GP>::edge_iterator`]
+ ]
+]
+
+Moreover, objects with the following names are generally expected to have the
+following types.
+
+[table
+ [[Object Name] [Type]]
+ [[`g`] [`directed_graph`]]
+ [[`u`, `v`] [`vertex_descriptor`]]
+ [[`e`] [`edge_descriptor`]]
+ [[`i`] [`vertex_iterator` or `edge_iterator`]]
+ [[`p`] [A property tag (usually a template parameter)]]
+ [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
+ [[`v`] [The value of a property (usually a template parameter)]]
+]
+
+[h4 Descriptor and Iterator Stability]
+With the `directed_graph` class, descriptors and iterators remain stable after
+all operations except descriptors and iterators to those edges or vertices being
+removed. Removing a vertex or edge will not invalidate descriptors or iterators
+referencing other vertices or edges.
+
+For example, consider the following code:
+
+ directed_graph<> g;
+ directed_graph<>::vertex_descriptor u = add_vertex(g);
+ directed_graph<>::vertex_descriptor v = add_vertex(g);
+ directed_graph<>::vertex_descriptor w = add_vertex(g);
+ remove_vertex(u);
+ add_edge(v, w, g);
+
+After running this program, the descriptor `u` will be invalid but `v` and `w` will
+still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
+property does not hold for all graph types.
+
+[h4 Vertex Indexing and Stability]
+The `directed_graph` class provides a builtin internal properties for vertex
+types, and will provide some degree of automated index management. Algorithms
+that use vertex indices generally assume that they are in the range
+\[0, `num_vertices(g)`). With the `directed_graph` class vertex indices will
+be in this continuous range until a vertex is removed from the graph. This is
+the only operation that invalidates vertex indices, but the vertices will need
+to be renumbered using the `renumber_vertex_indices()` function.
+
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
+[h4 Template Parameters]
+There are three parameters to the `directed_graph` class.
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`VertexProperties`]
+ [Specifies internal properties for vertices of the graph.]
+ [`no_property`]
+ ]
+ [
+ [`EdgeProperties`]
+ [Specifies internal properties for edges of the graph.]
+ [`no_property`]
+ ]
+ [
+ [`GraphProperties`]
+ [Specifies internal properties for the graph itself.]
+ [`no_property`]
+ ]
+]
+
+[h5 Model Of]
+[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
+[BoostMutableGraph], and [BoostPropertyGraph].
+
+[h5 Where Defined]
+`boost/graph/directed_graph.hpp`
+
+[h4 Associated Types]
+There are a number of useful types associated with the `directed_graph` class.
+Most of these are accessed through [boost_graph_traits] or other template classes.
+For convenience these types have been grouped by purpose.
+
+[h5 Descriptor Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<directed_graph>::vertex_descriptor`]
+ [
+ The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
+ models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_descriptor`]
+ [
+ The type for the edge descriptors associated with the graph. The `edge_descriptor`
+ models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ ]
+ ]
+]
+
+Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
+[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
+`std::tr1::unordered_map` respectively.
+
+[h5 Iterator Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<directed_graph>::vertex_iterator`]
+ [
+ The type for iterators returned by `vertices()`. Verex iterators are
+ models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_iterator`]
+ [
+ The type for iterators returned by `edges()`. Edge iterators are
+ models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::out_edge_iterator`]
+ [
+ The type for iterators returned by `out_edges()`. Outedge iterators
+ are models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::in_edge_iterator`]
+ [
+ The type for iterators returned by `in_edges()`. Inedge iterators
+ are models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::adjacency_iterator`]
+ [
+ The type for iterators returned by `adjacent_vertices`. Adjacency
+ iterators are models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+]
+
+[h5 Miscellaneous Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<directed_graph>::vertices_size_type`]
+ [The type used for dealing with the number of vertices in the graph.]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_size_type`]
+ [The type used for dealing with the number of edges in the graph.]
+ ]
+ [
+ [`graph_traits<directed_graph>::degree_size_type`]
+ [The type used for dealing with the number of edges incident to a vertex in the graph.]
+ ]
+ [
+ [`directed_graph::vertex_index_type`]
+ [The integral type representing vertex indices (generally `unsigned int`).]
+ ]
+ [
+ [
+ `property_map<directed_graph, Property>::type`
+
+ `property_map<directed_graph, Property>::const_type`
+ ]
+ [
+ The property map type for vertex or edge properties in the graph. The specific
+ property is specified by the `Property` template argument, and must match one of
+ the properties specified in the `VertexProperties` or `EdgeProperties` for the
+ graph.
+ ]
+ ]
+ [
+ [`graph_property<directed_graph, Property>::type`]
+ [
+ The value type for the graph property specified by the `Property` parameter.
+ `Property` must be one of the types in the `GraphProperties` template argument.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::directed_category`]
+ [
+ This is always `bidirectional_tag`, indicating that the graph supports in and
+ outedge operations.
+ ]
+ ]
+ [
+ [`graph_traits<directed_graph>::edge_parallel_category`]
+ [
+ This is always `allow_parallel_edges_tag`, indicating that multiple edges
+ may be added between two vertices (i.e., graphs can be /multigraphs/).
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+directed_graph(const GraphProperties& p = GraphProperties())
+``
+ ]
+ [The default constructor creates a graph with no vertices or edges.]
+ ]
+ [
+ [
+``directed_graph(const directed_graph& g)
+``
+ ]
+ [The copy constructor creates a copy of the given graph `g`.]
+ ]
+ [
+ [
+``
+directed_graph(vertices_size_type n,
+ const GraphProperties& p = GraphProperties())
+``
+ ]
+ [The default constructor creates a graph with `n` vertices and no edges.]
+ ]
+ [
+ [
+``directed_graph& operator =(const directed_graph& g)
+``
+ ]
+ [Copies the edges and vertices of the graph `g`.]
+ ]
+]
+
+[h4 Nonmember Functions]
+[h5 Nonmember Accessors]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+std::pair<vertex_iterator, vertex_iterator>
+vertices(const directed_graph& g)
+``
+ ]
+ [Returns an iterator range providing access to the vertex list of `g`.]
+ ]
+ [
+ [
+``
+std::pair<edge_iterator, edge_iterator>
+edges(const directed_graph& g)
+``
+ ]
+ [Returns an iterator range providing access to the edge list of `g`.]
+ ]
+ [
+ [
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+out_edges(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the outedges of
+ vertex `v` in the graph `g`.
+ ]
+ ]
+ [
+ [
+``
+std::pair<in_edge_iterator, in_edge_iterator>
+in_edges(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the inedges of
+ vertex `v` in the graph `g`.
+ ]
+ ]
+ [
+ [
+``
+std::pair<adjacency_iterator, adjacency_iterator>
+adjacent_vertices(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the adjacenct vertices
+ of vertex `v` in the graph `g`. Note that this is functionally
+ equivalent to iterating over the targets of all outedges of `v`.
+ ]
+ ]
+ [
+ [
+``
+vertices_size_type
+num_vertices(const directed_graph& g)
+``
+ ]
+ [Returns the number of vertices in the graph `g`.]
+ ]
+ [
+ [
+``
+edge_size_type
+num_edges(const directed_graph& g)
+``
+ ]
+ [Returns the number of edges the graph `g`.]
+ ]
+ [
+ [
+``
+degree_size_type
+degree(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the total degree of vertex `v` in the graph `g`. This is
+ functionally equivalent `out_degree(v,g) + in_degree(v,g)`.
+ ]
+ ]
+ [
+ [
+``
+degree_size_type
+out_degree(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the outdegree of vertex `v` in the graph `g`. In an
+ `directed_graph` this is equal to `in_degree(v, g)`.
+ ]
+ ]
+ [
+ [
+``
+degree_size_type
+in_degree(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the indegree of vertex `v` in the graph `g`. In an
+ `directed_graph` this is equal to `out_degree(v, g)`.
+ ]
+ ]
+ [
+ [
+``
+vertex_descriptor
+vertex(vertices_size_type n
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the /nth/ vertex in the graph `g`. With directed graphs,
+ this method is /O(n)/. As such its use with this type of graph is
+ discouraged.
+ ]
+ ]
+ [
+ [
+``
+std::pair<edge_descriptor, bool>
+edge(vertex_descriptor u,
+ vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ If the edge /(u,v)/ is in `g`, then this function returns the
+ descriptor for the edge connecting `u` and `v` with boolean value
+ set to `true`. Otherwise, the boolean value is `false` and the
+ edge descriptor is invalid.
+ ]
+ ]
+ [
+ [
+``
+vertex_size_type
+get_vertex_index(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the vertex index of the given vertex descriptor v. Note
+ that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+ This function is an alias for `get(vertex_index,g,v)`.
+ ]
+ ]
+ [
+ [
+``
+vertex_size_type
+max_vertex_index(vertex_descriptor v,
+ const directed_graph& g)
+``
+ ]
+ [
+ Returns the vertex index of the given vertex descriptor v. Note
+ that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+ This function is an alias for `get(vertex_index,g,v)`.
+ ]
+ ]
+]
+
+[h5 Nonmember Modifiers]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+vertex_descriptor
+add_vertex(directed_graph& g)
+``
+ ]
+ [Adds a vertex to `g` and returns a descriptors for the new vertex.]
+ ]
+ [
+ [
+``
+void
+clear_vertex(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all in and outedges of `v`, but leaves `v` in the graph `g`.
+ This is functioanlly equivalent to invoking `remove_edge()` on all
+ in or outedges of `v`, invalidating descriptors and iterators that
+ reference edges incident to `v`.
+ ]
+ ]
+ [
+ [
+``
+void
+clear_out_edges(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all outedges from vertex `v`, but does not remove the vertex
+ itself. This is functionally equivalent to calling `remove_edge()` for
+ all outedges of `v`, invalidating any descriptors and iterators that
+ reference edges incident to that vertex.
+ ]
+ ]
+ [
+ [
+``
+void
+clear_in_edges(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all inedges from vertex `v`, but does not remove the vertex
+ itself. This is functionally equivalent to calling `remove_edge()` for
+ all inedges of `v`, invalidating any descriptors and iterators that
+ reference edges incident to that vertex.
+ ]
+ ]
+ [
+ [
+``
+vertex_descriptor
+remove_vertex(vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes vertex `v` from the graph `g`. It is assumed that `v` has no
+ incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
+ before removing it.
+
+ Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
+ before calling this method, this operation will invalidate all vertex indices
+ in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
+ be renumbered using the `renumber_vertex_indices(g)` method. If possible,
+ prefer to remove groups of vertices at one time before renumbering since
+ renumbering is a /O(n)/ time operation.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_vertex_and_renumber_indices(vertex_iterator i,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes the vertex indicated by the iterator `i` from the graph `g`. Like
+ the `remove_vertex(v,g)` function, it is expected that `*i` have no
+ incident edges at the time of removal.
+
+ As indicated by the name, this method will also renumber vertex indices
+ after the removal of `*i`. This operation iterates over vertices after
+ `i`, decrementing their index by 1. If your program removes several
+ vertices at once, prefer to call several `remove_vertex(v,g)` methods,
+ followed by `renumber_vertices(g)` before using `g` in an algorithm.
+ ]
+ ]
+ [
+ [
+``
+void
+renumber_vertex_indices(directed_graph& g)
+``
+ ]
+ [
+ Renumbers all interior vertex indices such that each vertex has an index
+ in the range \[0, `num_vertices(g)`). Generally, this function needs to
+ be called after removing vertices and before invoking different graph
+ algorithms.
+ ]
+ ]
+ [
+ [
+``
+std::pair<edge_descriptor, bool>
+add_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
+ edge. For `directed_graph`s, the boolean value of the pair will always
+ be true.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes the edge /(u,v)/from the graph. This operation invalidates any
+ descriptors or iterators referencing the edge. Note that `u` and `v` must
+ be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
+ (with multiple edges between /(u,v)/, this mehtod will cause the removal of
+ all such edges connecting `u` and `v`.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(edge_descriptor e,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes the edge `e` from the graph. If multuple edges exist from
+ /(`source(e,g)`, `target(e,g)`)/, then this method will remove only
+ the single, specified edge.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(out_edge_iterator i,
+ directed_graph& g)
+``
+ ]
+ [
+ This is functionally equivalent to `remove_edge(*i, g)`.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge_if(Predicate p,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all edges from the graph that satisfy `predicate`. That is, if
+ `p()` returns true when applied to an edge, then that edge is removed.
+ The affect on descriptor and iterator is the same as that of invoking
+ `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+ [
+ [
+``
+template <class Predicate>
+void
+remove_out_edge_if(vertex_descriptor v,
+ Predicate p,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all edges outedges from vertex`v` that satisfy `predicate`.
+ That is, if `p()` returns true when applied to an edge, then that edge
+ is removed. The affect on descriptor and iterator is the same as that
+ of invoking `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+ [
+ [
+``
+template <class Predicate>
+void
+remove_in_edge_if(vertex_descriptor v,
+ Predicate p,
+ directed_graph& g)
+``
+ ]
+ [
+ Removes all edges inedges from vertex`v` that satisfy `predicate`.
+ That is, if `p()` returns true when applied to an edge, then that edge
+ is removed. The affect on descriptor and iterator is the same as that
+ of invoking `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+]
+
+[h5 Proprety Map Acessors]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class Property>
+property_map<directed_graph, Property>::type
+get(Property, directed_graph& g)
+``
+
+``
+template <class Property>
+property_map<directed_graph, Property>::const_type
+get(Property, const directed_graph& g)
+``
+ ]
+ [
+ Returns the property map object for the vertex property specified by the
+ type `Property`. This type must match one of the properties specified in
+ the `VertexProperties` template argument.
+ ]
+ ]
+ [
+ [
+``
+template <class Property, class Descriptor>
+typename
+ property_traits<
+ property_map<directed_graph, Property>::const_type
+ >::value_type
+get(Property,
+ const directed_graph& g,
+ Descriptor d)
+``
+ ]
+ [
+ Returns the property value specified by the type `Property` for either
+ the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
+ ]
+ ]
+ [
+ [
+``
+template <class Property, class Descriptor, class Value>
+void
+put(Property,
+ const directed_graph& g,
+ Descriptor d,
+ Value v)
+``
+ ]
+ [
+ Sets the property value denoted by the type `Property` for either edge
+ or vertex descriptor `d` to the given value `v`.
+ ]
+ ]
+ [
+ [
+``
+template <class GraphProprety>
+typename graph_property<directed_graph, GraphProperty>::type&
+get_property(directed_graph& g, GraphProperty)
+``
+
+``
+template <class GraphProprety>
+const typename graph_property<directed_graph, GraphProperty>::type&
+get_property(const directed_graph& g, GraphProperty)
+``
+ ]
+ [
+ Returns the graph property specified by the type `GraphProperty` for
+ the graph `g`.
+ ]
+ ]
+ [
+ [
+``
+template <class GraphProprety, class Value>
+void
+set_property(const directed_graph& g, GraphProperty, Value v)
+``
+ ]
+ [
+ Sets the graph proeprty specified by the type `GraphProperty` to
+ the given value `v`. Note that `GraphProperty` must be one of
+ the properties in the `GraphProperties` template argument.
+ ]
+ ]
+]
+
+[h4 Rationale]
+Unlike most graph classes in Boost.Graph, the `directed_graph` does not model the
+[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+difficult from a usability standpoint to easily deduce the type to be passed as a
+property when adding vertices and edges  but especially vertices.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,12 @@
+[/
+ / 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 Measures of Distances]
+
+
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk 20070719 09:59:20 EDT (Thu, 19 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 NonMember 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/reference/distributions.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,175 @@
+[/
+ / 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 Degree Distributions]
+ void degree_distribution(
+ _graph,
+ _distribution = not_given(),
+ _out_distribution = not_given(),
+ _in_distribution = not_given())
+
+ void degree_histogram(
+ _graph,
+ _histogram = not_given(),
+ _out_histogram = not_given(),
+ _in_histogram = not_given())
+
+The degree distribution function compute distributions of the degrees
+of vertices in a graph. A distribution is mapping of an observable property
+to the number of occurences of that property. In this context, the observable
+property is the degree of a vertex (or in and outdegree), which are in
+the range \[0, /max{degree(v)}/\] Where /max{degree(v)}/ is the maximum degree
+of any vertex in a graph /G/. Therefore, the output distribution is mapping
+of vertex degree to its number of occurences in a graph.
+
+This histogram functions are closely related to the degree distribution functions.
+However, instead of computing a mapping from vertex degree to the number of
+vertices, the histogram maps vertex degree to the /set of vertices/ that exhibit
+that degree. This is very useful if you want to quickly find all vertices with
+degree 0, or find the vertex with the highest degree.
+
+In both of these functions, the computation of distribution or histogram
+depends on which optional parameters are passed to the function. If called as:
+
+ degree_distribution(g, _distribution = dist, _in_distribution = in_dist);
+
+The algorithm will compute both the degree destribution and indegree distributions.
+Note that for undirected graphs, all three distributions or histograms will be
+identical.
+
+[h5 Where Defined]
+`boost/graph/degree_distribution.hpp`
+
+[h5 Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`_graph`]
+ [
+ The graph object for which the distribution will be computed. If
+ the `_distribution` or `_in_distribution` arguments are supplied
+ when calling this function then `_graph` must be a model of
+ [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+ then `_graph` must be a model of [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [optional, out]
+ [
+ `_distribution`
+
+ `_out_distribution`
+
+ `_in_distribution`
+ ]
+ [
+ The distribution parameters maps instances of vertex degree to the
+ number of observed vertices in the graph with that degree.
+
+ These parameters must model both the [SgiSequence] and
+ [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
+ distribution must be the same as `degree_size_type`. The `value_type` must
+ be integral (preferably unsigned).
+
+ If not supplied, these parameters assume the default value of `not_given`,
+ implying that no computation is performed.
+ ]
+ ]
+ [
+ [optional, out]
+ [
+ `_histogram`
+
+ `_out_histogram`
+
+ `_in_histogram`
+ ]
+ [
+ The distribution parameters maps instances of vertex degree to the
+ number of observed vertices in the graph with that degree.
+
+ The histogram output parameter must be a model of both [SgiSequence]
+ and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
+ distribution must be the same as `degree_size_type`. Additionally `value_type`
+ must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).
+
+ If not supplied, these parameters assume the default value of `not_given`,
+ implying that no computation is performed.
+ ]
+ ]
+]
+
+[h5 Return Value]
+Both functions return `void`.
+
+[h5 Complexity]
+The time complexity of all these functions is /O(V)/.
+
+The space complexity for the distributions functisons is /O(max{degree(v)})/ where
+/max{degree(v)}/ is the maxmimum degree of all vertices in a graph /G/.
+
+The space complexity for the histogram functions is /O(V + max{degree(v)})/.
+
+[h5 Notes]
+Because a graph may be a multigraph, there is no determinable upper bound on the
+size of the distribution or histogram parameters. As such they are required to
+be dynamically resized during the execution of the algorithm.
+
+The recommended type for the distribution parameters is:
+
+ std::vector<graph_traits<graph_type>::degree_size_type>
+
+where `graph_type` is the type of the `_graph` parameter. This satisfies the type
+requirements of the algorithms, and provides exceptional performance at the cost
+of extra memory overhead.
+
+The recommended type for the histogram parameters is:
+
+ std::vector<std::vector<graph_traits<graph_type>::vertex_descriptor> >
+
+Although this will consume more memory (due to the overhead of vector resizing),
+it may perform better than using `std::list` to store vertices of the same degree.
+This is because the `std::list::size()` function is not required to return in
+constant time.
+
+Note that if `dist` is the name of the output distribution after a call to
+`degree_distribution()` then the maximum degree is `dist.size()  1`. The
+minimum degree corresponds to the index in `dist` with the first nonzero value.
+
+[h5 Examples]
+The first example show how to compute and print the degree distribution.
+
+ undirected_graph<> g;
+ // add vertices and edges to g
+
+ std::vector<size_t> dist;
+ degree_distribution(g, dist);
+ copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
+
+The following example shows how to access the vertex (or vertices) with the maximum
+degree by using the `degree_histogram()` algorithm. This prints the index of that
+vertex.
+
+ undirected_graph<> g;
+ // add vertice and edges to g
+
+ typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
+ typedef std::vector<vertex_type> vertex_vector;
+
+ std::vector<vertex_vector> hist;
+ degree_histogram(g, hist);
+ cout << get_vertex_index(hist.back().back()) << "\n";
+
+[h5 Rationale]
+The use of these functions varies somewhat from typical use of named parameters
+where default values are simply used to supply default information. Here, they
+are used to control functionality. It should also be noted that if no parameters
+are supplied, this algorithm still runs in linear time. However, there is no
+additional overhead for not supplying a parameter because operations on the
+`not_given` type are noopped (they are instantiated as empty functions).
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/edge_list.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/edge_list.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,10 @@
+[/
+ / 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 Edge List]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk 20070719 09:59:20 EDT (Thu, 19 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 breadthfirst 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 depthfirst 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 NonMember 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/reference/property_writer.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk 20070719 09:59:20 EDT (Thu, 19 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 eventpoint 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 NonMember 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]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,68 @@
+[/
+ / 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 Reference Guide]
+
+[section Graph Types]
+[include undirected_graph.qbk]
+[include directed_graph.qbk]
+[include adjacency_list.qbk]
+[include edge_list.qbk]
+[endsect]
+
+[section Traits Classes]
+[endsect]
+
+[section Event Visitor List Adaptors]
+[include bfs_visitor.qbk]
+[include dfs_visitor.qbk]
+[include dijkstra_visitor.qbk]
+[include bellman_visitor.qbk]
+[include astar_visitor.qbk]
+[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]
+[include depth_first_search.qbk]
+[endsect]
+
+[section Shortest Path Algorithms]
+[endsect]
+
+[section Minimum Spanning Tree Algorithms]
+[endsect]
+
+[section Connectivity Algorithms]
+[include connected_components.qbk]
+[include strong_components.qbk]
+[include connectivity.qbk]
+[endsect]
+
+[section Maximum Flow Algorithms]
+[endsect]
+
+[section Sparse Matrix Ordering Algorithms]
+[endsect]
+
+[section Layout Algorithms]
+[endsect]
+
+[section Graph Measures]
+[include distributions.qbk]
+[include distance.qbk]
+[endsect]
+[endsect]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/strong_components.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/strong_components.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,116 @@
+[/
+ / 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 Strongly Connected Components]
+
+ template <class Graph, class ComponentMap, class P, class T, class R>
+ typename property_traits<ComponentMap>::value_type
+ strong_components(const Graph &g, ComponentMap c,
+ const bgl_named_params<P,T,R>& params = ``/defaults/``);
+
+The `strong_components()` functions compute the strongly connected components of a
+directed graph using Tarjan's algorithm based on DFS \[41\].
+
+The output of the algorithm is recorded in the component property map, which will
+contain numbers giving the component number assigned to each vertex. This algorithm
+returns the number of strongly connected components in the graph.
+
+[heading Where Defined]
+`boost/graph/strong_components.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`const Graph& g`]
+ [
+ The /directed/ graph for which connected components are being found.
+ This graph must be a model of VertexListGraph and Incidence Graph.
+ ]
+ ]
+ [
+ [out] [`ComponentMap c`]
+ [
+ The algorithm computes how many connected components are in the graph,
+ and assigning each component an integer label. The algorithm then records
+ which component each vertex in the graph belongs to by recording the
+ component number in the component property map. The ComponentMap type
+ must be a model of WritablePropertyMap. The value type shouch be an
+ integer type, preferably the same as the `vertices_size_type` of the
+ graph. The key type must be the graph's `vertex_descriptor` type.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [util] [`root_map(RootMap root_map)`]
+ [
+ This is used by the algorithm to record the candidate root vertex for each
+ vertex. By the end of the algorithm, there is a single root vertex for each
+ component and `get(root_map, v)` returns the root vertex for whichever
+ component vertex `v` is a member. The `RootMap` must be a ReadWritePropertyMap,
+ where the key type and the value type are the vertex descriptor type of the
+ graph.
+
+ *Default* An iterator_property_map created from a `std::vector` of
+ `vertex_descriptor`s of size `num_vertices(g)` and using the `index_map`
+ for accessing root vertices.
+ ]
+ ]
+ [
+ [util] [`discover_time_map(TimeMap time_map)`]
+ [
+ This is used by the algorithm to keep track of the DFS ordering of the vertices.
+ The `TimeMap` must be a model of ReadWritePropertyMap and its value type must
+ be an integer type. The key type must be the vertex descriptor type of the graph.
+
+ *Default* An iterator_property_map created from a `std::vector` of integers
+ of size `num_vertices(g)` and using the `index_map` for accessing root vertices.
+ ]
+ ]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VertexIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+]
+
+[heading Complexity]
+This algorithm runs in /O(V + E)/.
+
+[heading Notes]
+This algorithm will not compile if passed a /directed/ graph.
+
+[heading Examples]
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk 20070719 09:59:20 EDT (Thu, 19 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 eventpoint
+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 NonMember 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]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,743 @@
+[/
+ / 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 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 nonmember interface. An undirected graph
+is one in which edges have no direction  this is to say that edges can be "traveled"
+in both directions. This class provides general purpose implementation of undirected
+graphs and can be used with algorithms in the Boost Graph Library.
+
+[h4 Notation]
+The following notation is used in this documentation. The following type names
+are generally meant to mean the following:
+
+[table
+ [[Used Type] [Actual Type]]
+ [
+ [`undirected_graph`]
+ [
+ `undirected_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
+ arguments that correspond to userdefined or default verex properties,
+ edge properties, and graph properties.
+ ]
+ ]
+ [
+ [`vertex_descriptor`]
+ [`undirected_graph<VP,EP,GP>::vertex_descriptor`]
+ ]
+ [
+ [`edge_descriptor`]
+ [`undirected_graph<VP,EP,GP>::edge_descriptor`]
+ ]
+ [
+ [`vertex_iterator`]
+ [`undirected_graph<VP,EP,GP>::vertex_iterator`]
+ ]
+ [
+ [`edge_iterator`]
+ [`undirected_graph<VP,EP,GP>::edge_iterator`]
+ ]
+]
+
+Moreover, objects with the following names are generally expected to have the
+following types.
+
+[table
+ [[Object Name] [Type]]
+ [[`g`] [`undirected_graph`]]
+ [[`u`, `v`] [`vertex_descriptor`]]
+ [[`e`] [`edge_descriptor`]]
+ [[`i`] [`vertex_iterator` or `edge_iterator`]]
+ [[`p`] [A property tag (usually a template parameter)]]
+ [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
+ [[`v`] [The value of a property (usually a template parameter)]]
+]
+
+[h4 Descriptor and Iterator Stability]
+With the `undirected_graph` class, descriptors and iterators remain stable after
+all operations except descriptors and iterators referencing the vertices and edges
+that have been removed. Removing a vertex or edge will not invalidate descriptors
+and iterators to other vertices or edges.
+
+For example, consider the following code:
+
+ undirected_graph<> g;
+ undirected_graph<>::vertex_descriptor u = add_vertex(g);
+ undirected_graph<>::vertex_descriptor v = add_vertex(g);
+ undirected_graph<>::vertex_descriptor w = add_vertex(g);
+ remove_vertex(u);
+ add_edge(v, w, g);
+
+After running this program, the descriptor `u` will be invalid but `v` and `w` will
+still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
+property does not hold for all graph types.
+
+[h4 Vertex Indexing and Stability]
+The `undirected_graph` class provides a builtin internal properties for vertex
+types, and will provide semiautomated index management. Algorithms that use vertex
+indices generally assume that they are in the range \[0, `num_vertices(g)`). With
+the `undirected_graph` class vertex indices will be in this continuous range until
+a vertex is removed from the graph. This is the only operation that invalidates
+vertex indices, but the vertices will need to be renumbered using the
+`renumber_vertex_indices(g)` function.
+
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
+[h4 Function Names for Directed and Undirected Graphs]
+Many of the operations in the Boost Graph library are named in accordance
+with the concepts of directed graphs, specifically the use of outedges as the
+canonical adjacencty list for vertices. As a result, undirected graphs also
+use the outedge terminology to refern to its incident edges, but inedge operations
+are identical in behavior to outedge operations.
+
+There are three sets of operations that have multiple names and duplicate behaviors:
+`*degree()`computing functions, `*_edge()`iterating accessors, and the `remove_*_edge()`
+predicatebased functions. These functions are grouped together in their reference
+sections.
+
+This class also introduces two new functions, `incident_edges(g)` that returns an
+iterator range to the incident edges of `g`, and `remove_incident_edges_if(v,p,g)`.
+These are identical in behavior to their `in` and `out` counterparts. These
+functions are only provided for semantic consistency so developers should be aware
+that these new functions are /not/ defined for any other graph classes in the
+Boost Graph Library.
+
+Developers of generic algoriths should be aware that, when generalizing an algorithm
+for both directed and undirected graphs, it is better to use the `out_degree(g)`
+function to access outedges 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
+ [[Parameter] [Description] [Default]]
+ [
+ [`VertexProperties`]
+ [Specifies internal properties for vertices of the graph.]
+ [`no_property`]
+ ]
+ [
+ [`EdgeProperties`]
+ [Specifies internal properties for edges of the graph.]
+ [`no_property`]
+ ]
+ [
+ [`GraphProperties`]
+ [Specifies internal properties for the graph itself.]
+ [`no_property`]
+ ]
+]
+
+Additionally, the `undirected_graph` class provides a nonconstant time implementation
+of the [BoostAdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
+the concept.
+
+[h4 Where Defined]
+`boost/graph/undirected_graph.hpp`
+
+[h4 Associated Types]
+There are a number of useful types associated with the `undirected_graph` class.
+Most of these are accessed through `graph_traits` or other template classes.
+For convenience these types have been grouped by purpose.
+
+[h5 Descriptor Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<undirected_graph>::vertex_descriptor`]
+ [
+ The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
+ models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::edge_descriptor`]
+ [
+ The type for the edge descriptors associated with the graph. The `edge_descriptor`
+ models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+ ]
+ ]
+]
+
+Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
+[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
+`std::tr1::unordered_map` respectively.
+
+[h5 Iterator Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<undirected_graph>::vertex_iterator`]
+ [
+ The type for iterators returned by `vertices()`. Verex iterators are
+ models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::edge_iterator`]
+ [
+ The type for iterators returned by `edges()`. Edge iterators are
+ models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::out_edge_iterator`]
+ [
+ The type for iterators returned by `out_edges()`. Outedge iterators
+ are models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::in_edge_iterator`]
+ [
+ The type for iterators returned by `in_edges()`. Inedge iterators
+ are models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::adjacency_iterator`]
+ [
+ The type for iterators returned by `adjacent_vertices`. Adjacency
+ iterators are models of the [SgiBidirectionalIterator] concept.
+ ]
+ ]
+]
+
+[h5 Miscellaneous Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<undirected_graph>::vertices_size_type`]
+ [The type used for dealing with the number of vertices in the graph.]
+ ]
+ [
+ [`graph_traits<undirected_graph>::edge_size_type`]
+ [The type used for dealing with the number of edges in the graph.]
+ ]
+ [
+ [`graph_traits<undirected_graph>::degree_size_type`]
+ [The type used for dealing with the number of edges incident to a vertex in the graph.]
+ ]
+ [
+ [`undirected_graph::vertex_index_type`]
+ [The integral type representing vertex indices (generally `unsigned int`).]
+ ]
+ [
+ [
+ `property_map<undirected_graph, Property>::type`
+
+ `property_map<undirected_graph, Property>::const_type`
+ ]
+ [
+ The property map type for vertex or edge properties in the graph. The specific
+ property is specified by the `Property` template argument, and must match one of
+ the properties specified in the `VertexProperties` or `EdgeProperties` for the
+ graph.
+ ]
+ ]
+ [
+ [`graph_property<undirected_graph, Property>::type`]
+ [
+ The value type for the graph property specified by the `Property` parameter.
+ `Property` must be one of the types in the `GraphProperties` template argument.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::directed_category`]
+ [
+ This is always `undirectedS`, indicating that the graph supports operations
+ for undirected graphs.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::edge_parallel_category`]
+ [
+ This is always `allow_parallel_edges_tag`, indicating that multiple edges
+ may be added between two vertices (i.e., graphs can be /multigraphs/).
+ ]
+ ]
+]
+
+[h4 Member Functions]
+[table
+ [[Function] [Description]]
+ [
+ [`undirected_graph(const GraphProperties& p = GraphProperties()`]
+ [The default constructor creates a graph with no vertices or edges.]
+ ]
+ [
+ [`undirected_graph(const undirected_graph& x`)]
+ [The copy constructor creates a copy of the given graph `x`.]
+ ]
+ [
+ [
+``
+undirected_graph(vertices_size_type n,
+ const GraphProperties& p = GraphProperties())
+``
+ ]
+ [The default constructor creates a graph with `n` vertices and no edges.]
+ ]
+ [
+ [`undirected_graph& operator =(const undirected_graph& x)`]
+ [Copies the edges and vertices of the graph `x`.]
+ ]
+]
+
+[h4 Nonmember Functions]
+[h5 Nonmember Accessors]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+std::pair<vertex_iterator, vertex_iterator>
+vertices(const undirected_graph& g)
+``
+ ]
+ [Returns an iterator range providing access to the vertex list of `g`.]
+ ]
+ [
+ [
+``
+std::pair<edge_iterator, edge_iterator>
+edges(const undirected_graph& g)
+``
+ ]
+ [Returns an iterator range providing access to the edge list of `g`.]
+ ]
+ [
+ [
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+incident_edges(vertex_descriptor v, const undirected_graph& g)
+``
+
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+out_edges(vertex_descriptor v, const undirected_graph& g)
+``
+
+``
+std::pair<in_edge_iterator, in_edge_iterator>
+in_edges(vertex_descriptor v, const undirected_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the incident edges
+ of the vertex `v`. Because `g` is an undirected graph, these three
+ functions are guaranteed to return identical iterator ranges.
+ ]
+ ]
+ [
+ [
+``
+std::pair<adjacency_iterator, adjacency_iterator>
+adjacent_vertices(vertex_descriptor v,
+ const undirected_graph& g)
+``
+ ]
+ [
+ Returns an iterator range providing access to the adjacenct vertices
+ of vertex `v` in the graph `g`. Note that this is functionally
+ equivalent to iterating over the targets of all incident edges of `v`.
+ ]
+ ]
+ [
+ [
+``
+vertices_size_type
+num_vertices(const undirected_graph& g)
+``
+ ]
+ [Returns the number of vertices in the graph `g`.]
+ ]
+ [
+ [
+``
+edge_size_type
+num_edges(const undirected_graph& g)
+``
+ ]
+ [Returns the number of edges the graph `g`.]
+ ]
+ [
+ [
+``
+degree_size_type
+degree(vertex_descriptor v,
+ const undirected_graph& g)
+``
+
+``
+degree_size_type
+out_degree(vertex_descriptor v,
+ const undirected_graph& g)
+``
+
+``
+degree_size_type
+in_degree(vertex_descriptor v,
+ const undirected_graph& g)
+``
+ ]
+ [
+ Returns the degree of the vertex `v`, which is the number of
+ edges incident to it. Because `g` is undirected, all three
+ functions return equal values.
+ ]
+ ]
+ [
+ [
+``
+vertex_descriptor
+vertex(vertices_size_type n
+ const undirected_graph& g)
+``
+ ]
+ [
+ Returns the /nth/ vertex in the graph `g`. With undirected graphs,
+ this method is /O(n)/. As such its use with this type of graph is
+ discouraged.
+ ]
+ ]
+ [
+ [
+``
+std::pair<edge_descriptor, bool>
+edge(vertex_descriptor u,
+ vertex_descriptor v,
+ const undirected_graph& g)
+``
+ ]
+ [
+ If the edge (`u`,`v`) is in `g`, then this function returns the
+ descriptor for the edge connecting `u` and `v` with boolean value
+ set to `true`. Otherwise, the boolean value is `false` and the
+ edge descriptor is invalid.
+ ]
+ ]
+ [
+ [
+``
+vertex_size_type
+get_vertex_index(vertex_descriptor v,
+ const undirected_graph& g)
+``
+ ]
+ [
+ Returns the vertex index of the given vertex descriptor v. Note
+ that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+ This function is an alias for `get(vertex_index,g,v)`.
+ ]
+ ]
+ [
+ [
+``
+vertex_size_type
+max_vertex_index(vertex_descriptor v,
+ const undirected_graph& g)
+``
+ ]
+ [
+ Returns the vertex index of the given vertex descriptor v. Note
+ that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+ This function is an alias for `get(vertex_index,g,v)`.
+ ]
+ ]
+]
+
+[h5 Nonmember Modifiers]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+vertex_descriptor
+add_vertex(undirected_graph& g)
+``
+ ]
+ [Adds a vertex to `g` and returns a descriptors for the new vertex.]
+ ]
+ [
+ [
+``
+void
+clear_vertex(vertex_descriptor v,
+ undirected_graph& g)
+``
+ ]
+ [
+ Removes all in and outedges of `v`, but leaves `v` in the graph `g`.
+ This is functioanlly equivalent to invoking `remove_edge()` on all
+ in or outedges of `v`, potentially invalidating descriptors and
+ iterators.
+ ]
+ ]
+ [
+ [
+``
+vertex_descriptor
+remove_vertex(vertex_descriptor v,
+ undirected_graph& g)
+``
+ ]
+ [
+ Removes vertex `v` from the graph `g`. It is assumed that `v` has no
+ incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
+ before removing it.
+
+ Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
+ before calling this method, this operation will invalidate all vertex indices
+ in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
+ be renumbered using the `renumber_vertex_indices(g)` method. If possible,
+ prefer to remove groups of vertices at one time before renumbering since
+ renumbering is a /O(n)/ time operation.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_vertex_and_renumber_indices(vertex_iterator i,
+ undirected_graph& g)
+``
+ ]
+ [
+ Removes the vertex indicated by the iterator `i` from the graph `g`. Like
+ the `remove_vertex(v,g)` function, it is expected that `*i` have no
+ incident edges at the time of removal.
+
+ As indicated by the name, this method will also renumber vertex indices
+ after the removal of `*i`. This operation iterates over vertices after
+ `i`, decrementing their index by 1. If your program removes several
+ vertices at once, prefer to call several `remove_vertex(v,g)` methods,
+ followed by `renumber_vertices(g)` before using `g` in an algorithm.
+ ]
+ ]
+ [
+ [
+``
+void
+renumber_vertex_indices(undirected_graph& g)
+``
+ ]
+ [
+ Renumbers all interior vertex indices such that each vertex has an index
+ in the range \[0, `num_vertices(g)`). Generally, this function needs to
+ be called after removing vertices and before invoking graph algorithms.
+ ]
+ ]
+ [
+ [
+``
+std::pair<edge_descriptor, bool>
+add_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ undirected_graph& g)
+``
+ ]
+ [
+ Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
+ edge. For `undirected_graph`s, the boolean value of the pair will always
+ be true.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ undirected_graph& g)
+``
+ ]
+ [
+ Removes the edge /(u,v)/ from the graph. This operation invalidates any
+ descriptors or iterators referencing the edge. Note that `u` and `v` must
+ be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
+ (with multiple edges between /(u,v)/, this mehtod will cause the removal of
+ all such edges connecting `u` and `v`.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(edge_descriptor e,
+ undirected_graph& g)
+``
+ ]
+ [
+ Removes the edge `e` from the graph. If multuple edges exist from
+ (`source(e,g)`, `target(e,g)`), then this method will remove only
+ the single, specified edge.
+ ]
+ ]
+ [
+ [
+``
+void
+remove_edge(out_edge_iterator i,
+ undirected_graph& g)
+``
+ ]
+ [
+ This is functionally equivalent to `remove_edge(*i, g)`.
+ ]
+ ]
+ [
+ [
+``
+template <class Predicate> void
+remove_edge_if(Predicate p, undirected_graph& g)
+``
+ ]
+ [
+ Removes all edges from the graph that satisfy `predicate`. That is, if
+ `p()` returns true when applied to an edge, then that edge is removed.
+ The affect on descriptor and iterator is the same as that of invoking
+ `remove_edge()` for on each of the removed vertices.
+ ]
+ ]
+ [
+ [
+``
+template <class Predicate> void
+remove_incident_edge_if(vertex_descriptor v, Predicate p
+ undirected_graph& g)
+``
+
+``
+template <class Predicate> void
+remove_out_edge_if(vertex_descriptor v, Predicate p,
+ undirected_graph& g)
+``
+
+``
+template <class Predicate> void
+remove_in_edge_if(vertex_descriptor v, Predicate p,
+ undirected_graph& g)
+``
+ ]
+ [
+ Removes all edges incidentedges from vertex`v` that satisfy `predicate`.
+ That is, if `p()` returns true when applied to an edge, then that edge
+ is removed. The affect on descriptor and iterator is the same as that
+ of invoking `remove_edge()` for on each of the removed vertices.
+
+ Because this graph is undirected, these three funtions are identical
+ in behavior and run time.
+ ]
+ ]
+]
+
+[h5 Proprety Map Acessors]
+[table
+ [[Function] [Description]]
+ [
+ [
+``
+template <class Property>
+property_map<undirected_graph, Property>::type
+get(Property,
+ const undirected_graph& g)
+``
+ ]
+ [
+ Returns the property map object for the vertex property specified by the
+ type `Property`. This type must match one of the properties specified in
+ the `VertexProperties` template argument.
+ ]
+ ]
+ [
+ [
+``
+template <class Property, class Descriptor>
+typename
+ property_traits<
+ property_map<undirected_graph, Property>::const_type
+ >::value_type
+get(Property,
+ const undirected_graph& g,
+ Descriptor d)
+``
+ ]
+ [
+ Returns the property value specified by the type `Property` for either
+ the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
+ ]
+ ]
+ [
+ [
+``
+template <class Property, class Descriptor, class Value>
+void
+put(Property,
+ const undirected_graph& g,
+ Descriptor d,
+ Value v)
+``
+ ]
+ [
+ Sets the property value denoted by the type `Property` for either edge
+ or vertex descriptor `d` to the given value `v`.
+ ]
+ ]
+ [
+ [
+``
+template <class GraphProperty>
+typename graph_property<undirected_graph, GraphProperty>::type&
+get_property(undirected_graph& g, GraphProperty)
+``
+
+``
+template <class GraphProperty>
+const typename graph_property<undirected_graph, GraphProperty>::type&
+get_property(const undirected_graph& g, GraphProperty)
+``
+ ]
+ [
+ Returns the graph property specified by the type `GraphProperty` for
+ the graph `g`. Here, GraphProperty must be one of the properties
+ in the `GraphProperties` template argument.
+ ]
+ ]
+ [
+ [
+``
+template <class GraphProprety, class Value>
+void
+set_property(const undirected_graph& g, GraphProperty, Value v)
+``
+ ]
+ [
+ Sets the graph proeprty specified by the type `GraphProperty` to
+ the given value `v`. Note that `GraphProperty` must be one of
+ the properties in the `GraphProperties` template argument.
+ ]
+ ]
+]
+
+[h4 Rationale]
+Unlike most graph classes in Boost.Graph, the `undirected_graph` does not model the
+[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+difficult (from a usability standpoint) to easily deduce the type to be passed as a
+property when adding vertices and edges  but especially vertices.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk 20070719 09:59:20 EDT (Thu, 19 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 SGIdefined
+ / 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]]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/theory.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/theory.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,252 @@
+[/
+ / 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 webpages 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 selfloop. 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 outedge of vertex u and an inedge 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 outedge
+of b and an inedge of y. In Figure 2, y is adjacent to b and viceversa. The edge (y,b) is incident on
+vertices y and b.
+
+In a directed graph, the number of outedges of a vertex is its outdegree and the number of inedges is
+its indegree. For an undirected graph, the number of edges incident to a vertex is its degree. In Figure 1,
+vertex b has an outdegree of 3 and an indegree 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 adjacencymatrix representation is usually the best choice, whereas for sparse graphs
+the adjacencylist representation is a better choice. Also the edgelist representation is a space efficient
+choice for sparse graphs that is appropriate in some situations.
+
+[h3 Adjacency Matrix Representation]
+An adjacencymatrix representation of a graph is a 2dimensional 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 adjacencymatrix 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 adjacencymatrix data structure.
+
+[$../images/review_adjacency_matrix.gif]
+
+[h3 Adjacency List Representation]
+An adjacencylist representation of a graph stores an outedge sequence for each vertex. For sparse
+graphs this saves space since only O(V + E) memory is required. In addition, the outedges 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
+outedges for any vertex in the graph). Figure 4 depicts an adjacencylist representation of the
+graph in Figure 1. The adjacency_list class is an implementation of the adjacencylist representation.
+
+[$../images/review_adjacency_list.gif]
+
+[h3 Edge List Representation]
+An edgelist 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 edgelist representation of the
+graph in Figure 1. The edge_list adaptor class can be used to create implementations of the edgelist
+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 compressedsparserow 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 nontree 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 BreadthFirst Search]
+Breadthfirst 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 breadthfirst 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 DepthFirst Search]
+A depthfirst 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 asyet 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 depthfirst trees which together
+form the depthfirst forest. A depthfirst search categorizes the edges in the graph into three categories:
+treeedges, backedges, and forward or crossedges (it does not specify which). There are typically many
+valid depthfirst forests for a given graph, and therefore many different (and equally valid) ways to
+categorize the edges.
+
+One interesting property of depthfirst search is that the discover and finish times for each vertex form
+a parenthesis structure. If we use an openparenthesis when a vertex is discovered, and a closeparenthesis
+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 minimumspanningtree (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 ShortestPaths 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,...,k1 are in the edge set E).
+In the shortestpath problem, each edge is given a realvalued weight. We can therefore talk about the weight
+of a path
+
+/w(p)/ = sum from /i=1..k/ of /w(vi1,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 singlepair problem, but there
+is also the singlesource problem (all shortest paths from one vertex to every other vertex in the graph),
+the equivalent singledestination problem, and the allpairs problem. It turns out that there are no
+algorithms for solving the singlepair problem that are asymptotically faster than algorithms that solve
+the singlesource problem.
+
+A shortestpaths 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 singlesource algorithm is a shortestpaths 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 pushrelabel algorithm of Goldberg which is based on the notion of a preflow introduced by
+Karzanov.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/tour.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/tour.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,508 @@
+[/
+ / 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 outedges of the vertex. The edges
+{(0,1),(0,2),(0,3),(0,4)} are all outedges of vertex 0. The edges entering a vertex are called
+the inedges of the vertex. The edges {(0,4),(2,4),(3,4)} are all inedges 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 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<>` 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
+outedges 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 inedges. The other options for the third argument are `directedS` which selects a directed
+graph with only outedges, 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' inedges, outedges, 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 STLinteroperability 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., pointerlinked graphs). This difference is hidden underneath the "blackbox"
+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 OutEdges, InEdges, and Edge Descriptors]
+The outedges 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 outedges of a vertex (similar to how the vertices() function returned a pair of
+iterators). The iterators are called outedge 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 sourcetarget pairs for each outedge 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 << "outedges: ";
+ 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
+ outedges: (0,1) (0,2) (0,3) (0,4)
+]
+
+The `in_edges()` function of the BidirectionalGraph interface provides access to all the inedges
+of a vertex through inedge 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 << "inedges: ";
+ 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
+ inedges: (2,0) (3,0) (4,0)
+]
+
+[h3 Adjacent Vertices]
+Given the outedges 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 plugin
+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/dijkstraexample.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 shortestpaths 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 welldefined 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 shortestpaths 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
+shortestpaths 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
Added: sandbox/SOC/2007/graphs/libs/graph/doc/tutorial.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/tutorial.qbk 20070719 09:59:20 EDT (Thu, 19 Jul 2007)
@@ 0,0 +1,17 @@
+[/
+ / 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 Tutorial]
+
+This section contains a tutorial for the Boost.Graph library. It builds on the
+quick tour but discusses the concepts in much greater detail.
+
+[include tut_properties.qbk]
+
+[include tut_adjacency_list.qbk]
+
+[endsect]
\ No newline at end of file
BoostCommit 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