
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070611 12:55:13
Author: asutton
Date: 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
New Revision: 4525
URL: http://svn.boost.org/trac/boost/changeset/4525
Log:
Started refactoring documentation into a user's guide, hopefully with
the intent of replacing most of the older Boost.Graph documentation.
Added a fairly lengthy walkthru of undirected graphs.
Added:
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_directed.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tut_adjacency_list.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk  4 +++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tour.qbk  2 +
2 files changed, 4 insertions(+), 2 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
@@ 44,5 +44,7 @@
[include tour.qbk]
[include tutorial.qbk]
+[include guide.qbk]
+
+
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
@@ 0,0 +1,45 @@
+[/
+ / 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]
+In order to help ease your transition to working with Boost Graph, the library
+provides two general purpose graph classes: `undirected_graph` and `directed_graph`.
+These two classes are simply abstractions over the much more configurable, but
+somewhat obstruse `adjacency_list` class. It may be important to note that these
+classes are designed to be applicable to as many problems as possible, and may
+perform poorly in some circumstances. See the section
+[link boost_graph.user_s_guide.optimizing_for_performance Optimizing for Performance]
+for details on why you would want to and how to accomplish it.
+
+Note that these examples all use /bundled properties/  a mechanism for defining
+properties for graphs, vertices, and edges. Unfortunately, these may not work
+correctly on compilers that do not support partial template specialization. If you
+are trying to build these examples see the section on /bundled properties/ for
+translating to oldstyle properties.
+
+The following sections provide users guides and details for working with both
+the `undirected_graph` and `directed_graph`, the much more general `adjacency_list`
+and `adjacency_matrix` classes, the truth about properties and property maps,
+tips and tricks for optimizing, and notes on implementing new Boost.Graph
+algorithms.
+
+[include guide_undirected.qbk]
+
+[include guide_directed.qbk]
+
+[include guide_adjacency_list.qbk]
+
+[h2 Optimizing for Performance]
+One of the unfortunate problems of providing general purpose classes is that they often
+fail to scale up to larger problems. Consider the Six Degrees of Kevin Bacon game. What
+happens if you want to play on, say the entire contents of the
+[@http://www.imdb.com Internet Movie Database (IMDb)]?
+Will the `undirected_graph` class be capable of building the data structure and running
+the search algorithms in reasonable time? Probably not. This section is a guide on migrating
+from a "canned" graph to a customized solution.
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
@@ 0,0 +1,480 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section The `adjacency_list` Class]
+As mentioned in the Tour, the `adjacency_list` has six template parameters. Three are
+used to select storage types for the vertex list, the edge list and the out edge list,
+and the remaining three define the interior properties of vertices, edges, and the
+graph itself.
+
+[h2 Choosing the Edgelist and VertexList]
+This section focuses on how to decide which version of the `adjacency_list` class to use in different
+situations. The adjacency_list is like a swissarmy knife in that it can be configured in many ways.
+The parameters that we will focus on in this section are `OutEdgeList` and `VertexList`, which control
+the underlying data structures that will be used to represent the graph. The choice of `OutEdgeList` and
+`VertexList` affects the time complexity of many of the graph operations and the space complexity of the
+graph object.
+
+Boost.Graph uses containers from the STL such as `std::vector`, `std::list`, and `std::set` to represent
+the set of vertices and the adjacency structure (outedges and inedges) of the graph. There are several
+selector types that are used to specify the choice of container for `OutEdgeList` and `VertexList`.
+
+* `vecS` selects `std::vector`.
+* `listS` selects `std::list`.
+* `slistS` selects `std::slist`.
+* `setS` selects `std::set`.
+* `multisetS` selects `std::multiset`.
+* `hash_setS` selects `std::hash_set`.
+
+[h3 Choosing the VertexList Type]
+The VertexList parameter determines what kind of container will be used to represent the vertex set, or
+twodimensional structure of the graph. The container must model /Sequence/ or /RandomAccessContainer/. In
+general, listS is a good choice if you need to add and remove vertices quickly. The price for this is extra
+space overhead compared to choosing `vecS`.
+
+[h4 Space Complexity of the VertexList]
+The `std::list` has a higher pervertex space overhead than the `std::vector`, storing three extra pointers
+per vertex.
+
+[h4 Time Complexity of the VertexList]
+The choice of VertexList affects the time complexity of the following operations.
+
+[table VertexList Storage Options
+ [[Operation] [Performance Considerations]]
+ [
+ [`add_vertex()`]
+ [
+ This operation is amortized constant time for both vecS and listS (implemented with
+ `push_back()`). However, when the VertexList type is `vecS` the time for this operation
+ is occasionally large because the vector will be reallocated and the whole graph copied
+ but is still amortized constant time.
+ ]
+ ]
+ [
+ [`remove_vertex()`]
+ [
+ This operation is constant time for listS and O(V + E) for vecS. The large time
+ complexity for vecS is because the vertex descriptors (which in this case are indices
+ that correspond to the vertices' place in the vertex list) must be adjusted in the
+ outedges for the whole graph.
+ ]
+ ]
+ [
+ [`vertex()`]
+ [
+ This operation is constant time for vecS and for `listS`.
+ ]
+ ]
+]
+
+[h3 Choosing the OutEdgeList Type]
+The OutEdgeList parameter determines what kind of container will be used to store the outedges (and
+possibly inedges) for each vertex in the graph. The containers used for edge lists must either satisfy
+the requirements for Sequence or for AssociativeContainer.
+
+One of the first things to consider when choosing the OutEdgeList is whether you want `adjacency_list` to
+enforce the absence of parallel edges in the graph (that is, enforce that the graph not become a multigraph).
+If you want this enforced then use the setS or hash_setS selectors. If you want to represent a
+multigraph, or know that you will not be inserting parallel edges into the graph, then choose one of
+the Sequence types: `vecS`, `listS`, or `slistS`. You will also want to take into account the differences in
+time and space complexity for the various graph operations. Below we use V for the total number of vertices
+in the graph and E for the total number of edges. Operations not discussed here are constant time.
+
+[h4 Space Complexity of the OutEdgeList]
+The selection of the OutEdgeList affects the amount of space overhead per edge in the graph object. In the
+order of least space to most space, the selectors are `vecS`, `slistS`, `listS`, and `setS`.
+
+[h4 Time Complexity of the OutEdgeList]
+In the following description of the time complexity for various operations, we use E/V inside of the "bigO"
+notation to express the length of an outedge list. Strictly speaking this is not accurate because E/V merely
+gives the average number of edges per vertex in a random graph. The worstcase number of outedges for a vertex
+is V (unless it is a multigraph). For sparse graphs E/V is typically much smaller than V and can be considered
+a constant.
+
+[table OutEdgeList Storage Options
+ [[Operation] [Performance Considerations]]
+ [
+ [`add_edge()`]
+ [
+ When the OutEdgeList is a UniqueAssociativeContainer like `std::set` the absence of
+ parallel edges is enforced when an edge is added. The extra lookup involved has time
+ complexity O(log(E/V)). The OutEdgeList types that model Sequence do not perform this
+ check and therefore add_edge() is amortized constant time. This means that it if you
+ don't care whether the graph has parallel edges, or know that the input to the
+ graph does not contain them, then it is better to use the sequencebased OutEdgeList.
+ The `add_edge()` for the sequencebased OutEdgeList is implemented with `push_front()`
+ or `push_back()`. However, for `std::list` and `std::slist` this operation will
+ typically be faster than with `std::vector` which occasionally reallocates
+ and copies all elements.
+ ]
+ ]
+ [
+ [`remove_edge()`]
+ [
+ For sequencebased OutEdgeList types this operation is implemented with `std::remove_if()`
+ which means the average time is E/V. For setbased OutEdgeList types this is implemented
+ with the `erase()` member function, which has average time log(E/V).
+ ]
+ ]
+ [
+ [`edge()`]
+ [
+ The time complexity for this operation is O(E/V) when the OutEdgeList type is a Sequence
+ and it is O(log(E/V)) when the OutEdgeList type is an AssociativeContainer.
+ ]
+ ]
+ [
+ [`clear_vertex()`]
+ [
+ For directed graphs with sequencebased OutEdgeList types the time complexity is O(V + E),
+ while for associative container based OutEdgeList types the operation is faster, with
+ time complexity O(V log(E/V)). For undirected graphs this operation is O(E2/V2) or
+ O(E/V log(E/V)).
+ ]
+ ]
+ [
+ [`remove_vertex()`]
+ [
+ The time complexity for this operation is O(V + E) regardless of the OutEdgeList type.
+ ]
+ ]
+ [
+ [`out_edge_iterator::operator++()`]
+ [
+ This operation is constant time and exhibits a similar speed ordering as
+ the `out_edge_iterator` with respect to the OutEdgeList selection.
+ ]
+ ]
+
+ [
+ [`in_edge_iterator::operator++()`]
+ [
+ This operation is constant time and fast (same speed as incrementing a pointer).
+ The selection of OneD does not affect the speed of this operation.
+ ]
+ ]
+ [
+ [`vertex_iterator::operator++()`]
+ [
+ This operation is constant time and exhibits a similar speed ordering as the
+ out_edge_iterator with respect to the OutEdgeList selection. Traversing through the
+ whole edge set is O(V + E).
+ ]
+ ]
+ [
+ [`adjacency_iterator::operator++()`]
+ [
+ This operation is constant time and exhibits a similar speed ordering as
+ the out_edge_iterator with respect to the OutEdgeList selection.
+ ]
+ ]
+]
+
+[h2 Directed and Undirected Adjacency Lists]
+The `adjacency_list` class can be used to represent both directed and undirected graphs, depending on the
+argument passed to the Directed template parameter. Selecting `directedS` or `bidirectionalS` choose a directed
+graph, whereas `undirectedS` selects the representation for an undirected graph. See Section Undirected Graphs
+for a description of the difference between directed and undirected graphs in Boost.Graph. The `bidirectionalS`
+selector specifies that the graph will provide the `in_edges()` function as well as the `out_edges()` function.
+This imposes twice as much space overhead per edge, which is why `in_edges()` is optional.
+
+[h2 Internal Properties]
+Properties can be attached to the vertices or edges of an `adjacency_list` graph via the property interface.
+The template parameters VertexProperty and EdgeProperty of the `adjacency_list` class are meant to be filled
+by these interior properties.
+
+[note The Boost Graph Library supports two interchangeable methods for specifying interior properties:
+bundled properties and property lists. The former is easier to use and requires less effort, whereas the
+latter is compatible with older, broken compilers and is backwardcompatible with Boost versions prior to
+1.32.0. If you absolutely require these compatibility features, read on to learn about property lists.
+Otherwise, we strongly suggest that you read about the bundled properties mechanism.]
+
+One may specify internal properties via property lists, which are built from instances of the property class
+declared as follows.
+
+ template <class PropertyTag, class T, class NextProperty = no_property> struct property;
+
+The PropertyTag template parameter is a tag class that simply identifies or gives a unique name to the property.
+There are several predefined tags, and it is easy to add more.
+
+ struct vertex_index_t { };
+ struct vertex_index1_t { };
+ struct vertex_index2_t { };
+ struct edge_index_t { };
+ struct graph_name_t { };
+ struct vertex_name_t { };
+ struct edge_name_t { };
+ struct edge_weight_t { };
+ struct edge_weight2_t { };
+ struct edge_capacity_t { };
+ struct edge_residual_capacity_t { };
+ struct edge_reverse_t { };
+ struct vertex_distance_t { };
+ struct vertex_root_t { };
+ struct vertex_all_t { };
+ struct edge_all_t { };
+ struct graph_all_t { };
+ struct vertex_color_t { };
+ struct vertex_rank_t { };
+ struct vertex_predecessor_t { };
+ struct vertex_isomorphism_t { };
+ struct vertex_invariant_t { };
+ struct vertex_invariant1_t { };
+ struct vertex_invariant2_t { };
+ struct vertex_degree_t { };
+ struct vertex_out_degree_t { };
+ struct vertex_in_degree_t { };
+ struct vertex_discover_time_t { };
+ struct vertex_finish_time_t { };
+
+The T template parameter of property specifies the type of the property values. The type T must be Default
+Constructible, Assignable, and Copy Constructible. Like the containers of the C++ Standard Library, the
+property objects of type T are held byvalue inside of the graph.
+
+The NextProperty parameter allows property types to be nested, so that an arbitrary number of properties
+can be attached to the same graph.
+
+The following code shows how a vertex and edge property type can be assembled and used to create a graph type.
+We have attached a distance property with values of type float and a name property with values of type
+std::string to the vertices of the graph. We have attached a weight property with values of type float to
+the edges of the graph.
+
+ // specify property types fora graph
+ typedef property<vertex_distance_t, float, property<vertex_name_t, std::string> > VertexProperty;
+ typedef property<edge_weight_t, float> EdgeProperty;
+
+ // specify the graph has having the above properties
+ typedef adjacency_list<mapS, vecS, undirectedS,
+ VertexProperty, EdgeProperty> Graph;
+
+ // instantiate the graph with N (a compiletime constant integer) vertices
+ Graph g(N);
+
+The property values are then read from and written to using property maps. See Section Interior Properties
+for a description of how to obtain property maps from a graph, and read Section Property Maps for how to use
+property maps.
+
+[h3 Builtin Vertex and Edge Properties]
+Even if a graph type is instantiated without any userspecified properties, Boost.Graph will define a few
+default properties for both vertices and edges. These are always available in algorithms through the
+property map interfaces.
+
+Vertices have the following properties:
+
+Edges have the following properties:
+
+[h3 Custom Edge Properties]
+Creating your own property types and properties is easy; just define a tag class for your new property.
+The property tag class will need to define num with a unique integer ID, and kind which should be either
+edge_property_tag, vertex_property_tag, or graph_property_tag.
+
+ struct flow_t {
+ typedef edge_property_tag kind;
+ };
+
+ struct capacity_t {
+ typedef edge_property_tag kind;
+ };
+
+You can also use enum's instead of struct's to create tag types. Create an enum type for each property.
+The first part of the name of the enum type must be edge, vertex, or graph followed by an underscore,
+the new property name, and a _t at the end. Inside the enum, define a value with the same name minus the
+_t. Then invoke the BOOST_INSTALL_PROPERTY macro.
+
+ enum edge_flow_t { edge_flow };
+ enum edge_capacity_t { edge_capacity };
+
+ namespace boost {
+ BOOST_INSTALL_PROPERTY(edge, flow);
+ BOOST_INSTALL_PROPERTY(edge, capacity);
+ }
+
+Now you can use your new property tag in the definition of properties just as you would one of the builtin tags.
+
+ typedef property<capacity_t, int> Cap;
+ typedef property<flow_t, int, Cap> EdgeProperty;
+ typedef adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;
+
+Just as before, the property maps for these properties can be obtained from the graph via the get(Property, g) function.
+
+ property_map<Graph, capacity_t>::type capacity = get(capacity_t(), G);
+ property_map<Graph, flow_t>::type flow = get(flow_t(), G);
+
+The file edge_property.cpp shows the complete source code for this example.
+
+[h3 Custom Vertex Properties]
+Creating your own properties to attach to vertices is just as easy as for edges. Here we want to attach people's
+first names to the vertices in the graph.
+
+ struct first_name_t {
+ typedef vertex_property_tag kind;
+ };
+
+Now we can use the new tag in the property class and use that in the assembly of a graph type. The following
+code shows creating the graph type, and then creating the graph object. We fill in the edges and also assign
+names to the vertices. The edges will represent "who owes who";
+
+ typedef property<first_name_t, std::string> FirstNameProperty;
+ typedef adjacency_list<vecS, vecS, directedS,
+ FirstNameProperty> MyGraphType;
+
+ typedef pair<int,int> Pair;
+ Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
+ Pair(0,4), Pair(2,0), Pair(3,0),
+ Pair(2,4), Pair(3,1), Pair(3,4),
+ Pair(4,0), Pair(4,1) };
+
+ MyGraphType G(5);
+ for (int i = 0; i < 11; ++i) {
+ add_edge(edge_array[i].first, edge_array[i].second, G);
+ }
+
+ property_map<MyGraphType, first_name_t>::type name = get(first_name_t(), G);
+
+ boost::put(name, 0, "Jeremy");
+ boost::put(name, 1, "Rich");
+ boost::put(name, 2, "Andrew");
+ boost::put(name, 3, "Jeff");
+ name[4] = "Kinis"; // you can also use the operator[] too
+
+ who_owes_who(edges(G).first, edges(G).second, G);
+
+The `who_owes_who()` function written for this example was implemented in a generic style. The input is
+templated so we do not know the actual graph type. To find out the type of the property map for our
+firstname property, we need to use the property_map traits class. The const_type is used since the graph
+parameter is const. Once we have the property map type, we can deduce the value type of the property using
+the property_traits class. In this example, we know that the property's value type will be `std::string`, but
+written in this generic fashion the `who_owes_who()` function could work with other property value types.
+
+ template <class EdgeIter, class Graph>
+ void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
+ {
+ // Access the propety acessor type for this graph
+ typedef typename property_map<Graph, first_name_t>::const_type NameMap;
+ typedef typename boost::property_traits<NameMap>::value_type NameType;
+
+ NameMap name = get(first_name, G);
+ NameType src_name, targ_name;
+
+ while (first != last) {
+ src_name = boost::get(name, source(*first, G));
+ targ_name = boost::get(name, target(*first, G));
+ cout << src_name << " owes "
+ << targ_name << " some money" << "\n";
+ ++first;
+ }
+ }
+
+The output is:
+
+ Jeremy owes Rich some money
+ Jeremy owes Andrew some money
+ Jeremy owes Jeff some money
+ Jeremy owes Kinis some money
+ Andrew owes Jeremy some money
+ Andrew owes Kinis some money
+ Jeff owes Jeremy some money
+ Jeff owes Rich some money
+ Jeff owes Kinis some money
+ Kinis owes Jeremy some money
+ Kinis owes Rich some money
+
+The complete source code to this example is in the file interior_property_map.cpp.
+
+[h3 Customizing the Adjacency List Storage]
+The `adjacency_list` is constructed out of two kinds of containers. One type of container to hold all the
+vertices in the graph, and another type of container for the outedge list (and potentially inedge list)
+for each vertex. Boost.Graph provides selector classes that allow the user to choose between several of the
+containers from the STL. It is also possible to use your own container types. When customizing the VertexList
+you need to define a container generator as described below. When customizing the OutEdgeList you will need
+to define a container generator and the parallel edge traits. The file container_gen.cpp has an example of
+how to use a custom storage type.
+
+[h4 Container Generator]
+The `adjacency_list` class uses a traits class called `container_gen` to map the OutEdgeList and VertexList
+selectors to the actual container types used for the graph storage. The default version of the traits class
+is listed below, along with an example of how the class is specialized for the listS selector.
+
+ namespace boost {
+ template <class Selector, class ValueType>
+ struct container_gen { };
+
+ template <class ValueType>
+ struct container_gen<listS, ValueType> {
+ typedef std::list<ValueType> type;
+ };
+ }
+
+To use some other container of your choice, define a selector class and then specialize the `container_gen`
+for your selector.
+
+ struct custom_containerS { }; // your selector
+
+ namespace boost {
+ // the specialization for your selector
+ template <class ValueType>
+ struct container_gen<custom_containerS, ValueType> {
+ typedef custom_container<ValueType> type;
+ };
+ }
+
+There may also be situations when you want to use a container that has more template parameters than
+just ValueType. For instance, you may want to supply the allocator type. One way to do this is to
+hardcode in the extra parameters within the specialization of container_gen. However, if you want more
+flexibility then you can add a template parameter to the selector class. In the code below we show how
+to create a selector that lets you specify the allocator to be used with the `std::list`.
+
+ template <class Allocator>
+ struct list_with_allocatorS { };
+
+ namespace boost {
+ template <class Alloc, class ValueType>
+ struct container_gen<list_with_allocatorS<Alloc>, ValueType>
+ {
+ typedef typename Alloc::template rebind<ValueType>::other Allocator;
+ typedef std::list<ValueType, Allocator> type;
+ };
+ }
+
+ // now you can define a graph using std::list and a specific allocator
+ typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
+
+[h4 Push and Erase for the Custom Container]
+You must also tell the `adjacency_list` how elements can be efficiently added and removed from the
+custom container. This is accomplished by overloading the `push()` and `erase()` functions for the custom
+container type. The `push()` function should return an iterator pointing to the newly inserted element
+and a bool flag saying whether the edge was inserted.
+
+ template <class T>
+ std::pair<typename custom_container<T>::iterator, bool>
+ push(custom_container<T>& c, const T& v)
+ {
+ // this implementation may need to change for your container
+ c.push_back(v);
+ return std::make_pair(boost::prior(c.end()), true);
+ }
+
+ template <class T>
+ void erase(custom_container<T>& c, const T& x)
+ {
+ // this implementation may need to change for your container
+ c.erase(std::remove(c.begin(), c.end(), x), c.end());
+ }
+
+There are default `push()` and `erase()` functions implemented for the STL container types.
+
+[h4 Parallel Edge Traits]
+When customizing the OutEdgeList, you must also specialize the `parallel_edge_traits` class to specify whether
+the container type allows parallel edges (and is a Sequence) or if the container does not allow parallel
+edges (and is an AssociativeContainer).
+
+ template <>
+ struct parallel_edge_traits<custom_containerS> {
+ typedef allow_parallel_edge_tag type;
+ };
+
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
@@ 0,0 +1,10 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section Working with Directed Graphs]
+Blah blah blah...
+[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
@@ 0,0 +1,528 @@
+[/
+ / 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 Working with Undirected Graphs]
+This section could be called "Things to do with Undirected Graphs" since its goal
+is to provide a number of concrete examples of how undirected graphs can be used
+to solve problems  and more specifically how to implement them using Boost.Graph.
+
+[h2 Citation Graphs]
+The first example problem we want to look at is the "Six Degrees of Kevin Bacon"
+problem. Mathematicians might be more familiar with this is as "Erdos Numbering".
+This problem is based on a network of relationships between people. In the Six
+Degrees problem, two actors are related if they appear in the same movie. With
+Erdos, two people are related if they collaborated on a published article. This
+type of network is often called a /citation/ graph (or network) and is 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. There are actually two different problems that we
+can solve:
+# 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.
+# What is the fastest way to travel (along the citation graph) from Kevin Bacon
+to any other actor? This is more commonly known as the "Six Degrees of Kevin
+Bacon Game" and was actually discussed (on air) by its inventors on MTV's "The Jon
+Stewart Show" (go figure).
+These are actually two different instances of the same problem and can be solved
+using the same algorithm  a simple breadthfirst search (BFS).
+
+[h3 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 index;
+ int distance;
+ std::string name;
+ };
+
+ struct Movie
+ {
+ std::string name;
+ };
+
+In this example, we are "internalizing" a number of properties for each vertex.
+Here, `Actor::index` represents the index of the vertex within the graph. Unfortunately,
+the graph class is not smart enough to automatically assign and maintain these indices
+(for a number of reasons), so we're going to have to manage this later. Likewise, the
+`Actor::distance` property records the distance from each actor to Kevin Bacon. This is
+the value that we will be computing for every actor in the data set. The `Actor::name`
+and `Movie::name` properties should be fairly selfexplanatory.
+
+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::type, int Actor::*>::type ActorIndexMap;
+ typedef boost::property_map<Graph::type, int Actor::*>::type ActorDistanceMap;
+
+The first template argument `Graph::type` defines the type of the structure that
+the property map is going to access. The second template argument with the somewhat
+peculiar syntax is the type of the property. These are pointers to member variables
+of type `int`.
+
+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>
+
+ typedef std::map<std::string, Vertex> ActorMap;
+
+ using namespace std;
+ using namespace boost;
+
+ void build_citation_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
+ v = add_vertex(graph);
+ it>second = v;
+
+ // configure the vertex properties
+ g[v].index = num_vertices(graph)  1;
+ 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.
+
+[warning
+Vertex indices (as used in this example) are entirely unstable if vertices are removed
+from the graph. Many graph algorithms require vertex index maps with values in the range
+\[0, `num_vertices(g)`)/. If we were to remove the first vertex in this example, the
+vertex indices would be incorrect and the program would potentially crash (accessing
+beyond `num_vertices(g)`). It is relatively trivial and inexpensive (O(`num_vertices(g)`)
+to renumber vertices just before running algorithms that require vertex index maps.
+]
+
+Our main program looks like this:
+
+ int main()
+ {
+ Graph graph;
+ ActorMap actors;
+ build_citation_graph(cin, graph, actors);
+
+ // ...to be continued...
+ }
+
+[h3 Distance To Kevin Bacon]
+Now, all we have left to do is assign distances to Kevin Bacon. To do this, we're going
+to use a breadthfirst search (starting from Kevin Bacon) and simply record the "depth"
+of each vertex as the distance from Kevin to every other actor. To do this, we're going
+to need some help in the form of a BFS visitor.
+
+ template <typename DistanceMap>
+ struct ActorDistanceRecorder : public bfs_visitor<>
+ {
+ ActorDistanceRecorder(DistanceMap d)
+ : distances(d)
+ {}
+
+ template <typename Edge, typename Graph>
+ void tree_edge(Edge e, const Graph& g) const
+ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ Vertex
+ u = source(e, g),
+ v = target(e, g);
+ distances[v] = distances[u] + 1;
+ }
+
+ DistanceMap distances;
+ };
+
+This visitor overloads the `tree_edge()` member function in order to compute the distance
+from a central vertex. In this example, the distance of a vertex from a starting vertex
+is one plus the depth of its parent in the spanning tree generated by a BFS.
+
+We're also going to provide a simple little helper function so we don't have to
+explicitly instantiate the visitor when we use it with the BFS algorithm.
+
+ template <typename DistanceMap>
+ ActorDistanceRecorder<DistanceMap> record_actor_distances(DistanceMap d)
+ {
+ return ActorDistanceRecorder<DistanceMap>(d);
+ }
+
+This leaves the question: what is a DistanceMap? To answer that, we have to complete the
+solution to the Kevin Bacon problem. Back to the `main()`...
+
+ int main()
+ {
+ // ...continue from above...
+
+ ActorIndexMap indices = get(&Actor::index, graph);
+ ActorDistanceMap distances = get(&Actor::distance, graph);
+
+ // find kevin (our starting point) and zero out his distancetoself
+ Vertex kevin = actors["Kevin Bacon"];
+ distances[kevin] = 0;
+
+ breadth_first_search(graph, kevin,
+ vertex_index_map(indices).
+ visitor(record_actor_distances(distances)));
+
+ // ...to be continued...
+ }
+
+Finally, we're using the property maps that we defined so far above. The `get()` function
+essentially returns a maplike object that allows us to read and/or write the specified vertex
+or edge property. As mentioned earlier, these maps allow algorithms to reand and write both
+internal and external properties in a uniform method. Because graph algorithms cannot guess
+whether properties are internal or external, we have to pass these maps to just about every
+algorithm in this manner.
+
+We actually use the actors' distance map as it is in the distance recorder above (mostly as
+an example). We could just as easily have written the distance assignment as:
+
+ graph[kevin].distance = 0;
+
+with the same effect.
+
+Finally, we can run our BFS and assign "Kevin Bacon numbers" to our actors. This is done
+by calling the `breadth_first_search()` function passing the graph, the starting vertex
+and some named parameters. The first named parameter is the vertex index map which provides
+read access to the `Actor::index` property assigned during graph construction. The second
+is an instance of our distancerecording visitor (as returned by our helper function).
+
+After finishing, each vertices distance property will be assigned. All there is left to do
+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
+]
+
+[h3 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;
+
+We are also going to change the BFS visitor that we used in the previous example.
+
+ template <typename ParentMap>
+ struct ActorParentRecorder : public bfs_visitor<>
+ {
+ ActorParentRecorder(ParentMap d)
+ : parents(d)
+ {}
+
+ template <typename Edge, typename Graph>
+ void tree_edge(Edge e, const Graph& g) const
+ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ Vertex
+ u = source(e, g),
+ v = target(e, g);
+ parents[v] = u;
+ }
+
+ ParentMap parents;
+ };
+
+ template <typename ParentMap>
+ ActorParentRecorder<ParentMap> record_actor_parents(ParentMap d)
+ {
+ return ActorParentRecorder<ParentMap>(d);
+ }
+
+Despite the fact that this code is essentially cut, paste, and replace from the code
+above, there is one interesting change. Instead of assigning a distance to a vertex,
+we are setting the parent of the target to be the source. This one line allows us
+to walk the shortest paths from any actor to Kevin Bacon.
+
+The only other changes are going to be in the `main()` program.
+
+ int main(int argc, char *argv[])
+ {
+ 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_citation_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;
+ }
+
+ ActorIndexMap = get(&Actor::index, graph);
+ ActorParentMap = get(&Actor::parent, graph);
+
+ breadth_first_search(graph, u,
+ vertex_index_map(indices).
+ visitor(record_actor_parents(parents)));
+
+ // ...to be continued...
+
+The `find_actor_vertex()` method is relatively trivial:
+
+ 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 passing our
+modified parentrecording visitor to the `breadth_first_search()` function. The step
+in the solution is to backtrack from the target actor to the parent, printing the
+movies that form the citation chain.
+
+ int main(...)
+ {
+ // ...continued from before...
+ while(v != u) {
+ Vertex p = parents[v];
+ string from = g[v].name;
+ string to = g[p].name;
+
+ Edge e;
+ Graph::out_edge_iterator i, j;
+ for(tie(i, j) = out_edges(v, g); i != j; ++i) {
+ if(target(*i, g) == p) {
+ e = *i;
+ break;
+ }
+ }
+
+ string movie = g[e].name;
+ cout << from << " starred with " << to << " in '" << movie << "'\n";
+
+ v = p;
+ }
+ }
+
+The only "complicated" part of the backtracking is finding the edge from
+the child to the parent. Because `undirected_graph` does is not a model of an
+`adjacency_matrix`, there is no simple method that returns edge data given
+two vertices.
+
+[note This problem can be simplified using the `graph_as_matrix` adapter.]
+
+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.
+
+[h3 Closing Thoughts]
+Notice that this problem can be trivially adapted to the Erd\ös Numbering problem
+by simply redefining the semantics of the graph. Instead of actors, each vertex
+can represent an author, and each edge connects two authors if and only if both
+authors collaborated on the same publication. It is easy to see that the two graphs
+are equivalent, and the same algorithms will work on both.
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tour.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tour.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tour.qbk 20070611 12:55:12 EDT (Mon, 11 Jun 2007)
@@ 52,7 +52,7 @@
using namespace std;
using namespace boost;

+
int main(int, char*[])
{
// create a typedef for the Graph type
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tut_adjacency_list.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/tut_adjacency_list.qbk 20070611 12:55:12 EDT (Mon, 11 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` Class]
As mentioned in the Tour, the `adjacency_list<>` has six 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
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