
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070627 08:23:16
Author: asutton
Date: 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
New Revision: 7192
URL: http://svn.boost.org/trac/boost/changeset/7192
Log:
Massive filesystem change... Put guide components into separate
directories for "convenience" also as per doc structure suggestions.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_graphs.qbk
 copied unchanged from r7186, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/concepts.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide_adjacency_list.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide_directed.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide_undirected.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_adjacency_list.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_connected_components.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_connectivity.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_directed_graph.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_distributions.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_strong_components.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_undirected_graph.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk
 copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_details.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,110 +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 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.

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.

[table
 [[Expression] [Return Type or Description]]
 [[*Graph*]]
 [[`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.]]
 [[*Incidence Graph* refines Graph]]
 [[`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`]]
 [[*BidirectionalGraph* refines IncidenceGraph]]
 [[`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`]]
 [[*AdjacencyGraph* refines Graph]]
 [[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
 [[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
 [[*VertexListGraph* refines IncidenceGraph and AdjacencyGraph]]
 [[`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`]]
 [[*EdgeListGraph* refines Graph]]
 [[`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`]]
 [[*AdjacencyMatrix* refines Graph]]
 [[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
 [[*MutableGraph* refines Graph]]
 [[`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`]]
 [[*MutablePropertyGraph* refines Graph]]
 [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
 [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
 [[*PropertyGraph* refines Graph]]
 [[`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`.]]
]

[*TODO]

There are some functions missing like `get_property()` and `put/set_property()`.
These occur in some documentation somewhere but are in no means pervasive, complete
or accurate.

It should also be worth pointing out that we can redefine the entire concept hierarchy
based on a) vertex or edge operations, b) directed/undirected or c) simple or multigraphs.
Basically, there are some interesting ways to conceptualize the Boost.Graph interface.

[h3 Undirected Graphs]

Lots of stuff here on undirected graphs...

[endsect]
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,34 +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 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 Graph (or refinement)]]
 [[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]]
 [[p] [An object of type Property]]
 [[Predicate] [A function that, given an argument, returns true or false]]
 [[pred] [An object of type Predicate]]
]

[include con_graphs.qbk]
[include con_visitors.qbk]

[endsect]
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,16 +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 User's Guide]

[include guide_undirected.qbk]

[include guide_directed.qbk]

[include guide_adjacency_list.qbk]

[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,480 +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 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_details.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_details.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,143 +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 More About Simple Graphs]
The `directed_graph` and `undirected_graph` classes  the socalled "simple graph
classes" are not parts of the original Boost.Graph Libray. In fact, they are some
of the most recent additions, designed to provide a lower entry barrier to graph
programming with Boost. As such, they leverage much of the existing Boost.Graph
infrastructure for their implementaiton.This section provides details on design
and structure of these classes.

Both simple graph classes provides three template parameters that can be used
to customize the internal properties of vertices, edges, and the graph itself.
They are described in Table 1.

[table
 [[Parameter] [Description] [Default]]
 [
 [VertexProperties]
 [Specifies internal properties of each vertex.]
 [`no_property`]
 ]
 [
 [EdgeProperties]
 [Specifies internal properties of each edge.]
 [`no_property`]
 ]
 [
 [GraphProperties]
 [Specifies global, internal properties for the graph.]
 [`no_property`]
 ]
]

The previous examples have all been shown using /bundled properties/  an approach
to specifying internal properties that allows the user to use member variables
of common structures in property maps. However, this is not the only means of
specifying properties. If your compiler does not support partial template
specialization, then you cannot use bundled properties in your program. See the
page on [link boost_graph.old_style_properties oldStyle properties] for details.

One of the most important features of both of these classes is that they are
implemented entirely in terms of an underlying `adjacency_list`. While, it may
not be commonplace to disclose implementation details in a user's guide, I find
that it is actually important in this case. Because the `adjacency_list` was
designed as the "Swiss army knife" of graph classes, it is very customizable
and there are some significant tradeoffs in graph behavior depending on the
arguments supplied.

The `adjacency_list` class traditionally provides seven template parameters.
These are described in Table 2 along with the arguments supplied by the
`directed_graph` and `undirected_graph` classes.

[table
 [[Parameter] [Description] [Default]]
 [
 [OutEdgeList]
 [Storage component for the outedges of each vertex.]
 [`listS`]
 ]
 [
 [VertexList]
 [Storage component for vertices of the graph.]
 [`listS`]
 ]
 [
 [Directed]
 [
 Whether the graph is undirected, directed (outedges only), or
 bidirectional (out and inedges).
 ]
 [`undirectedS` or `bidirectionalS`]
 ]
 [
 [VertexProperties]
 [See Table 1.]
 [As template argument]
 ]
 [
 [VertexProperties]
 [See Table 1.]
 [As template argument]
 ]
 [
 [VertexProperties]
 [See Table 1.]
 [As template argument]
 ]
 [
 [EdgeList]
 [Storage component for the edges of the graph.]
 [`listS`]
 ]
]

With both classes, the storage components are assigned as defaults and
cannot be changed. The directionality of edges is also specified as
a nonchangeable parameter. It should be fairly obvious that the `undirected_graph`
class uses the `undirectedS` selector while the `directed_graph` class uses
`directedS`. The internal properties of the graph are assigned from the template
parameters of the simple graph classes themselves. If omitted, these all default
to `no_property`.

This set of template arguments was chosen to provide maximum flexibility for
solving different sets of problems. However, there may be cases where these
classes do not meet your needs or perform poorly under certain situations.
In this case, we suggest using `adjacency_list` directly. See the section
[link boost_graph.user_s_guide.more_about_simple_graphs.customizing_graphs on
customizing your graph] for more details.

[h4 Stability and Validity]
As you can see, all of the storage components for these graph classes are
selected with `listS`. Using list storage provides a number of benefits over
the more traditional vector storage, specifically in terms of iterator and
descriptor stability for mutable graphs. Generally speaking stablity refers
to the continuing validity of iterators and descriptors after changes to
the graph such as adding or removing vertices and edges. With some storage
components (e.g., `vecS`), iterators and descriptors can become invalide after
some operations. However `listS` guarantees stability after most operations.
A more complete description of containers, stability and their tradeoffs
can be found [link boost_graph.adjacency_list.stability here].

[h4 Customizing Graphs]
Although the `undirected_graph` and `directed_graph` classes are designed
along the "onesize fits most" principle, there can be times when these
classes do not meet your performance requirements. For example, your problem
may not require the extra memory overhead of bidirectional edges, which over
a million edges or so tends to add up. Or maybe you're adding a million
vertices to a graph and the repeated insertions to a list cause your
computer to page a lot  potentially a performance nightmare. In these cases,
you may need to consider customizing your graph by using an `adjacency_list`
and tweaking some of the default storage components.

Consider the first example of the costar graphs. Suppose we have 200,000
actors and three million edges in our data file.
Migrating this example
to an `adjacency_list` is nearly trivial since

[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,371 +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 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,473 +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 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,400 +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 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` && [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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,95 +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 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,28 +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 Connectivity Measures]

Reference for connectivity measures. Apparently, these are just going to be
simple wrappers around connected_components or strong_components to provide
some extra information. These might include:

* `is_connected()`, `is_strongly_connected()`
* `largest_connected_component()`, `largest_strong_component()`

We might extend these for biconnected components also. Essentially, these
functions take the component map computed by the connectivity stuff as
an input and produce results. If the connectivity map isn't provided,
we could compute it on the fly.

[Examples]

``
 connected_comp
``

[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,756 +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 Directed Graph]
This section provides detailed information about the `directed_graph` class,
its associated types, member functions and nonmember interface.

[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 Vertex and Edge Storage]
The `directed` graph class has four distinct storage compontents: one for each
of vertices, edges, outedges per vertex, and inedges 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 three
different lists. For example, adding an edge to the graph will insert the edge
or descriptors into the edge list, the outedge list of the source vertex, and
the inedge list of the target vertex. These lists are accessible via the
`edges(g)`, `out_edges(v,g)`, and `in_edges(v,g)` respectively.

[h4 Descriptor and Iterator Stability]
With the `directed_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 except for the edge or
vertex that was actually removed.

[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.

[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]
VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.

[h5 Where Defined]
`boost/graph/directed_graph.hpp`

[h4 Associated Types]
There are a number of useful types associated with the `directed_graph` class.
Most of these are accessed through `graph_traits` or other template classes.
For convenience these types have been grouped by purpose.

[h5 Descriptor Types]
[table
 [[Type] [Description]]
 [
 [`graph_traits<directed_graph>::vertex_descriptor`]
 [
 The type for the vertex descriptors associated with the graph.
 ]
 ]
 [
 [`graph_traits<directed_graph>::edge_descriptor`]
 [
 The type for the edge descriptors associated with the graph.
 ]
 ]
]

[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 `BidirectionalIterator` concept.
 ]
 ]
 [
 [`graph_traits<directed_graph>::edge_iterator`]
 [
 The type for iterators returned by `edges()`. Edge iterators are
 models of the `BidirectionalIterator` concept.
 ]
 ]
 [
 [`graph_traits<directed_graph>::out_edge_iterator`]
 [
 The type for iterators returned by `out_edges()`. Outedge iterators
 are models of the `BidirectionalIterator` concept.
 ]
 ]
 [
 [`graph_traits<directed_graph>::in_edge_iterator`]
 [
 The type for iterators returned by `in_edges()`. Inedge iterators
 are models of the `BidirectionalIterator` concept.
 ]
 ]
 [
 [`graph_traits<directed_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<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.
 ]
 ]
]

[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,128 +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 Degree Distributions]
 template <class Graph, class DistributionMap>
 void degree_distribution(const Graph &g, DistributionMap& dist);

 template <class Graph, class DistributionMap>
 void in_degree_distribution(const Graph &g, DistributionMap& dist);

 template <class Graph, class DistributionMap>
 void out_degree_distribution(const Graph &g, DistributionMap& dist);


 template <class Graph, class HistogramMap>
 void degree_histogram(const Graph &g, HistogramMap& dist);

 template <class Graph, class HistogramMap>
 void in_degree_histogram(const Graph &g, HistogramMap& dist);

 template <class Graph, class HistogramMap>
 void out_degree_histogram(const Graph &g, HistogramMap& dist);

The degree distribution functions compute statistical distributions of the degrees
of vertices in a graph. In addition to the degree distribution, different algorithms
allow for the computation indegree and outdegree distributions.

The histogramming functions compute historgrams, associating each vertex in
the graph with its degree in the distribution.

[heading Where Defined]
`boost/graph/degree_distribution.hpp`

[heading Parameters]
[table
 [[Type] [Parameter] [Description]]
 [
 [in] [`const Graph& g`]
 [
 The graph object for which the distribution will be computed. For
 `degree_distributions()` and `in_degree_distribution()`, `g` must
 be a model of a BidirectionalGraph. For `out_degree_distribution()`,
 `g`, must model the IncidenceGraph concept.
 ]
 ]
 [
 [out] [`DistributionMap& dist`]
 [
 The distribution parameter maps instances of degrees (numerically)
 to the number of vertices in the graph that exhibit that degree.

 The distribution output parameter has a number of strict typ requirements.
 First, it must be a model of the Sequence concept, specifically providing
 a `resize()` member function. They key (or index) type of this parameter
 should be the same as `degree_size_type` of the graph. Finally, the
 `value_type` of this method should be an integer type (preferrably
 unsigned). It is recommended to use `std::vector<degree_size_type>` for
 this parameter.
 ]
 ]
 [
 [out] [`HistogramMap& hist`]
 [
 The histogram parameter maps instances of degrees (numerically) to the
 set of vertices that exhibit that degree.

 The histogram parameter has fairly stringent type requirements due to
 its structure. First, the parameter must model the Sequence concept,
 providing a `resize()` member function. Seocnd, the key (index) of
 the type should be the same as `degree_size_type` of the graph. The
 `value_type` of this is required to model the BackInsertionSequence,
 and the `value_type` of that /must/ be the same as the `vertex_descriptor`
 of the graph parameter.
 ]
 ]
]

[heading Complexity]
The complexity of this function is /O(V)/.

[heading 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.

For the distribution parameter, we recommend `std::vector<size_t>`. This satisfies
all the requirements. For the histogram, we recommend using a `std::vector<Sequence<Vertex> >`
where `Sequence` is one of `std::list`, `std::vector`, `std::deque`, or `std::queue`. The
choice doesn't make much difference except that a `std::list` will require more allocations,
but a `std::vector` will require more space. The `Vertex` type must be
`graph_traits<Graph>::vertex_descriptor`.

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.

[heading Examples]
The first example show how to compute and print the degree distribution. Each
element in the returned distribution corresponds to the number of instances
of

 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::list<vertex_type> vertex_list;

 std::vector<vertex_list> hist;
 degree_histogram(g, hist);
 cout << get_vertex_index(hist.back().back()) << "\n";

[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,116 +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 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,718 +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 Undirected Graph]
This section provides detailed information about the `undirected_graph` class,
its associated types, member functions and nonmember interface.

[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.

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
 [[Type] [Description]]
 [
 [`graph_traits<undirected_graph>::vertex_descriptor`]
 [
 The type for the vertex descriptors associated with the graph.
 ]
 ]
 [
 [`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.
 ]
 ]
 [
 [
``
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 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.
 ]
 ]
 [
 [
``
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.
 ]
 ]
]

[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk 20070627 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ 1,46 +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 Reference Guide]

[section Graph Types]
[include ref_undirected_graph.qbk]
[include ref_directed_graph.qbk]
[include ref_adjacency_list.qbk]
[endsect]

[section Algorithms]
[section Core Algorithms]
[endsect]

[section Shortest Path Algorithms]
[endsect]

[section Minimum Spanning Tree Algorithms]
[endsect]

[section Connectivity Algorithms]
[include ref_connected_components.qbk]
[include ref_strong_components.qbk]
[include ref_connectivity.qbk]
[endsect]

[section Maximum Flow Algorithms]
[endsect]

[section Sparse Matrix Ordering Algorithms]
[endsect]

[section Layout Algorithms]
[endsect]

[section Graph Measures]
[include ref_distributions.qbk]
[endsect]
[endsect]

[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