
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070625 13:32:43
Author: asutton
Date: 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
New Revision: 7140
URL: http://svn.boost.org/trac/boost/changeset/7140
Log:
Moved some of the metadocumentation (users, pubs, etc). to the intro.
Wrote some pretty signficant chunks of the reference docs for undirected,
directed graphs.
Rewrote the undirected graph tutorial for new changes (still need to do
the directed tutorial).
Started adding the concept documentation back in.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_visitors.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/acknowledgements.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/publications.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/users.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2  82 ++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk  51 +
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk  31 
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk  8
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk  237 ++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk  57 +++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk  8
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk  714 ++++++++++++++++++++++++++++++++++++++
9 files changed, 935 insertions(+), 255 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 1,13 +1,79 @@
import quickbook ;
+# 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)
xml graph
 : graph.qbk
 ;
+using quickbook ;
+
+xml graph : graph.qbk ;
boostbook standalone
 : graph
 ;
+ :
+ 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"
+ ;
+
+
+
+
+
+
+
+
+
+
install html : ../../../../doc/html/boostbook.css ;
install ../ : ../../../../boost.png ;
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/acknowledgements.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/acknowledgements.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ 1,36 +0,0 @@
[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section 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]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 0,0 +1,35 @@
+[/
+ / 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 reusability of the algorithm.
+
+Figure 1: The graph concepts and refinement relationships.
+
+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.
+
+[h3 Undirected Graphs]
+
+Lots of stuff here on undirected graphs...
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_visitors.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_visitors.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 0,0 +1,26 @@
+[/
+ / 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]
+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:
+
+* BFS Visitor
+* DFS Visitor
+* Dijkstra Visitor
+* Bellman Ford Visitor
+* A* Visitor
+* Event Visitor
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 0,0 +1,15 @@
+[/
+ / 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.
+
+[include con_graphs.qbk]
+[include con_visitors.qbk]
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 1,4 +1,4 @@
 [/
+[/
/ Copyright (c) 2007 Andrew Sutton
/
/ Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ 6,45 +6,36 @@
/]
[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])
 ]
+ [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])
+ ]
]
[/ Images ]
[def __note__ [$images/note.png]]
[def __alert__ [$images/caution.png]]
[def __detail__ [$images/note.png]]
[def __tip__ [$images/tip.png]]

[/ Contents ]
[include introduction.qbk]
[include history.qbk]
[include users.qbk]

[include publications.qbk]

[include acknowledgements.qbk]
+[/ [include theory.qbk] /]
[include theory.qbk]

[include tour.qbk]
+[/ [include tour.qbk] /]
[include guide.qbk]
[include rationale.qbk]
+[include concepts.qbk]
+
+[include reference.qbk]
+[/ [include bibliography.qbk] /]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 6,42 +6,11 @@
/]
[section User's Guide]
In order to help ease your transition to working with Boost Graph, the library
provides two general purpose graph classes: `undirected_graph` and `directed_graph`.
These two classes are simply abstractions over the much more configurable, but
somewhat obstruse `adjacency_list` class. It may be important to note that these
classes are designed to be applicable to as many problems as possible, and may
perform poorly in some circumstances. See the section
[link boost_graph.user_s_guide.optimizing_for_performance Optimizing for Performance]
for details on why you would want to and how to accomplish it.

Note that these examples all use /bundled properties/  a mechanism for defining
properties for graphs, vertices, and edges. Unfortunately, these may not work
correctly on compilers that do not support partial template specialization. If you
are trying to build these examples see the section on /bundled properties/ for
translating to oldstyle properties.

The following sections provide users guides and details for working with both
the `undirected_graph` and `directed_graph`, the much more general `adjacency_list`
and `adjacency_matrix` classes, the truth about properties and property maps,
tips and tricks for optimizing, and notes on implementing new Boost.Graph
algorithms.
[include guide_undirected.qbk]
[include guide_directed.qbk]
[include guide_details.qbk]

[include guide_adjacency_list.qbk]
[h2 Optimizing for Performance]
One of the unfortunate problems of providing general purpose classes is that they often
fail to scale up to larger problems. Consider the Six Degrees of Kevin Bacon game. What
happens if you want to play on, say the entire contents of the
[@http://www.imdb.com Internet Movie Database (IMDb)]?
Will the `undirected_graph` class be capable of building the data structure and running
the search algorithms in reasonable time? Probably not. This section is a guide on migrating
from a "canned" graph to a customized solution.

[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 5,7 +5,7 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
[section The `adjacency_list` Class]
+[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
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 34,16 +34,16 @@
implement the examples described in this user's guide. Their dependencies are
shown in figure 1. Path names have been omitted for readability.
[$../images/files.png]
+[$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
+* 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
+* 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.
@@ 196,7 +196,7 @@
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/reverse.png]
+[$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
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 6,10 +6,6 @@
/]
[section Undirected Graphs]
This section could be called "Things to do with Undirected Graphs" since its goal
is to provide a number of concrete examples of how undirected graphs can be used
to solve problems  and more specifically how to implement them using Boost.Graph.

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.
@@ 26,24 +22,23 @@
and yes, Kevin Bacon is actually in /Animal House/ (he plays a snotty Omega pledge
in his film debut).
[$../images/movie.png]
+[$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?). What can we do
+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
+* 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
+* 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" and was actually discussed (on air) by its inventors on MTV's "The Jon
Stewart Show" (go figure).
+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).
@@ 57,6 +52,10 @@
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]
@@ 99,7 +98,6 @@
struct Actor
{
 int index;
int distance;
std::string name;
};
@@ 109,27 +107,24 @@
std::string name;
};
In this example, we are "internalizing" a number of properties for each vertex.
Here, `Actor::index` represents the index of the vertex within the graph. Unfortunately,
the graph class is not smart enough to automatically assign and maintain these indices
(for a number of reasons), so we're going to have to manage this later. Likewise, the
`Actor::distance` property records the distance from each actor to Kevin Bacon. This is
the value that we will be computing for every actor in the data set. The `Actor::name`
and `Movie::name` properties should be fairly selfexplanatory.
+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
+/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::type, int Actor::*>::type ActorIndexMap;
 typedef boost::property_map<Graph::type, int Actor::*>::type ActorDistanceMap;
+ typedef boost::property_map<Graph, int Actor::*>::type ActorDistanceMap;
The first template argument `Graph::type` defines the type of the structure that
+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 member variables
of type `int`.
+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
@@ 151,6 +146,7 @@
#include <boost/tokenizer.hpp>
+ // the very important actortovertex mapping
typedef std::map<std::string, Vertex> ActorMap;
using namespace std;
@@ 199,12 +195,12 @@
if(inserted) {
// if the vertex was inserted into the map, we need to
 // create a new vertex in the graph
+ // 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].index = num_vertices(graph)  1;
g[v].name = name;
}
else {
@@ 241,15 +237,6 @@
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.
[warning
Vertex indices (as used in this example) are entirely unstable if vertices are removed
from the graph. Many graph algorithms require vertex index maps with values in the range
\[0, `num_vertices(g)`)/. If we were to remove the first vertex in this example, the
vertex indices would be incorrect and the program would potentially crash (accessing
beyond `num_vertices(g)`). It is relatively trivial and inexpensive (O(`num_vertices(g)`)
to renumber vertices just before running algorithms that require vertex index maps.
]

Our main program looks like this:
int main()
@@ 264,90 +251,59 @@
[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. To do this, we're going
to need some help in the form of a BFS visitor.

 template <typename DistanceMap>
 struct ActorDistanceRecorder : public bfs_visitor<>
 {
 ActorDistanceRecorder(DistanceMap d)
 : distances(d)
 {}

 template <typename Edge, typename Graph>
 void tree_edge(Edge e, const Graph& g) const
 {
 typedef typename Graph::vertex_descriptor Vertex;
 Vertex
 u = source(e, g),
 v = target(e, g);
 distances[v] = distances[u] + 1;
 }

 DistanceMap distances;
 };

This visitor overloads the `tree_edge()` member function in order to compute the distance
from a central vertex. In this example, the distance of a vertex from a starting vertex
is one plus the depth of its parent in the spanning tree generated by a BFS.

We're also going to provide a simple little helper function so we don't have to
explicitly instantiate the visitor when we use it with the BFS algorithm.

 template <typename DistanceMap>
 ActorDistanceRecorder<DistanceMap> record_actor_distances(DistanceMap d)
 {
 return ActorDistanceRecorder<DistanceMap>(d);
 }

This leaves the question: what is a DistanceMap? To answer that, we have to complete the
solution to the Kevin Bacon problem. Back to the `main()`...
+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()
{
 // ...continue from above...

 ActorIndexMap indices = get(&Actor::index, graph);
 ActorDistanceMap distances = get(&Actor::distance, graph);
+ // ...continued from above...
 // find kevin (our starting point) and zero out his distancetoself
+ // 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,
 vertex_index_map(indices).
 visitor(record_actor_distances(distances)));
+ visitor(
+ make_bfs_visitor(record_distances(distances, on_tree_edge()))
+ )
+ );
// ...to be continued...
 }
Finally, we're using the property maps that we defined so far above. The `get()` function
essentially returns a maplike object that allows us to read and/or write the specified vertex
or edge property. As mentioned earlier, these maps allow algorithms to reand and write both
internal and external properties in a uniform method. Because graph algorithms cannot guess
whether properties are internal or external, we have to pass these maps to just about every
algorithm in this manner.
+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.
We actually use the actors' distance map as it is in the distance recorder above (mostly as
an example). We could just as easily have written the distance assignment as:
+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())))
+ );
with the same effect.

Finally, we can run our BFS and assign "Kevin Bacon numbers" to our actors. This is done
by calling the `breadth_first_search()` function passing the graph, the starting vertex
and some named parameters. The first named parameter is the vertex index map which provides
read access to the `Actor::index` property assigned during graph construction. The second
is an instance of our distancerecording visitor (as returned by our helper function).

After finishing, each vertices distance property will be assigned. All there is left to do
+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";
@@ 401,39 +357,6 @@
// ...
typedef boost::property_map<Graph::type, &Vertex Actor::*>::type ActorParentMap;
We are also going to change the BFS visitor that we used in the previous example.

 template <typename ParentMap>
 struct ActorParentRecorder : public bfs_visitor<>
 {
 ActorParentRecorder(ParentMap d)
 : parents(d)
 {}

 template <typename Edge, typename Graph>
 void tree_edge(Edge e, const Graph& g) const
 {
 typedef typename Graph::vertex_descriptor Vertex;
 Vertex
 u = source(e, g),
 v = target(e, g);
 parents[v] = u;
 }

 ParentMap parents;
 };

 template <typename ParentMap>
 ActorParentRecorder<ParentMap> record_actor_parents(ParentMap d)
 {
 return ActorParentRecorder<ParentMap>(d);
 }

Despite the fact that this code is essentially cut, paste, and replace from the code
above, there is one interesting change. Instead of assigning a distance to a vertex,
we are setting the parent of the target to be the source. This one line allows us
to walk the shortest paths from any actor to Kevin Bacon.

The only other changes are going to be in the `main()` program.
int main(int argc, char *argv[])
@@ 476,16 +399,19 @@
return 1;
}
 ActorIndexMap = get(&Actor::index, graph);
 ActorParentMap = get(&Actor::parent, graph);
+ // get the parents map for later use.
+ ActorParentMap parents = get(&Actor::parent, g);
 breadth_first_search(graph, u,
 vertex_index_map(indices).
 visitor(record_actor_parents(parents)));
+ 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:
+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)
{
@@ 497,10 +423,13 @@
return v;
}
Otherwise, the code is essentially the same as above. In this case, we're passing our
modified parentrecording visitor to the `breadth_first_search()` function. The step
in the solution is to backtrack from the target actor to the parent, printing the
movies that form the chain of costarring actors.
+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(...)
{
@@ 510,28 +439,24 @@
string from = g[v].name;
string to = g[p].name;
+ // find the edge so we can print the movie
Edge e;
 Graph::out_edge_iterator i, j;
 for(tie(i, j) = out_edges(v, g); i != j; ++i) {
 if(target(*i, g) == p) {
 e = *i;
 break;
 }
 }
+ bool found;
+ tie(e, found) = edge(v, p, g);
string movie = g[e].name;
cout << from << " starred with " << to << " in '" << movie << "'\n";
v = p;
}
 }
The only "complicated" part of the backtracking is finding the edge from
the child to the parent. Because `undirected_graph` does is not a model of an
`adjacency_matrix`, there is no simple method that returns edge data given
two vertices.
+ return 0;
+ }
[note This problem can be simplified using the `graph_as_matrix` adapter.]
+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
@@ 541,7 +466,7 @@
Elisabeth Shue starred with Kevin Bacon in 'Hollow Man (2000)'
]
You now have a completely unbeatable implementation of the "Six Degrees of Kevin
+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.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 155,7 +155,60 @@
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.
+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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/publications.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/publications.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ 1,17 +0,0 @@
[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section Who's Writing about Me Now?]

* 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

[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 1,4 +1,4 @@
 [/
+[/
/ Copyright (c) 2007 Andrew Sutton
/
/ Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ 108,4 +108,10 @@
needs finergrained control he or she can easily use the remove_edge(e, g) function
where /e/ is an edge descriptor.
+[h3 Propertybased Add Functions]
+The `\[un\]directed_graph` classes no longer provide `add` functionst that take
+a property as an argument. These tend not to work so well with bundled properties 
+especially when we're introducing a hidden property in the undirected_graph
+class. It makes type determination really difficult.
+
[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 0,0 +1,400 @@
+[/
+ / 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 Reference]
+
+[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` && [br] Directed = `directedS`]
+ [OEL = `vecS`]
+ ]
+ [
+ [
+ `remove_edge()`[br]
+ `remove_edge_if()`[br]
+ `remove_out_edge_if()`[br]
+ `remove_in_edge_if()`[br]
+ `clear_vertex()`
+ ]
+ [Valid]
+ [Valid]
+ [Valid]
+ [OEL = `vecS` && [br] 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` [br]
+ `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
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
@@ 1,4 +1,4 @@
 [/
+[/
/ Copyright (c) 2007 Andrew Sutton
/
/ Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ 6,42 +6,712 @@
/]
[section Undirected Graph Reference]
+This section provides detailed information about the `undirected_graph` class,
+its associated types, member functions and nonmember interface.
*TODO*: I should probably document somewhere that out_edges() and in_edges()
are equivalent for this function. Is it important? I don't know, maybe.
+[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 Duplicitous Operations]
+Many of the original operations in the Boost Graph library are named in accordance
+with the terminology for 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.
[h3 Members]
The following tables define and describe the members of the `undirected_graph`
class.
+There are three sets of operations that have multiple names and duplicate behavior:
+`*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.
+
+[h4 Vertex and Edge Storage]
+The `undirected` graph class has three distinct storage compontents: one for each
+of vertices, edges, and incidentedges per vertex. Each of these storage components
+uses a `std::list`. This is important to remember when considering the performance
+of oeprations on these graphs.
+
+Note that mutating (modifying) edge operations on a graph must operate on both
+the edge list and incident edge lists. For example, adding an edge to the graph
+will insert the edge or descriptors into both the edge list and the incidence
+edge list of the edge's source and target.
+
+It is important to note that the use of the term /incident edges/ in this context
+generally refers to the /out/edges of a vertex. Because the graph is undirected,
+every inedge is also an outedge, and so we use the term /incident/ to capture
+these semantics. As a result, the `out_edges(g)`, `in_edges(g)` and `incident_edges(g)`
+functions all return identical iterator ranges.
+
+[h4 Descriptor and Iterator Stability]
+With the `undirected_graph` class, descriptors and iterators remain stable after
+most operations. This is to say that removing a vertex or edge will not invalidate
+descriptors and iterators to other vertices or edges.
+
+[h4 Vertex Indexing and Stability]
+The `undirected_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 `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()` function.
+
+[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`]
+ ]
+]
+
+[h5 Model Of]
+VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
+
+[h5 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
 [[Member] [Where Defined] [Description]]
+ [[Type] [Description]]
[
 [`vertex_descriptor`]
 [Graph]
 [An opaque type whose values are used to access vertices and their properties.]
+ [`graph_traits<undirected_graph>::vertex_descriptor`]
+ [
+ The type for the vertex descriptors associated with the graph.
+ ]
]
[
 [`edge_descriptor`]
 [Graph]
 [An opaque type whose values are used to access edges and their properties.]
+ [`graph_traits<undirected_graph>::edge_descriptor`]
+ [
+ The type for the edge descriptors associated with the graph.
+ ]
+ ]
+]
+
+[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 `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::edge_iterator`]
+ [
+ The type for iterators returned by `edges()`. Edge iterators are
+ models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::out_edge_iterator`]
+ [
+ The type for iterators returned by `out_edges()`. Outedge iterators
+ are models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::in_edge_iterator`]
+ [
+ The type for iterators returned by `in_edges()`. Inedge iterators
+ are models of the `BidirectionalIterator` concept.
+ ]
+ ]
+ [
+ [`graph_traits<undirected_graph>::adjacency_iterator`]
+ [
+ The type for iterators returned by `adjacent_vertices`. Adjacency
+ iterators are models of the `BidirectionalIterator` 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.
+ ]
]
[
 [`directed_category`]
 [Graph]
 [Indicates the graph has undirected edges. It's type is `undirected_tag`.]
+ [
+``
+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`.
+ ]
]
[
 [`edge_parallel_category`]
 [Graph]
 [...]
+ [
+``
+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 different 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.
+ ]
]
[
 [`traversal_category`]
 [Graph]
 [...]
+ [
+``
+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.
+ ]
]
]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 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 Reference Guide]
+
+[include ref_undirected_graph.qbk]
+[include ref_directed_graph.qbk]
+[include ref_adjacency_list.qbk]
+
+[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/users.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/users.qbk 20070625 13:32:41 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ 1,27 +0,0 @@
[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section Who's Using Me Now?]

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]

[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