|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-11 12:55:13
Author: asutton
Date: 2007-06-11 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 2007-06-11 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 2007-06-11 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 old-style 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 2007-06-11 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 swiss-army 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 (out-edges and in-edges) 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
+two-dimensional 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 per-vertex 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
+ out-edges 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 out-edges (and
+possibly in-edges) 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 multi-graph).
+If you want this enforced then use the setS or hash_setS selectors. If you want to represent a
+multi-graph, 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 "big-O"
+notation to express the length of an out-edge list. Strictly speaking this is not accurate because E/V merely
+gives the average number of edges per vertex in a random graph. The worst-case number of out-edges for a vertex
+is V (unless it is a multi-graph). 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 sequence-based OutEdgeList.
+ The `add_edge()` for the sequence-based 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 sequence-based OutEdgeList types this operation is implemented with `std::remove_if()`
+ which means the average time is E/V. For set-based 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 sequence-based 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 backward-compatible 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 by-value 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 compile-time 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 Built-in Vertex and Edge Properties]
+Even if a graph type is instantiated without any user-specified 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
+first-name 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 out-edge list (and potentially in-edge 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
+hard-code 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 2007-06-11 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 2007-06-11 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 breadth-first 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 self-explanatory.
+
+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 breadth-first 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 distance-to-self
+ 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 map-like 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 distance-recording 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 parent-recording 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 2007-06-11 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 2007-06-11 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 swiss-army 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 (out-edges and in-edges) 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
-two-dimensional 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 per-vertex 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
- out-edges 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 out-edges (and
-possibly in-edges) 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 multi-graph).
-If you want this enforced then use the setS or hash_setS selectors. If you want to represent a
-multi-graph, 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 "big-O"
-notation to express the length of an out-edge list. Strictly speaking this is not accurate because E/V merely
-gives the average number of edges per vertex in a random graph. The worst-case number of out-edges for a vertex
-is V (unless it is a multi-graph). 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 sequence-based OutEdgeList.
- The `add_edge()` for the sequence-based 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 sequence-based OutEdgeList types this operation is implemented with `std::remove_if()`
- which means the average time is E/V. For set-based 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 sequence-based 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 backward-compatible 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 by-value 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 compile-time 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 Built-in Vertex and Edge Properties]
-Even if a graph type is instantiated without any user-specified 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
-first-name 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 out-edge list (and potentially in-edge 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
-hard-code 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
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk