|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-27 08:23:16
Author: asutton
Date: 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
New Revision: 7192
URL: http://svn.boost.org/trac/boost/changeset/7192
Log:
Massive filesystem change... Put guide components into separate
directories for "convenience" also as per doc structure suggestions.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/con_graphs.qbk
- copied unchanged from r7186, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/concepts.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide_adjacency_list.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide_directed.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide/guide_undirected.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_adjacency_list.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_connected_components.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_connectivity.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_directed_graph.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_distributions.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_strong_components.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/ref_undirected_graph.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk
- copied unchanged from r7185, /sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_details.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,110 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Graph Concepts]
-The heart of the Boost Graph Library (BGL) is the interface, or concepts (in the
-parlance of generic programming), that define how a graph can be examined and
-manipulated in a data-structure neutral fashion. In fact, the BGL interface need
-not even be implemented using a data-structure, as for some problems it is easier
-or more efficient to define a graph implicitly based on some functions.
-
-The Boost.Graph interface does not appear as a single graph concept. Instead it is
-factored into much smaller peices. The reason for this is that the purpose of a
-concept is to summarize the requirements for particular algorithms. Any one algorithm
-does not need every kind of graph operation, typically only a small subset. Furthermore,
-there are many graph data-structures that can not provide efficient implementations of
-all the operations, but provide highly efficient implementations of the operations
-necessary for a particular algorithm . By factoring the graph interface into many smaller
-concepts we provide the graph algorithm writer with a good selection from which to choose
-the concept that is the closest match for their algorithm.
-
-Figure 1 shows the refinements relations between the graph concepts. The reason for
-factoring the graph interface into so many concepts is to encourage algorithm interfaces
-to require and use only the minimum interface of a graph, thereby increasing the
-usability of the algorithm.
-
-Figure 1: The graph concepts and refinement relationships.
-
-Table 1 gives a summary of the valid expressions and associated types for the graph
-concepts and provides links to the detailed descriptions of each of the concepts.
-The notation used in the table is as follows.
-
-[table
- [[Expression] [Return Type or Description]]
- [[*Graph*]]
- [[`graph_traits<G>::vertex_descriptor`] [The type for vertex representative objects.]]
- [[`graph_traits<G>::edge_descriptor`] [The type for edge representative objects.]]
- [[`graph_traits<G>::directed_category`] [Graph is directed or undirected?]]
- [[`graph_traits<G>::edge_parallel_category`] [Graph allows parallel edges?]]
- [[`graph_traits<G>::traversal_category`] [The ways in which the vertices and edges can be traversed.]]
- [[*Incidence Graph* refines Graph]]
- [[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
- [[`graph_traits<G>::out_edge_iterator`] [Type for iterating over out edges.]]
- [[`out_edges(v,g)`] [`std::pair<out_edge_iterator, out_edge_iterator>`]]
- [[`out_degree(v,g)`] [`degree_size_type`]]
- [[`source(e,g)`] [`vertex_descriptor`]]
- [[`target(e,g)`] [`vertex_descriptor`]]
- [[*BidirectionalGraph* refines IncidenceGraph]]
- [[`graph_traits<G>::in_edge_iterator`] [Type for iterating over in edges.]]
- [[`in_edges(v,g)`] [`std::pair<in_edge_iterator,in_edge_iterator>`]]
- [[`in_degree(v,g)`] [`degree_size_type`]]
- [[`degree(v,g)`] [`degree_size_type`]]
- [[*AdjacencyGraph* refines Graph]]
- [[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
- [[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
- [[*VertexListGraph* refines IncidenceGraph and AdjacencyGraph]]
- [[`graph_traits<G>::vertex_iterator`] [Type for iterating over vertices.]]
- [[`graph_traits<G>::vertices_size_type`] [Unsigned integer type for the number of vertices.]]
- [[`vertices(g)`] [`std::pair<vertex_iterator,vertex_iterator>`]]
- [[`num_vertices(g)`] [`vertices_size_type`]]
- [[*EdgeListGraph* refines Graph]]
- [[`graph_traits<G>::edge_iterator`] [Type for iterating over edges.]]
- [[`graph_traits<G>::edges_size_type`] [Unsigned integer type for the number of edges.]]
- [[`edges(g)`] [`std::pair<edge_iterator, edge_iterator>`]]
- [[`num_edges(g)`] [`edges_size_type`]]
- [[`source(e,g)`] [`vertex_descriptor`]]
- [[`target(e,g)`] [`vertex_descriptor`]]
- [[*AdjacencyMatrix* refines Graph]]
- [[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
- [[*MutableGraph* refines Graph]]
- [[`add_vertex(g)`] [`vertex_descriptor`]]
- [[`clear_vertex(v,g)`] [`void`]]
- [[`clear_out_edges(v,g)`] [`void`]]
- [[`clear_in_edges(v,g)`] [`void`]]
- [[`add_edge(u,v,g)`] [`std::pair<edge_descriptor,bool>`]]
- [[`remove_edge(u,v,g)`] [`void`]]
- [[`remove_edge(e,g)`] [`void`]]
- [[`remove_edge(ei,g)`] [`void`]]
- [[`remove_edge_if(pred,g)`] [`void`]]
- [[`remove_out_edge_if(v,pred,g)`] [`void`]]
- [[`remove_in_edge_if(v,pred,g)`] [`void`]]
- [[*MutablePropertyGraph* refines Graph]]
- [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
- [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
- [[*PropertyGraph* refines Graph]]
- [[`property_map<G,Property>::type`] [Type for a mutable property map.]]
- [[`property_map<G,Property>::const_type`] [Type for a non-mutable property map.]]
- [[`get(p,g)`] [Function to get a property map.]]
- [[`get(p,g,x)`] [Get the property value for vertex or edge `x`]]
- [[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
-]
-
-[*TODO]
-
-There are some functions missing like `get_property()` and `put/set_property()`.
-These occur in some documentation somewhere but are in no means pervasive, complete
-or accurate.
-
-It should also be worth pointing out that we can redefine the entire concept hierarchy
-based on a) vertex or edge operations, b) directed/undirected or c) simple or multigraphs.
-Basically, there are some interesting ways to conceptualize the Boost.Graph interface.
-
-[h3 Undirected Graphs]
-
-Lots of stuff here on undirected graphs...
-
-[endsect]
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,34 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Concepts]
-This section provides a detailed listing of the type concepts in the Boost.Graph
-library.
-
-[heading Notation]
-For the following sections, we use the following notional convents:
-
-[table
- [[Object] [Type]]
- [[G] [A type that is a model of a Graph (or refinement)]]
- [[g] [An object of type G]]
- [[u,v] [Objects of type `graph_traits<G>::vertex_descriptor`]]
- [[e] [An object of type `graph_traits<G>::edge_descriptor`]]
- [[vi] [An object of type `graph_traits<G>::vertex_iterator`]]
- [[ei] [An object of type `graph_traits<G>::edge_iterator`]]
- [[vp] [An object of type `G::vertex_property_type`]]
- [[ep] [An object of type `G::edge_property_type`]]
- [[Property] [A type used to specify a vertex or edge property]]
- [[p] [An object of type Property]]
- [[Predicate] [A function that, given an argument, returns true or false]]
- [[pred] [An object of type Predicate]]
-]
-
-[include con_graphs.qbk]
-[include con_visitors.qbk]
-
-[endsect]
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,16 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section User's Guide]
-
-[include guide_undirected.qbk]
-
-[include guide_directed.qbk]
-
-[include guide_adjacency_list.qbk]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,480 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section The Adjacency List]
-As mentioned in the Tour, the `adjacency_list` has seven template parameters. Three are
-used to select storage types for the vertex list, the edge list and the out edge list,
-and the remaining three define the interior properties of vertices, edges, and the
-graph itself.
-
-[h2 Choosing the Edgelist and VertexList]
-This section focuses on how to decide which version of the `adjacency_list` class to use in different
-situations. The adjacency_list is like a 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_details.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_details.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,143 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section More About Simple Graphs]
-The `directed_graph` and `undirected_graph` classes - the so-called "simple graph
-classes" are not parts of the original Boost.Graph Libray. In fact, they are some
-of the most recent additions, designed to provide a lower entry barrier to graph
-programming with Boost. As such, they leverage much of the existing Boost.Graph
-infrastructure for their implementaiton.This section provides details on design
-and structure of these classes.
-
-Both simple graph classes provides three template parameters that can be used
-to customize the internal properties of vertices, edges, and the graph itself.
-They are described in Table 1.
-
-[table
- [[Parameter] [Description] [Default]]
- [
- [VertexProperties]
- [Specifies internal properties of each vertex.]
- [`no_property`]
- ]
- [
- [EdgeProperties]
- [Specifies internal properties of each edge.]
- [`no_property`]
- ]
- [
- [GraphProperties]
- [Specifies global, internal properties for the graph.]
- [`no_property`]
- ]
-]
-
-The previous examples have all been shown using /bundled properties/ - an approach
-to specifying internal properties that allows the user to use member variables
-of common structures in property maps. However, this is not the only means of
-specifying properties. If your compiler does not support partial template
-specialization, then you cannot use bundled properties in your program. See the
-page on [link boost_graph.old_style_properties old-Style properties] for details.
-
-One of the most important features of both of these classes is that they are
-implemented entirely in terms of an underlying `adjacency_list`. While, it may
-not be commonplace to disclose implementation details in a user's guide, I find
-that it is actually important in this case. Because the `adjacency_list` was
-designed as the "Swiss army knife" of graph classes, it is very customizable
-and there are some significant tradeoffs in graph behavior depending on the
-arguments supplied.
-
-The `adjacency_list` class traditionally provides seven template parameters.
-These are described in Table 2 along with the arguments supplied by the
-`directed_graph` and `undirected_graph` classes.
-
-[table
- [[Parameter] [Description] [Default]]
- [
- [OutEdgeList]
- [Storage component for the out-edges of each vertex.]
- [`listS`]
- ]
- [
- [VertexList]
- [Storage component for vertices of the graph.]
- [`listS`]
- ]
- [
- [Directed]
- [
- Whether the graph is undirected, directed (out-edges only), or
- bidirectional (out- and in-edges).
- ]
- [`undirectedS` or `bidirectionalS`]
- ]
- [
- [VertexProperties]
- [See Table 1.]
- [As template argument]
- ]
- [
- [VertexProperties]
- [See Table 1.]
- [As template argument]
- ]
- [
- [VertexProperties]
- [See Table 1.]
- [As template argument]
- ]
- [
- [EdgeList]
- [Storage component for the edges of the graph.]
- [`listS`]
- ]
-]
-
-With both classes, the storage components are assigned as defaults and
-cannot be changed. The directionality of edges is also specified as
-a non-changeable parameter. It should be fairly obvious that the `undirected_graph`
-class uses the `undirectedS` selector while the `directed_graph` class uses
-`directedS`. The internal properties of the graph are assigned from the template
-parameters of the simple graph classes themselves. If omitted, these all default
-to `no_property`.
-
-This set of template arguments was chosen to provide maximum flexibility for
-solving different sets of problems. However, there may be cases where these
-classes do not meet your needs or perform poorly under certain situations.
-In this case, we suggest using `adjacency_list` directly. See the section
-[link boost_graph.user_s_guide.more_about_simple_graphs.customizing_graphs on
-customizing your graph] for more details.
-
-[h4 Stability and Validity]
-As you can see, all of the storage components for these graph classes are
-selected with `listS`. Using list storage provides a number of benefits over
-the more traditional vector storage, specifically in terms of iterator and
-descriptor stability for mutable graphs. Generally speaking stablity refers
-to the continuing validity of iterators and descriptors after changes to
-the graph such as adding or removing vertices and edges. With some storage
-components (e.g., `vecS`), iterators and descriptors can become invalide after
-some operations. However `listS` guarantees stability after most operations.
-A more complete description of containers, stability and their tradeoffs
-can be found [link boost_graph.adjacency_list.stability here].
-
-[h4 Customizing Graphs]
-Although the `undirected_graph` and `directed_graph` classes are designed
-along the "one-size fits most" principle, there can be times when these
-classes do not meet your performance requirements. For example, your problem
-may not require the extra memory overhead of bidirectional edges, which over
-a million edges or so tends to add up. Or maybe you're adding a million
-vertices to a graph and the repeated insertions to a list cause your
-computer to page a lot - potentially a performance nightmare. In these cases,
-you may need to consider customizing your graph by using an `adjacency_list`
-and tweaking some of the default storage components.
-
-Consider the first example of the co-star graphs. Suppose we have 200,000
-actors and three million edges in our data file.
-Migrating this example
-to an `adjacency_list` is nearly trivial since
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,371 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Directed Graphs]
-Like the previous section, here we take a look at how to solve different
-types graph problems using the Boost.Graph library. In this case however,
-the problems being addressed are better modeled with directed graphs. A
-directed graph (also a /digraph/) is one in which edges can only be traversed
-in a specific direction.
-
-In this section we are concerned with /dependency graphs/. A dependency graph
-describes a relationship between two entities in which one (/source/) requires
-a second (/target/). The source is said to be dependant upon the target.
-Dependency graphs arise in many, many real-world situations such as source
-code analysis, software installation, "tech-trees" in computer games, etc.
-In this example, we will look at a common dependency graph: dependencies
-between software documents and build targets.
-
-[h3 File Dependencies]
-If you've ever typed `make` and wondered how the program decides the order
-tasks to build, then this tutorial is for you. The make software relies on
-dependency information explicitly encoded into Makefiles. Binaries (executable
-programs and libraries) depend on sets of source files. Source files, which
-implement program features, depend on header files, which expose type and
-function declarations. These, in turn, might depend on generated source files
-generated by `lex`, `yacc` or any other of an assortment of code-generating
-tools. These dependencies can be modeled with a directed graph.
-
-For this example, we're actually going to use some of the files that actually
-implement the examples described in this user's guide. Their dependencies are
-shown in figure 1. Path names have been omitted for readability.
-
-[$images/guide/files.png]
-
-From this graph, it should be relatively easy to see that the build should
-start at the bottom and proceed "upwards" with the executable programs being
-built last - maybe. There are actually two different approaches to bulding
-these programs:
-
-* One at a time. This is probably what you're used to seeing. The compiler
-builds file A, followed by file B, and finally file C.
-* In parallel. If you're lucky enough to have a multi-processor computer
-available to you we might be able to process (compile) a number of different
-files at the same time by distributing the tasks to different processors.
-
-The solution to both of these problems is addressed by topologically sorting
-the graph. This provies the schedule of files to be processed by ordering
-the vertices based on their dependencies.
-
-A third problem we might encounter is that of cycles in the dependency
-graph. Cycles are bad since topological sorts will not work in their presence.
-
-[h4 Makefiles and Graphs]
-The first step in implementing a make-ordering for source files is acquiring
-some data. For this example, we our program will parse files in a stripped down,
-Makefile-like format. The input looks something like something like this.
-
-[pre
-undirected_graph.hpp : adjacency_list.hpp
-directed_graph.hpp : adjacency_list.hpp
-movies.hpp : undirected_graph.hpp
-movies.cpp : movies.hpp tokenizer.hpp
-kevin_bacon.cpp : movies.hpp visitors.hpp breadth_first_search.hpp
-kevin_bacon.exe : movies.cpp kevin_bacon.cpp
-build_order.cpp : directed_graph.hpp topological_sort.hpp
-build_order.exe : build_order.cpp
-]
-
-Obviously, we're going to have to build a parser for this input format. Just as
-before our program starts by defining aliases for commonly used template types.
-
- struct Target;
-
- typedef boost::directed_graph<Target> Graph;
- typedef Graph::vertex_descriptor Vertex;
- typedef Graph::edge_descriptor Edge;
-
-In this graph, vertex properties are encapsulated in a `Target` structure. For
-this application, a target is any named file that might appear in the dependency
-graph. Unlike the previous example, we really don't have any need for edge propreties,
-so we can simply omit that template parameter. The `Target` is defined as:
-
- struct Target
- {
- int index;
- std::string name;
- };
-
-[note
-If you think you're seeing some similarities between the previous example, and this
-one... just wait. There are a number of common properties and tasks in many graph
-related problems such as indexing vertices, providing name labels, etc. Pay special
-attention to the method of adding vertices to the graph - the mapping of a unique
-name to a vertex is nearly ubiquitous in the setup of graph problems.
-]
-
-Likewise, we'll go ahead and predefine a property map that will be used later.
-We also need a mapping of target name to vertex so we don't duplicate vertices
-and have a convenient lookup tool later on.
-
- typedef boost::property_map<Graph::type, int Target::*>::type TargetIndexMap;
- typedef std::map<std::string, Vertex> TargetMap;
-
-We can now start building a program to parse the input data and build a dependency
-graph.
-
- using namespace std;
- using namespace boost;
-
- int main()
- {
- typedef char_separator<char> separator;
- typedef tokenizer<separator> tokenizer;
-
- Graph grapg;
- TargetMap targets;
-
- for(string line; getline(cin, line); ) {
- // skip comment and blank lines
- if(line[0] == '#' || line.empty()) {
- continue;
- }
-
- // split the string on the dependency
- size_t index = line.find_first_of(':');
- if(index == string::npos) {
- continue;
- }
- string target = trim_copy(line.substr(0, index));
- string deps = trim_copy(line.substr(index + 1));
-
- // add the target to the build graph
- Vertex u = add_target(graph, targets, target);
-
- // tokenize the dependencies
- separator sep(" \t");
- tokenizer tok(deps, sep);
- tokenizer::iterator i = tok.begin(), j = tok.end();
- for( ; i != j; ++i) {
- string dep = *i;
-
- // add this dependency as a target
- Vertex v = add_target(graph, targets, dep);
-
- // add the edge
- add_dependency(graph, u, v);
- }
- }
-
- // ...to be continued...
-
-This is a fairly large chunk of code that implements input parsing and graph construction
-with the help of the `add_target()` and `add_dependency()` functions. Essentially, this
-snippet creates a vertex (target) for each file named in the input file. A dependency
-edge is added between the first target (preceeding the ':' character) and each subsequent
-target (white space separated list following the ':'). The `add_target()` and `add_dependency()`
-method are implemented as:
-
- Vertex add_target(Graph& graph, TargetMap& targets, const string& name)
- {
- Vertex v;
- TargetMap::iterator it;
- bool inserted;
- tie(it, inserted) = targets.insert(make_pair(name, Vertex()));
- if(inserted) {
- v = add_vertex(graph);
- it->second = v;
-
- graph[v].index = num_vertices(graph) - 1;
- graph[v].name = name;
- }
- else {
- v = it->second;
- }
- return v;
- }
-
-You may notice that the `add_target()` function is nearly line-for-line identical to the
-`add_actor()` function in the previous example. This is no coincidence - both functions
-do exactly the same thing. They associate a vertex with a unique name and assign it an
-index that we can use later for various graph algorithms.
-
- Edge add_dependency(Graph& graph, Vertex u, Vertex v)
- {
- return add_edge(v, u, graph).first;
- }
-
-The `add_dependency()` method is considerably more terse than its undirected counter part,
-but essentially does the same thing. There is one very important difference, however:
-the direction of the edge is reversed to create a subtly different graph. Although
-the method is called to indicate that vertex `u` dependes on vertex `v`, the added edge
-actually indicates that vertex `v` satisfies the dependency of vertex `u`. In fact, this
-is the reverse of the original graph and is shown in Figure 2.
-
-[$images/guide/reverse.png]
-
-[h4 Obtaining the Make Order]
-We are now ready to compute the make order by running a topological sort. Thanks to a
-canned implementation, this is trivial.
-
- int main()
- {
- // ...continued from above...
-
- TargetIndexMap indices = get(&Target::index, graph);
-
- typedef list<Vertex> MakeOrder;
- MakeOrder order;
- topological_sort(graph, front_inserter(order), vertex_index_map(indices));
-
- BuildOrder::iterator i = order.begin(), j = order.end();
- for( ; i != j; ++i) {
- cout << graph[*i] << "\n";
- }
- }
-
-The `topological_sort()` algorithm takes an output iterator as the second parameter.
-Here, we use a standard front insertion iterator to prepend each target to the make
-order. The `vertex_index_map()` named parameter is also required for the implementation.
-After computation, we simply print the ordering to standard output.
-
-[h4 parallel Compilation]
-What if we have multiple processors available? Surely there is a way to determine if
-we can compile several independent files simultaneously, thereby reducing the overall
-build time. In fact, there is. Consider rephrasing the question to "what is the earliest
-time that a file can be built assuming that an unlimited number of files can be built
-at the same time?". In our simplified example, the only criteria for when a file can
-be built is that it has no dependencies (i.e., in edges). Further simplifiying the
-example, we assume that each file takes the same amount of time to build (1 time unit).
-
-For parallel compilation, we can build all files with zero dependencies in the first
-time unit at the same time. For each file, the time at which it can be built is one
-more than the maximum build time of the files on which it depends. In this example,
-`adjacency_list.hpp` is one of the files that will compile first (in parallel).
-The `directed_graph.hpp` file will compile in the second time step, and `build_order.cpp`
-in the third.
-
-To implement this, we need a vector that represents the time slots in which each vertex
-will be built. By visiting the vertices in topological order, we ensure that we can
-assigned the correct time slot to each vertex since values "propogate" down the ordering.
-Just for fun, we'll merge the time ordering with the output so we can see a) the order
-in which each file is built and b) the time slot it could be built in.
-
- int main()
- {
- // ...continued from above...
- vector<int> time(num_vertices(graph), 0);
- BuildOrder::iterator i = order.begin(), j = order.end();
- for( ; i != j; ++i) {
- int slot = -1;
- Graph::in_edge_iterator j, k;
- for(tie(j, k) = in_edges(*i, graph); j != k; ++j) {
- Vertex v = source(*j, graph);
- slot = std::max(time[graph[v].index], slot);
- }
- time[g[*i].index] = slot + 1;
-
- cout << g[*i].name << "\t[" << time[g[*i].index] << "]\n";
- }
- }
-
-This is a code may be a little dense, but demonstrates two important aspects of
-the Boost.Graph library. First this demonstrates the importantance of vertex
-indices. Despite their instability with mutable graphs, many (most?) graph algorithms
-use vertex indices to efficiently associate extra data with a vertex. In fact, this
-approach is so ubiquitous in the examples that it leads many to believe the
-`vertex_descriptor` is always the index of a vertex.
-
-[warning
-A `vertex_descriptor` is *not* its index in the graphs container of vectors!
-]
-
-The second important aspect this demonstrates is the construction of an /external
-property/ for vertices. Although we don't use the `time` vector in any additional
-computations, we could easily turn it into a property map for use with other
-algorithms.
-
-The output might something like this:
-
-[pre
-$ ./make_order < files
-topological_sort.hpp [0]
-breadth_first_search.hpp [0]
-visitors.hpp [0]
-tokenizer.hpp [0]
-adjacency_list.hpp [0]
-directed_graph.hpp [1]
-build_order.cpp [2]
-build_order.exe [3]
-undirected_graph.hpp [1]
-movies.hpp [2]
-kevin_bacon.cpp [3]
-movies.cpp [3]
-kevin_bacon.exe [4]
-]
-
-Although it probably won't since I doctored the tabbing for display purposes.
-
-[h4 Finding Cycles]
-Admittedly, cycles in dependency graphs for software probably don't occur so often
-that we need to develop special software to find them. However, if the dependency
-graph is big (think about all the source code, binaries, data files and thier
-dependencies that constitute a typical Linux distribution), then its possible that
-cycles creep into the graph. It might be nice to determine if there is such a cycle
-before actually trying to build it.
-
-To do this, we are going to provide a customized visitor for a depth-first search (DFS).
-Just like the custom visitors in our undirected graph examples, we overload a visitor
-event (here, the `back_edge` event) to indicate that a cycle has been found. Using the
-same setup as before, our visitor follows:
-
- struct CycleDetector : public dfs_visitor<>
- {
- CycleDetector(bool& c)
- : has_cycle(c)
- {}
-
- template <class Edge, class Graph>
- void back_edge(Edge, Graph&)
- {
- has_cycle = true;
- }
-
- bool& has_cycle;
- };
-
- CycleDetector detect_cycles(bool& c)
- { return CycleDetector(c); }
-
-That's it... When the `back_edge()` method is called, we know that a cycle exists
-in the graph. This literally indicates that there is an edge to a vertex that we
-have already visited, hence: a cycle. We also provide a helper function that
-instantiates the visitor.
-
-Using the cycle-detecting visitor is just as easy as before. After constructing the
-graph, we would find the following in the `main()` program.
-
- int main()
- {
- // ...continued from above...
-
- TargetIndexMap indices = get(&Target::index, g);
-
- bool cycle = false;
- depth_first_search(g,
- vertex_index_map(indices).
- visitor(detect_cycles(cycle)));
- cout << "has cycle: " << cycle << "\n";
- }
-
-Unfortunately, our test input file doesn't currently contain any cycles - a sign of
-good engineering - so we'll have to add one. Add the following lines to the input
-to create a completely superfluous cycle.
-
-[pre
-movies.exe : kevin_bacon.exe
-kevin_bacon.exe : movies.exe
-]
-
-Running the program on the modified input should yield:
-
-[pre
-$ ./cycle < files
-has cycle: 1
-]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,473 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Undirected Graphs]
-In this section, our example revolves around a particular type of /social network/.
-A social network is a graph that models the relationships between people. Specifically,
-in this example we are looking at a graph that connects co-stars of films.
-
-[h3 Co-Star Graphs]
-The first example problem we want to look at is the "Six Degrees of Kevin Bacon"
-problem. In this problem, two actors are related if they appear in the same movie,
-which can be trivially represented using an undirected graph.
-
-For the Six Degrees problem, we define a citation graph such that each vertex in
-the graph represents an actor, and each edge connects two actors if and only if
-they appear in the same movie. Consider the example in Figure 1. Here we have
-ten relatively well-known actors and the movies in which they appear together -
-and yes, Kevin Bacon is actually in /Animal House/ (he plays a snotty Omega pledge
-in his film debut).
-
-[$images/guide/movie.png]
-
-Although this is a relatively simple graph, it isn't hard to imagine that it
-scales up fairly quickly. Consider what would happen if we added all of Kevin
-Bacon's co-stars from major motion picture in which he starred - and all of
-their co-stars. It's not hard to imagine that only three iterations might
-actually encompass all of Hollywood and beyond (Bollywood?). So what can we do
-with these graphs?
-
-For starters, we can identify two different problems of the "Six Degrees".
-
-* How far is every actor in the graph from Kevin Bacon? This gives us the number
-of steps between Mr. Bacon and any other actor. The distances from a central actor
-can give clues to the size (especially the diameter) of a graph.
-* What is the "fastest" way to travel along the co-star graph from Kevin Bacon
-to any other actor? This is more commonly known as the "Six Degrees of Kevin
-Bacon Game".
-
-These are actually two different instances of the same problem and can be solved
-using the same algorithm - a simple breadth-first search (BFS).
-
-[note
-The term "six degrees of separation" refers to the total distance one must travel
-in a social network to get from one's self to any other person in the network.
-This notion is supported through a number of social experiments, namely that of
-Stanley Milgram who coined the term "small world" with respect to social networks.
-His experiment showed that Americans are connected, on average by six friendships.
-The notion of a "small world" social network is now nearly synonymous with a
-graph having an average degree of connectivity (formally known as its /mean geodesic
-distance/) of just six steps.
-
-On a side note, the name "Six Degrees of Kevin Bacon" can be attributed to a
-producer on /The Jon Stewart Show/ when the creators (students from Abright
-College) made an appearence to discuss and demonstrate the concept.
-]
-
-[h4 Actors, Movies, and Graphs]
-
-Our program begins by inlcuding required headers and creating some convenient
-type aliases.
-
- #include <string>
- #include <map>
- #include <boost/graph/undirected_graph.hpp>
- #include <boost/graph/breadth_first_search.hpp>
-
- struct Actor;
- struct Movie;
-
- typedef boost::undirected_graph<Actor, Movie> Graph;
- typedef Graph::vertex_descriptor Vertex;
- typedef Graph::edge_descriptor Edge;
-
-In this snippet, our `Actor` structure is going to represent the properties of each
-vertex in the graph while the `Movie` structure encapsulates edge information (i.e.,
-the movie that two actors appear in).
-
-The graph itself is defined by the type `boost::undirected_graph<Actor, Movie>`.
-Essentially, this states that each vertex will have properties given in the `Actor`
-structure, and that edges will have properties in the `Movie` structure. We also
-create some aliases for the graph's vertex and edge descriptors.
-
-[important
-Many of the examples in the Boost Graph Library treat vertex descriptors as the
-index of a vertex within the graph. It must be noted however, that this is not
-a reliable approach to indexing vertices and /will not/ work with the `undirected_graph`
-and `directed_graph` classes. Try to get in the habit of thinking of vertex and
-edge descriptors as opaque types and values - they are simply keys that provide
-access to the properties of their respective types.
-]
-
-In order to fully model our problem, we need to finish defining the `Actor` and
-`Movie` structures for our graph.
-
- struct Actor
- {
- int distance;
- std::string name;
- };
-
- struct Movie
- {
- std::string name;
- };
-
-In this example, we are "internalizing" a couple of properties for each vertex.
-The `Actor::distance` property will be used to record the distance from each actor
-to Kevin Bacon. The `Actor::name` and `Movie::name` properties should be fairly
-self-explanatory. However in this example, we are going to require that all actors
-have unique names. We'll see why in a bit.
-
-We're also going to define a number of other types related to the graphs properties:
-/property maps/. These maps provide a mechanism for accessing the interior and exterior
-properties of vertices and edges in a uniform manner. In this example, all of the
-vertex and edge properties are internal, but we could easily make them external and
-have the program run just as quickly.
-
- typedef boost::property_map<Graph, int Actor::*>::type ActorDistanceMap;
-
-The first template argument `Graph` defines the type of the graph that
-the property map is going to access. The second template argument with the somewhat
-peculiar syntax is the type of the property. These are pointers to `Actor` member
-variables of type `int`.
-
-Now that the preliminaries are out of the way, we need to concentrate on the construction
-of our graph. For this task, we're going to need another data structure that maps actor
-names to vertices in the graph. We're going to use this to prevent adding mulitple
-vertices for the same actor and later, to find the vertex in the graph that corresponds to
-Kevin Bacon.
-
-This program reads an input file from standard input. The input file is given in an edge-
-list format with semicolon separators. Each line corresponds to an edge, giving the two
-actors as the endpoints and the name of the movie they both appear in. For example:
-[pre
-Tim Matheson;Kevin Bacon;Animal House (1978)
-John Belushi;Kevin Bacon;Animal House (1978)
-Carrie Fisher;John Belushi;The Blues Brothers (1980)
-Mark Hamill;Carrie Fisher;Star Wars (1977)
-]
-
-The following function implements the input parser for the graph data.
-
- #include <boost/tokenizer.hpp>
-
- // the very important actor-to-vertex mapping
- typedef std::map<std::string, Vertex> ActorMap;
-
- using namespace std;
- using namespace boost;
-
- void build_costar_graph(istream& is, Graph& graph, ActorMap&)
- {
- // pull all of the data from std in.
- for(string line; getline(is, line); ) {
- // skip any comment or blank lines
- if(line[0] == '#' || line.empty()) {
- continue;
- }
-
- // tokenize the string
- char_delimiters_separator<char> sep(false, "", ";");
- tokenizer<> tok(line, sep);
- tokenizer<>::iterator i = tok.begin();
-
- // grab the names of the two actors and the movie title
- string first = *i++;
- string second = *i++;
- string movie = *i++;
-
- // get the vertices associated with the actors adding them
- // to the graph if necessary
- Vertex
- u = add_actor(g, actors, first),
- v = add_actor(g, actors, second);
-
- // create an edge (movie) linking the actors
- add_movie(g, u, v, movie);
- }
- }
-
-To finish graph construction, we need to implement the `add_actor()` and `add_movie()`
-functions:
-
- Vertex add_actor(Graph& graph, ActorMap& actors, const string& name)
- {
- // try inserting the actors name into the actors map
- Vertex v;
- ActorMap::iterator it;
- bool inserted;
- tie(it, inserted) = actors.insert(make_pair(name, Vertex()));
-
- if(inserted) {
- // if the vertex was inserted into the map, we need to
- // create a new vertex in the graph and make sure that
- // the map references the correct vertex
- v = add_vertex(graph);
- it->second = v;
-
- // configure the vertex properties
- g[v].name = name;
- }
- else {
- // otherwise, the name is already in the map, so
- // return the vertex associated with it
- v = it->second;
- }
-
- return v;
- }
-
- Edge add_movie(Graph& g, Vertex u, Vertex v, const string& movie)
- {
- Edge e;
- bool inserted;
- tie(e, inserted) = add_edge(u, v, g);
- if(inserted) {
- g[e].name = movie;
- }
- return e;
- }
-
-There are several important features of these two functions to pay special attention to.
-The first is the use of the `tie()` constructor. This is arguably one of the most useful
-and most used functions (it's actually a type) in Boost.Graph. It simply takes the
-values returned in a `std::pair` and assigns them to the variables passed to the
-constructor. In this function it is more or less equivalent to:
-
- std::pair<ActorMap::Iterator, bool> x = actors.insert(...);
- ActorMap::iterator iter = x.first;
- bool inserted = x.second;
-
-The second (and most important) is the assignment of the vertex properties. These
-two lines of code use the /bundled properties/ syntax to assign both an index
-and a name to the vertex that was just added to the graph.
-
-Our main program looks like this:
-
- int main()
- {
- Graph graph;
- ActorMap actors;
- build_costar_graph(cin, graph, actors);
-
- // ...to be continued...
- }
-
-[h4 Distance To Kevin Bacon]
-Now, all we have left to do is assign distances to Kevin Bacon. To do this, we're going
-to use a breadth-first search (starting from Kevin Bacon) and simply record the "depth"
-of each vertex as the distance from Kevin to every other actor. Fortunately, Boost.Graph
-gives us lots of help in this area so we don't have to write much more code. Let's look
-at the main program.
-
- int main()
- {
- // ...continued from above...
-
- // find kevin (our starting point)
- Vertex kevin = actors["Kevin Bacon"];
-
- // get a property map and zero out kevin's distance-to-self
- ActorDistanceMap distances = get(&Actor::distance, graph)
- distances[kevin] = 0;
-
- breadth_first_search(graph, kevin,
- visitor(
- make_bfs_visitor(record_distances(distances, on_tree_edge()))
- )
- );
-
- // ...to be continued...
-
-This is actually the "meat" of the solution. First, get a reference to the vertex that
-represents Kevin Bacon - our `ActorMap` is very good at this. Next we have to get the
-property map for our actor's distances so we can set Kevin's distance to zero. In this
-case, the actor's distance is actually a /bundled property/ of the `Actor` structure.
-
-Finally, we invoke the `breadth_first_search()` on `graph` with `kevin` as our starting
-vertex. The `visitor()` function is actually a /named parameter/ - a function that assigns
-a value to a parameter of an algorithm. In this case, the parameter is the /visitor/
-parameter (as indicated by the function name). The value is in turn provided by the
-`make_bfs_visitor()` function, which creates visitor object depnding on the parameters.
-The `record_distances()` function creates a `distance_recorder` visitor. The `distances`
-argument is our property map, indicating that the visitor will operate on those values.
-Finally, the `on_tree_edge()` call instructs the `distance_recorder` to record distances
-when a new edge in the BFS tree is encountered. This BFS visitor will effectively compute
-the distance from a root vertex to all other vertices in the graph.
-
-This is a somewhat verbose way of writing the code. We could write it a little more
-succinctly, although it's somewhat less readable:
-
- graph[kevin].distance = 0;
- breadth_first_search(graph, kevin,
- visitor(make_bfs_visitor(record_distances(get(&Actor::distance, graph), on_tree_edge())))
- );
-
-After finishing, each vertex's distance property will be assigned. All there is left to do
-is display the numbers:
-
- int main()
- {
- // ...continued from above...
- Graph::vertex_iterator i, j;
- for(tie(i, j) = vertices(g); i != j; ++i) {
- cout << graph[*i].distance << " : " << graph[*i].name << "\n";
- }
- }
-
-The output should look something like this (note that $ is a shell prompt):
-[pre
-$ ./kevin_bacon < movies
-1 : Chris Penn
-1 : Sarah Jessica Parker
-2 : James Belushi
-2 : David Ogden Stiers
-3 : Mark Hamill
-3 : Dan Akroyd
-1 : John Belushi
-1 : Tim Matheson
-2 : Tom Hulce
-2 : Peter Riegert
-2 : Karen Allen
-2 : Mike Meyers
-2 : Sylvester Stallone
-2 : Eddie Murphy
-]
-
-[h4 The Kevin Bacon Game]
-Using the above algorithm we can find how far away each actor is from Kevin Bacon, but what
-if we want to know how to get there. For example, we know that Dan Akroyd is three steps away
-so what are the movies? We could look at the input file, but that won't really give us any
-advantage. A better solution would be to modify the program to record the shortest paths.
-
-Since the term /shortest paths/ arises in the problem description, we might be tempted to
-use a shortest paths algorithm such as Dijkstra's. However, if we think about the problem a
-little bit, we should realize that there aren't any edge weights - something required for
-Dijkstra's algorithm. We could implicitly treat all edges as having a weight of one, but
-that turns out to be somewhat ineffective. It turns out that we can use the same BFS
-algorithm to record shortest paths instead of (or in addition to) actors' distances to
-Kevin Bacon. Specifically, we can record each the parent of each vertex in the BFS tree
-and simply backtrack from a given actor to Kevin Bacon.
-
-There are only a couple of modifications that we really need to make. First, we want to
-add an extra property for each actor: its parent vertex in the search tree. For convenience,
-we are also going to add a new property map type.
-
- struct Actor
- {
- // ...same as before...
- Vertex parent;
- };
-
- // ...
- typedef boost::property_map<Graph::type, &Vertex Actor::*>::type ActorParentMap;
-
-The only other changes are going to be in the `main()` program.
-
- int main(int argc, char *argv[])
- {
- string src = "Kevin Bacon";
- string tgt;
-
- if(argc < 2) {
- cerr << "usage: actor_paths actor [actor] < movies";
- return -1;
- }
- else if(argc == 2) {
- tgt = argv[1];
- }
- else {
- src = argv[1];
- tgt = argv[2];
- }
-
- Graph graph;
- ActorMap actors;
- build_costar_graph(cin, graph, actors);
-
- // ...to be continued...
-
-This program accepts a couple of command line parameters. If one actor is given then
-we find the path to Kevin Bacon. If two actors are given, we find the shortest path
-between the two actors. We can now get the vertices for specified actors, and find
-the paths between them.
-
- // ...continued from before...
- Vertex u = find_actor_vertex(g, actors, src);
- Vertex v = find_actor_vertex(g, actors, tgt);
- if(u == Graph::null_vertex()) {
- cerr << "could not find actor " << src << "\n";
- return -1;
- }
- if(v == Graph::null_vertex()) {
- cerr << "could not find actor " << tgt << "\n";
- return -1;
- }
-
- // get the parents map for later use.
- ActorParentMap parents = get(&Actor::parent, g);
-
- breadth_first_search(graph, kevin,
- visitor(
- make_bfs_visitor(record_predecessors(distances, on_tree_edge()))
- )
- );
-
- // ...to be continued...
-
-The `find_actor_vertex()` method is relatively trivial. We extracted it as a function
-so the program wouldn't be quite so repetitive.
-
- Vertex find_actor_vertex(const Graph& g, const ActorMap& actors, const std::string& name)
- {
- Vertex v = Graph::null_vertex();
- ActorMap::const_iterator i = actors.find(name);
- if(i != actors.end()) {
- v = i->second;
- }
- return v;
- }
-
-Otherwise, the code is essentially the same as above. In this case, we're constructing
-a `predecessor_recorder` as the visitor to the BFS. In contrast to the `distance_recorder`
-this method stores the parents (or predecessor) of each vertex in the BFS tree. This is
-an important property because it allows us to backtrack from one endpoint in the graph
-to the starting point, showing the path from, say Kevin Bacon to any another actor.
-
-Backtracking is relatively easy.
-
- int main(...)
- {
- // ...continued from before...
- while(v != u) {
- Vertex p = parents[v];
- string from = g[v].name;
- string to = g[p].name;
-
- // find the edge so we can print the movie
- Edge e;
- bool found;
- tie(e, found) = edge(v, p, g);
-
- string movie = g[e].name;
- cout << from << " starred with " << to << " in '" << movie << "'\n";
-
- v = p;
- }
-
- return 0;
- }
-
-Althgough we could simply backtrack over the parents and print the actors in a chain,
-we think it's more entertaining to know the movies that each pair co-stars in. To do
-this we use the `edge()` function to locate the edge corresponding edge connecting
-the two actors who costarred in a movie.
-
-The output might look something like:
-[pre
-$ ./six_degrees "Dan Akroyd" < movies
-Dan Akroyd starred with Carrie Fisher in 'The Blues Brothers (1980)'
-Carrie Fisher starred with Elisabeth Shue in 'Soapdish (1991)'
-Elisabeth Shue starred with Kevin Bacon in 'Hollow Man (2000)'
-]
-
-You now have a completely /unbeatable/ implementation of the "Six Degrees of Kevin
-Bacon" game - provided of course that you add a lot more movie data to the simple
-data set provided with this example.
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,400 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Adjacency List]
-
-[warning
-This reference is missing documentation for a number of associated types and
-methods.
-]
-
-[h4 Missing or Incorrect Documentation]
-* `edge_iterator`
-* `clear_in_edges()`
-* `clear_out_edges()`
-
-The adjacency_list class implements a generalized adjacency list graph structure.
-The template parameters provide many configuration options so that you can pick a
-version of the class that best meets your needs. An adjacency-list is basically a
-two-dimensional structure, where each element of the first dimension represents a
-vertex, and each of the vertices contains a one-dimensional structure that is its
-edge list. Figure 1 shows an adjacency list representation of a directed graph.
-
-The VertexList template parameter of the adjacency_list class controls what kind
-of container is used to represent the outer two-dimensional container. The
-OutEdgeList template parameter controls what kind of container is used to represent
-the edge lists. The choices for OutEdgeList and VertexList will determine the space
-complexity of the graph structure, and will determine the time complexity of the
-various graph operations. The possible choices and tradeoffs are discussed in
-Section Choosing the Edgelist and VertexList.
-
-The Directed template parameter controls whether the graph is directed, undirected,
-or directed with access to both the in-edges and out-edges (which we call
-bidirectional). The bidirectional graph takes up twice the space (per edge) of a
-directed graph since each edge will appear in both an out-edge and in-edge list.
-Figure 2 shows an adjacency list representation of an undirected graph.
-
-A tutorial on how to use the adjacency_list class is in Section Using adjacency_list.
-
-[h3 Template Parameters]
-[table
- [[Parameter] [Description] [Default]]
- [
- [`OutEdgeList`]
- [
- The selector for the container used to represent the edge-list for each
- of the vertices.
- ]
- [`vecS`]
- ]
- [
- [`VertexList`]
- [
- The selector for the container used to represent the vertex-list of the graph.
- ]
- [`vecS`]
- ]
- [
- [`Directed`]
- [
- A selector to choose whether the graph is directed, undirected, or
- directed with bidirectional edge access (access to both out-edges
- and in-edges). The options are directedS, undirectedS, and
- bidirectionalS.
- ]
- [`directedS`]
- ]
- [
- [`VertexProperties`]
- [Specifies internal properties for vertices.]
- [`no_property`]
- ]
- [
- [`EdgeProperties`]
- [Specifies internal properties for edges.]
- [`no_property`]
- ]
- [
- [`GraphProperties`]
- [Specifies internal properties for the graph object.]
- [`no_property`]
- ]
- [
- [`EdgeList`]
- [
- The selector for the container used to represent the edge-list for
- the graph.
- ]
- [`listS`]
- ]
-]
-
-[h4 Model of]
-VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable,
-and Serializable.
-
-[h4 Where Defined]
-
-`boost/graph/adjacency_list.hpp`
-
-The serialization functionality is in `boost/graph/adj_list_serialize.hpp`.
-
-[h3 Vertex and Edge Properties]
-Properties such as color, distance, weight, and user-defined properties can be
-attached to the vertices and edges of the graph using properties. The property
-values can be read from and written to via the property maps provided by the
-graph. The property maps are obtained via the get(property, g) function. How
-to use properties is described in Section Internal Properties . The property
-maps are objects that implement the interface defined in Section Property Map
-Concepts or may be bundled properties, which have a more succinct syntax. The
-types of all property values must be Copy Constructible, Assignable, and
-Default Constructible. The property maps obtained from the adjacency_list class
-are models of the Lvalue Property Map concept. If the adjacency_list is const,
-then the property map is constant, otherwise the property map is mutable.
-
-If the VertexList of the graph is vecS, then the graph has a builtin vertex
-indices accessed via the property map for the vertex_index_t property. The
-indices fall in the range [0, num_vertices(g)) and are contiguous. When a
-vertex is removed the indices are adjusted so that they retain these
-properties. Some care must be taken when using these indices to access exterior
- roperty storage. The property map for vertex index is a model of Readable
-Property Map.
-
-[h3 Iterator and Descriptor Stability/Invalidation]
-Some care must be taken when changing the structure of a graph (via adding or
-removing edges). Depending on the type of adjacency_list and on the operation,
-some of the iterator or descriptor objects that point into the graph may become
-invalid. For example, the following code will result in undefined (bad)
-behavior:
-
- typedef adjacency_list<listS, vecS> Graph; // VertexList = vecS
- Graph G(N);
-
- // Fill in the graph...
-
- // Attempt to remove all the vertices. Wrong!
- graph_traits<Graph>::vertex_iterator vi, vi_end;
- for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
- remove_vertex(*vi, G);
- }
-
- // Remove all the vertices. This is still wrong!
- graph_traits<Graph>::vertex_iterator vi, vi_end, next;
- tie(vi, vi_end) = vertices(G);
- for(next = vi; vi != vi_end; vi = next) {
- ++next;
- remove_vertex(*vi, G);
- }
-
-The reason this is a problem is that we are invoking remove_vertex(), which
-when used with an adjacency_list where VertexList=vecS, invalidates all
-iterators and descriptors for the graph (such as vi and vi_end), thereby
-causing trouble in subsequent iterations of the loop.
-
-If we use a different kind of `adjacency_list`, with `VertexList` as `listS`,
-then the iterators are not invalidated by calling remove_vertex unless the
-iterator is pointing to the actual vertex that was removed. The following code
-demonstrates this.
-
- typedef adjacency_list<listS, listS> Graph; // VertexList = listS
- Graph G(N);
-
- // Fill in the graph...
-
- // Attempt to remove all the vertices. Wrong!
- graph_traits<Graph>::vertex_iterator vi, vi_end;
- for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
- remove_vertex(*vi, G);
- }
-
- // Remove all the vertices. This is OK.
- graph_traits<Graph>::vertex_iterator vi, vi_end, next;
- tie(vi, vi_end) = vertices(G);
- for(next = vi; vi != vi_end; vi = next) {
- ++next;
- remove_vertex(*vi, G);
- }
-
-The stability issue also affects vertex and edge descriptors. For example,
-suppose you use vector of vertex descriptors to keep track of the parents
-(or predecessors) of vertices in a shortest paths tree (see
-`examples/dijkstra-example.cpp`). You create the parent vector with a call
-to dijkstra_shortest_paths(), and then remove a vertex from the graph.
-Subsequently you try to use the parent vector, but since all vertex descriptors
-have become invalid, the result is incorrect.
-
- std::vector<Vertex> parent(num_vertices(G));
- std::vector<Vertex> distance(num_vertices(G));
-
- dijkstra_shortest_paths(G, s,
- distance_map(&distance[0])
- .predecessor_map(&parent[0]));
-
- remove_vertex(s, G); // Bad idea! Invalidates vertex descriptors in parent vector.
-
- // The following will produce incorrect results
- for(tie(vi, vend) = vertices(G); vi != vend; ++vi) {
- std::cout << p[*vi] << " is the parent of " << *vi << std::endl;
- }
-
-Note that in this discussion iterator and descriptor invalidation is concerned
-with the invalidation of iterators and descriptors that are not directly
-affected by the operation. For example, performing `remove_edge(u, v, g)` will
-always invalidate any edge descriptor for /(u,v)/ or edge iterator pointing to
-/(u,v)/, regardless of the kind `adjacency_list`. In this discussion of iterator
-and descriptor invalidation, we are only concerned with the affect of
-`remove_edge(u, v, g)` on edge descriptors and iterators that point to other
-edges (not /(u,v)/).
-
-In general, if you want your vertex and edge descriptors to be stable (never
-invalidated) then use listS or setS for the VertexList and OutEdgeList template
-parameters of adjacency_list. If you are not as concerned about descriptor and
-iterator stability, and are more concerned about memory consumption and graph
-traversal speed, use vecS for the VertexList and/or OutEdgeList template
-parameters.
-
-The following table summarizes which operations cause descriptors and iterators
-to become invalid. In the table, OEL is an abbreviation for OutEdgeList and VL
-means VertexList. The "Adjacency Iterator" category includes the `out_edge_iterator`,
-`in_edge_iterator`, and `adjacency_iterator types`. A more detailed description of
-descriptor and iterator invalidation is given in the documentation for each
-operation.
-
-[table
- [[Function] [Vertex Descriptor] [Edge Descriptor] [Vertex Iterator] [Edge Iterator] [Adjacency Iterator]]
- [
- [`add_edge()`]
- [Valid]
- [Valid]
- [Valid]
- [OEL = `vecS` && [br] Directed = `directedS`]
- [OEL = `vecS`]
- ]
- [
- [
- `remove_edge()`[br]
- `remove_edge_if()`[br]
- `remove_out_edge_if()`[br]
- `remove_in_edge_if()`[br]
- `clear_vertex()`
- ]
- [Valid]
- [Valid]
- [Valid]
- [OEL = `vecS` && [br] Directed = `directedS`]
- [OEL = `vecS`]
- ]
- [
- [`add_vertex()`]
- [Valid]
- [Valid]
- [Valid]
- [Valid]
- [Valid]
- ]
- [
- [`remove_vertex()`]
- [VL = `vecS`]
- [VL = `vecS`]
- [VL = `vecS`]
- [VL = `vecS`]
- [VL = `vecS`]
- ]
-]
-
-[h3 Associated Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<adjancency_list>::vertex_descriptor`]
- [
- The type for the vertex descriptors associated with the `adjacency_list`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::edge_descriptor`]
- [
- The type for the edge descriptors associated with the `adjacency_list`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::vertex_iterator`]
- [
- The type for iterators returned by `vertices()`. The concept modeled by this
- type varies with the type of the `VertexList` parameter. If the `VertexList`
- selector is `vecS`, then this type models the `RandomAccessIterator` concept.
- In all other cases, it is a model of `BidirectionalIterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::out_edge_iterator`]
- [
- The type for iterators returned by `edges()`. The concept modeled by this type
- depends on the `OutEdgeList` parameter. If the selector is `vecS` then the
- iterator is a model of `RandomAccessIterator`. If the selector is `slistS`
- then it is a model of `ForwardIterator`. Otherwise, the iterator models
- `BidirectionalIterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::in_edge_iterator`]
- [
- This type is only valid if the `Directed` parameter is given as `bidirectionalS`.
- The concepts modeled by this type are the same as the `out_edge_iterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::adjacency_iterator`]
- [
- The type for iterators returned by `adjacent_vertices()`. The concepts modeled
- by this type are the same as `out_edge_iterator`. Dereferencing these types,
- however, will result in vertex descriptors rather than edge descriptors.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::inv_adjacency_iterator`]
- [
- The type for iterators returned by `inv_adjacent_vertices()`. The concepts
- modeled by this type are identical to hose of the `adjacency_iterator`.
- ]
- ]
- [
- [`graph_traits<adjancency_list>::directed_category`]
- [
- Provides inforamtion about whether the graph is undirected (`undirected_tag`),
- directed (`directed_tag`), or bidirectional (`bidirectional_tag`).
- ]
- ]
- [
- [`graph_traits<adjacency_list>::edge_parallel_category`]
- [
- This describes whether the class allows the insertion of parallel edges; those
- with the same source and target. When `EdgeList` is selected as `setS` or
- `hash_setS`, this type is set to `disallow_parallel_edge_tag`. Otherwise it
- is `allow_parallel_edge_tag`.
- ]
- ]
- [
- [`graph_traits<adjacency_list>::vertices_size_type`]
- [The type used for dealing with the number of vertices in the graph. ]
- ]
- [
- [`graph_traits<adjacency_list>::edge_size_type`]
- [The type used for dealing with the number of edges in the graph. ]
- ]
- [
- [`graph_traits<adjacency_list>::degree_size_type`]
- [The type used for dealing with the number of edges incident to a vertex in the graph. ]
- ]
- [
- [
- `property_map<adjacency_list, Property>::type` [br]
- `property_map<adjacency_list, Property>::const_type`
- ]
- [
- The property map type for vertex or edge properties in the graph. The specific
- property is specified by the `Property` template argument, and must match one of
- the properties specified in the `VertexProperties` or `EdgeProperties` for the
- graph.
- ]
- ]
- [
- [`graph_property<adjacency_list, Property>::type`]
- [
- The value type ofor the graph property specified by the `Property` parameter.
- ]
- ]
- [
- [`adjacency_list::out_edge_list_selector`]
- [The instantiated type of the `OutEdgeList` template parameter.]
- ]
- [
- [`adjacency_list::vertex_list_selector`]
- [The instantiated type of the `VertexList` template parameter.]
- ]
- [
- [`adjacency_list::directed_selector`]
- [The instantiated type of the `Directed` template parameter.]
- ]
- [
- [`adjacency_list::edge_list_selector`]
- [The instantiated type of the `EdgeList` template parameter.]
- ]
-]
-
-[h3 Member Functions]
-[table
- [[Member Function] [Description]]
- [
- [`adjacency_list(const GraphProperties& = GraphProperties()`]
- [
- The default constructor creates an empty graph with no vertices or edges.
- ]
- ]
-]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connected_components.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,95 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Connected Components]
-
- template <class Graph, class ComponentMap, class P, class T, class R>
- typename property_traits<ComponentMap>::value_type
- connected_components(const Graph &g, ComponentMap c,
- const bgl_named_params<P,T,R>& params = ``/defaults/``);
-
-
-The connected_components() functions compute the connected components of an undirected
-graph using a DFS-based approach. A connected component of an undirected graph is a
-set of vertices that are all reachable from each other. If the connected components
-need to be maintained while a graph is growing the disjoint-set based approach of
-function `incremental_components()` is faster. For "static" graphs this DFS-based
-approach is faster \[8\].
-
-The output of the algorithm is recorded in the component property map, which will
-contain numbers giving the component number assigned to each vertex. This algorithm
-returns the total number of connected components in the graph.
-
-[heading Where Defined]
-`boost/graph/connected_components.hpp`
-
-[heading Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [in] [`const Graph& g`]
- [
- The /undirected/ graph for which connected components are being found.
- This graph must be a model of VertexListGraph and Incidence Graph.
- ]
- ]
- [
- [out] [`ComponentMap c`]
- [
- The algorithm computes how many connected components are in the graph,
- and assigning each component an integer label. The algorithm then records
- which component each vertex in the graph belongs to by recording the
- component number in the component property map. The ComponentMap type
- must be a model of WritablePropertyMap. The value type shouch be an
- integer type, preferably the same as the `vertices_size_type` of the
- graph. The key type must be the graph's `vertex_descriptor` type.
- ]
- ]
-]
-
-[heading Named Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [util] [`color_map(ColorMap color)`]
- [
- This is used by the algorithm to keep track of its progress through the
- graph. The type ColorMap must be a model of ReadWritePropertyMap and
- its key type must be the graph's `vertex_descriptor` type and the value
- type of the color map must model ColorValue.
-
- *Default* An `iterator_property_map` create from a `std::vector` of
- `default_color_type` of size `num_vertices(g)` and using `index_map` as
- the index map (to access colors for a vertex).
- ]
- ]
- [
- [in] [`vertex_index_map(VertexIndexMap index_map)`]
- [
- This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
- This parameter is only necessary when the default color property map is
- used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
- value type of the map must be an integer type. The vertex descriptor type
- of the graph needs to be usable as the key type of the map.
-
- *Default* `get(vertex_index, g)`. Note if you use this default, make sure
- that your graph has an interior `vertex_index` property. For example
- `adjacency_list` with `VertexList=listS` does not have an interior
- `vertex_index` property.
- ]
- ]
-]
-
-[heading Complexity]
-This algorithm runs in /O(V + E)/.
-
-[heading Notes]
-This algorithm will not compile if passed a /directed/ graph.
-
-[heading Examples]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_connectivity.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,28 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Connectivity Measures]
-
-Reference for connectivity measures. Apparently, these are just going to be
-simple wrappers around connected_components or strong_components to provide
-some extra information. These might include:
-
-* `is_connected()`, `is_strongly_connected()`
-* `largest_connected_component()`, `largest_strong_component()`
-
-We might extend these for biconnected components also. Essentially, these
-functions take the component map computed by the connectivity stuff as
-an input and produce results. If the connectivity map isn't provided,
-we could compute it on the fly.
-
-[Examples]
-
-``
- connected_comp
-``
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_directed_graph.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,756 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Directed Graph]
-This section provides detailed information about the `directed_graph` class,
-its associated types, member functions and non-member interface.
-
-[h4 Notation]
-The following notation is used in this documentation. The following type names
-are generally meant to mean the following:
-[table
- [[Used Type] [Actual Type]]
- [
- [`directed_graph`]
- [
- `directed_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
- arguments that correspond to user-defined or default verex properties,
- edge properties, and graph properties.
- ]
- ]
- [
- [`vertex_descriptor`]
- [`directed_graph<VP,EP,GP>::vertex_descriptor`]
- ]
- [
- [`edge_descriptor`]
- [`directed_graph<VP,EP,GP>::edge_descriptor`]
- ]
- [
- [`vertex_iterator`]
- [`directed_graph<VP,EP,GP>::vertex_iterator`]
- ]
- [
- [`edge_iterator`]
- [`directed_graph<VP,EP,GP>::edge_iterator`]
- ]
-]
-
-Moreover, objects with the following names are generally expected to have the
-following types.
-
-[table
- [[Object Name] [Type]]
- [[`g`] [`directed_graph`]]
- [[`u`, `v`] [`vertex_descriptor`]]
- [[`e`] [`edge_descriptor`]]
- [[`i`] [`vertex_iterator` or `edge_iterator`]]
- [[`p`] [A property tag (usually a template parameter)]]
- [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
- [[`v`] [The value of a property (usually a template parameter)]]
-]
-
-[h4 Vertex and Edge Storage]
-The `directed` graph class has four distinct storage compontents: one for each
-of vertices, edges, out-edges per vertex, and in-edges per vertex. Each of these
-storage components uses a `std::list`. This is important to remember when
-considering the performance of oeprations on these graphs.
-
-Note that mutating (modifying) edge operations on a graph must operate on three
-different lists. For example, adding an edge to the graph will insert the edge
-or descriptors into the edge list, the out-edge list of the source vertex, and
-the in-edge list of the target vertex. These lists are accessible via the
-`edges(g)`, `out_edges(v,g)`, and `in_edges(v,g)` respectively.
-
-[h4 Descriptor and Iterator Stability]
-With the `directed_graph` class, descriptors and iterators remain stable after
-most operations. This is to say that removing a vertex or edge will not invalidate
-descriptors and iterators to other vertices or edges except for the edge or
-vertex that was actually removed.
-
-[h4 Vertex Indexing and Stability]
-The `directed_graph` class provides a built-in internal properties for vertex
-types, and will provide some degree of automated index management. Algorithms
-that use vertex indices generally assume that they are in the range
-\[0, `num_vertices(g)`). With the `directed_graph` class vertex indices will
-be in this continuous range until a vertex is removed from the graph. This is
-the only operation that invalidates vertex indices, but the vertices will need
-to be renumbered using the `renumber_vertex_indices()` function.
-
-[h4 Template Parameters]
-There are three parameters to the `directed_graph` class.
-[table
- [[Parameter] [Description] [Default]]
- [
- [`VertexProperties`]
- [Specifies internal properties for vertices of the graph.]
- [`no_property`]
- ]
- [
- [`EdgeProperties`]
- [Specifies internal properties for edges of the graph.]
- [`no_property`]
- ]
- [
- [`GraphProperties`]
- [Specifies internal properties for the graph itself.]
- [`no_property`]
- ]
-]
-
-[h5 Model Of]
-VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
-
-[h5 Where Defined]
-`boost/graph/directed_graph.hpp`
-
-[h4 Associated Types]
-There are a number of useful types associated with the `directed_graph` class.
-Most of these are accessed through `graph_traits` or other template classes.
-For convenience these types have been grouped by purpose.
-
-[h5 Descriptor Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<directed_graph>::vertex_descriptor`]
- [
- The type for the vertex descriptors associated with the graph.
- ]
- ]
- [
- [`graph_traits<directed_graph>::edge_descriptor`]
- [
- The type for the edge descriptors associated with the graph.
- ]
- ]
-]
-
-[h5 Iterator Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<directed_graph>::vertex_iterator`]
- [
- The type for iterators returned by `vertices()`. Verex iterators are
- models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<directed_graph>::edge_iterator`]
- [
- The type for iterators returned by `edges()`. Edge iterators are
- models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<directed_graph>::out_edge_iterator`]
- [
- The type for iterators returned by `out_edges()`. Out-edge iterators
- are models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<directed_graph>::in_edge_iterator`]
- [
- The type for iterators returned by `in_edges()`. In-edge iterators
- are models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<directed_graph>::adjacency_iterator`]
- [
- The type for iterators returned by `adjacent_vertices`. Adjacency
- iterators are models of the `BidirectionalIterator` concept.
- ]
- ]
-]
-
-[h5 Miscellaneous Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<directed_graph>::vertices_size_type`]
- [The type used for dealing with the number of vertices in the graph.]
- ]
- [
- [`graph_traits<directed_graph>::edge_size_type`]
- [The type used for dealing with the number of edges in the graph.]
- ]
- [
- [`graph_traits<directed_graph>::degree_size_type`]
- [The type used for dealing with the number of edges incident to a vertex in the graph.]
- ]
- [
- [`directed_graph::vertex_index_type`]
- [The integral type representing vertex indices (generally `unsigned int`).]
- ]
- [
- [
- `property_map<directed_graph, Property>::type`
-
- `property_map<directed_graph, Property>::const_type`
- ]
- [
- The property map type for vertex or edge properties in the graph. The specific
- property is specified by the `Property` template argument, and must match one of
- the properties specified in the `VertexProperties` or `EdgeProperties` for the
- graph.
- ]
- ]
- [
- [`graph_property<directed_graph, Property>::type`]
- [
- The value type for the graph property specified by the `Property` parameter.
- `Property` must be one of the types in the `GraphProperties` template argument.
- ]
- ]
- [
- [`graph_traits<directed_graph>::directed_category`]
- [
- This is always `bidirectional_tag`, indicating that the graph supports in- and
- out-edge operations.
- ]
- ]
- [
- [`graph_traits<directed_graph>::edge_parallel_category`]
- [
- This is always `allow_parallel_edges_tag`, indicating that multiple edges
- may be added between two vertices (i.e., graphs can be /multigraphs/).
- ]
- ]
-]
-
-[h4 Member Functions]
-[table
- [[Function] [Description]]
- [
- [
-``
-directed_graph(const GraphProperties& p = GraphProperties())
-``
- ]
- [The default constructor creates a graph with no vertices or edges.]
- ]
- [
- [
-``directed_graph(const directed_graph& g)
-``
- ]
- [The copy constructor creates a copy of the given graph `g`.]
- ]
- [
- [
-``
-directed_graph(vertices_size_type n,
- const GraphProperties& p = GraphProperties())
-``
- ]
- [The default constructor creates a graph with `n` vertices and no edges.]
- ]
- [
- [
-``directed_graph& operator =(const directed_graph& g)
-``
- ]
- [Copies the edges and vertices of the graph `g`.]
- ]
-]
-
-[h4 Non-member Functions]
-[h5 Non-member Accessors]
-[table
- [[Function] [Description]]
- [
- [
-``
-std::pair<vertex_iterator, vertex_iterator>
-vertices(const directed_graph& g)
-``
- ]
- [Returns an iterator range providing access to the vertex list of `g`.]
- ]
- [
- [
-``
-std::pair<edge_iterator, edge_iterator>
-edges(const directed_graph& g)
-``
- ]
- [Returns an iterator range providing access to the edge list of `g`.]
- ]
- [
- [
-``
-std::pair<out_edge_iterator, out_edge_iterator>
-out_edges(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns an iterator range providing access to the out-edges of
- vertex `v` in the graph `g`.
- ]
- ]
- [
- [
-``
-std::pair<in_edge_iterator, in_edge_iterator>
-in_edges(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns an iterator range providing access to the in-edges of
- vertex `v` in the graph `g`.
- ]
- ]
- [
- [
-``
-std::pair<adjacency_iterator, adjacency_iterator>
-adjacent_vertices(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns an iterator range providing access to the adjacenct vertices
- of vertex `v` in the graph `g`. Note that this is functionally
- equivalent to iterating over the targets of all out-edges of `v`.
- ]
- ]
- [
- [
-``
-vertices_size_type
-num_vertices(const directed_graph& g)
-``
- ]
- [Returns the number of vertices in the graph `g`.]
- ]
- [
- [
-``
-edge_size_type
-num_edges(const directed_graph& g)
-``
- ]
- [Returns the number of edges the graph `g`.]
- ]
- [
- [
-``
-degree_size_type
-degree(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns the total degree of vertex `v` in the graph `g`. This is
- functionally equivalent `out_degree(v,g) + in_degree(v,g)`.
- ]
- ]
- [
- [
-``
-degree_size_type
-out_degree(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns the out-degree of vertex `v` in the graph `g`. In an
- `directed_graph` this is equal to `in_degree(v, g)`.
- ]
- ]
- [
- [
-``
-degree_size_type
-in_degree(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns the in-degree of vertex `v` in the graph `g`. In an
- `directed_graph` this is equal to `out_degree(v, g)`.
- ]
- ]
- [
- [
-``
-vertex_descriptor
-vertex(vertices_size_type n
- const directed_graph& g)
-``
- ]
- [
- Returns the /nth/ vertex in the graph `g`. With directed graphs,
- this method is /O(n)/. As such its use with this type of graph is
- discouraged.
- ]
- ]
- [
- [
-``
-std::pair<edge_descriptor, bool>
-edge(vertex_descriptor u,
- vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- If the edge /(u,v)/ is in `g`, then this function returns the
- descriptor for the edge connecting `u` and `v` with boolean value
- set to `true`. Otherwise, the boolean value is `false` and the
- edge descriptor is invalid.
- ]
- ]
- [
- [
-``
-vertex_size_type
-get_vertex_index(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns the vertex index of the given vertex descriptor v. Note
- that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
- This function is an alias for `get(vertex_index,g,v)`.
- ]
- ]
- [
- [
-``
-vertex_size_type
-max_vertex_index(vertex_descriptor v,
- const directed_graph& g)
-``
- ]
- [
- Returns the vertex index of the given vertex descriptor v. Note
- that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
- This function is an alias for `get(vertex_index,g,v)`.
- ]
- ]
-]
-
-[h5 Non-member Modifiers]
-[table
- [[Function] [Description]]
- [
- [
-``
-vertex_descriptor
-add_vertex(directed_graph& g)
-``
- ]
- [Adds a vertex to `g` and returns a descriptors for the new vertex.]
- ]
- [
- [
-``
-void
-clear_vertex(vertex_descriptor v,
- directed_graph& g)
-``
- ]
- [
- Removes all in- and out-edges of `v`, but leaves `v` in the graph `g`.
- This is functioanlly equivalent to invoking `remove_edge()` on all
- in- or out-edges of `v`, invalidating descriptors and iterators that
- reference edges incident to `v`.
- ]
- ]
- [
- [
-``
-void
-clear_out_edges(vertex_descriptor v,
- directed_graph& g)
-``
- ]
- [
- Removes all out-edges from vertex `v`, but does not remove the vertex
- itself. This is functionally equivalent to calling `remove_edge()` for
- all out-edges of `v`, invalidating any descriptors and iterators that
- reference edges incident to that vertex.
- ]
- ]
- [
- [
-``
-void
-clear_in_edges(vertex_descriptor v,
- directed_graph& g)
-``
- ]
- [
- Removes all in-edges from vertex `v`, but does not remove the vertex
- itself. This is functionally equivalent to calling `remove_edge()` for
- all in-edges of `v`, invalidating any descriptors and iterators that
- reference edges incident to that vertex.
- ]
- ]
- [
- [
-``
-vertex_descriptor
-remove_vertex(vertex_descriptor v,
- directed_graph& g)
-``
- ]
- [
- Removes vertex `v` from the graph `g`. It is assumed that `v` has no
- incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
- before removing it.
-
- Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
- before calling this method, this operation will invalidate all vertex indices
- in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
- be renumbered using the `renumber_vertex_indices(g)` method. If possible,
- prefer to remove groups of vertices at one time before renumbering since
- renumbering is a /O(n)/ time operation.
- ]
- ]
- [
- [
-``
-void
-remove_vertex_and_renumber_indices(vertex_iterator i,
- directed_graph& g)
-``
- ]
- [
- Removes the vertex indicated by the iterator `i` from the graph `g`. Like
- the `remove_vertex(v,g)` function, it is expected that `*i` have no
- incident edges at the time of removal.
-
- As indicated by the name, this method will also renumber vertex indices
- after the removal of `*i`. This operation iterates over vertices after
- `i`, decrementing their index by 1. If your program removes several
- vertices at once, prefer to call several `remove_vertex(v,g)` methods,
- followed by `renumber_vertices(g)` before using `g` in an algorithm.
- ]
- ]
- [
- [
-``
-void
-renumber_vertex_indices(directed_graph& g)
-``
- ]
- [
- Renumbers all interior vertex indices such that each vertex has an index
- in the range \[0, `num_vertices(g)`). Generally, this function needs to
- be called after removing vertices and before invoking different graph
- algorithms.
- ]
- ]
- [
- [
-``
-std::pair<edge_descriptor, bool>
-add_edge(vertex_descriptor u,
- vertex_descriptor v,
- directed_graph& g)
-``
- ]
- [
- Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
- edge. For `directed_graph`s, the boolean value of the pair will always
- be true.
- ]
- ]
- [
- [
-``
-void
-remove_edge(vertex_descriptor u,
- vertex_descriptor v,
- directed_graph& g)
-``
- ]
- [
- Removes the edge /(u,v)/from the graph. This operation invalidates any
- descriptors or iterators referencing the edge. Note that `u` and `v` must
- be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
- (with multiple edges between /(u,v)/, this mehtod will cause the removal of
- all such edges connecting `u` and `v`.
- ]
- ]
- [
- [
-``
-void
-remove_edge(edge_descriptor e,
- directed_graph& g)
-``
- ]
- [
- Removes the edge `e` from the graph. If multuple edges exist from
- /(`source(e,g)`, `target(e,g)`)/, then this method will remove only
- the single, specified edge.
- ]
- ]
- [
- [
-``
-void
-remove_edge(out_edge_iterator i,
- directed_graph& g)
-``
- ]
- [
- This is functionally equivalent to `remove_edge(*i, g)`.
- ]
- ]
- [
- [
-``
-void
-remove_edge_if(Predicate p,
- directed_graph& g)
-``
- ]
- [
- Removes all edges from the graph that satisfy `predicate`. That is, if
- `p()` returns true when applied to an edge, then that edge is removed.
- The affect on descriptor and iterator is the same as that of invoking
- `remove_edge()` for on each of the removed vertices.
- ]
- ]
- [
- [
-``
-template <class Predicate>
-void
-remove_out_edge_if(vertex_descriptor v,
- Predicate p,
- directed_graph& g)
-``
- ]
- [
- Removes all edges out-edges from vertex`v` that satisfy `predicate`.
- That is, if `p()` returns true when applied to an edge, then that edge
- is removed. The affect on descriptor and iterator is the same as that
- of invoking `remove_edge()` for on each of the removed vertices.
- ]
- ]
- [
- [
-``
-template <class Predicate>
-void
-remove_in_edge_if(vertex_descriptor v,
- Predicate p,
- directed_graph& g)
-``
- ]
- [
- Removes all edges in-edges from vertex`v` that satisfy `predicate`.
- That is, if `p()` returns true when applied to an edge, then that edge
- is removed. The affect on descriptor and iterator is the same as that
- of invoking `remove_edge()` for on each of the removed vertices.
- ]
- ]
-]
-
-[h5 Proprety Map Acessors]
-[table
- [[Function] [Description]]
- [
- [
-``
-template <class Property>
-property_map<directed_graph, Property>::type
-get(Property, directed_graph& g)
-``
-
-``
-template <class Property>
-property_map<directed_graph, Property>::const_type
-get(Property, const directed_graph& g)
-``
- ]
- [
- Returns the property map object for the vertex property specified by the
- type `Property`. This type must match one of the properties specified in
- the `VertexProperties` template argument.
- ]
- ]
- [
- [
-``
-template <class Property, class Descriptor>
-typename
- property_traits<
- property_map<directed_graph, Property>::const_type
- >::value_type
-get(Property,
- const directed_graph& g,
- Descriptor d)
-``
- ]
- [
- Returns the property value specified by the type `Property` for either
- the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
- ]
- ]
- [
- [
-``
-template <class Property, class Descriptor, class Value>
-void
-put(Property,
- const directed_graph& g,
- Descriptor d,
- Value v)
-``
- ]
- [
- Sets the property value denoted by the type `Property` for either edge
- or vertex descriptor `d` to the given value `v`.
- ]
- ]
- [
- [
-``
-template <class GraphProprety>
-typename graph_property<directed_graph, GraphProperty>::type&
-get_property(directed_graph& g, GraphProperty)
-``
-
-``
-template <class GraphProprety>
-const typename graph_property<directed_graph, GraphProperty>::type&
-get_property(const directed_graph& g, GraphProperty)
-``
- ]
- [
- Returns the graph property specified by the type `GraphProperty` for
- the graph `g`.
- ]
- ]
- [
- [
-``
-template <class GraphProprety, class Value>
-void
-set_property(const directed_graph& g, GraphProperty, Value v)
-``
- ]
- [
- Sets the graph proeprty specified by the type `GraphProperty` to
- the given value `v`. Note that `GraphProperty` must be one of
- the properties in the `GraphProperties` template argument.
- ]
- ]
-]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_distributions.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,128 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Degree Distributions]
- template <class Graph, class DistributionMap>
- void degree_distribution(const Graph &g, DistributionMap& dist);
-
- template <class Graph, class DistributionMap>
- void in_degree_distribution(const Graph &g, DistributionMap& dist);
-
- template <class Graph, class DistributionMap>
- void out_degree_distribution(const Graph &g, DistributionMap& dist);
-
-
- template <class Graph, class HistogramMap>
- void degree_histogram(const Graph &g, HistogramMap& dist);
-
- template <class Graph, class HistogramMap>
- void in_degree_histogram(const Graph &g, HistogramMap& dist);
-
- template <class Graph, class HistogramMap>
- void out_degree_histogram(const Graph &g, HistogramMap& dist);
-
-The degree distribution functions compute statistical distributions of the degrees
-of vertices in a graph. In addition to the degree distribution, different algorithms
-allow for the computation in-degree and out-degree distributions.
-
-The histogramming functions compute historgrams, associating each vertex in
-the graph with its degree in the distribution.
-
-[heading Where Defined]
-`boost/graph/degree_distribution.hpp`
-
-[heading Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [in] [`const Graph& g`]
- [
- The graph object for which the distribution will be computed. For
- `degree_distributions()` and `in_degree_distribution()`, `g` must
- be a model of a BidirectionalGraph. For `out_degree_distribution()`,
- `g`, must model the IncidenceGraph concept.
- ]
- ]
- [
- [out] [`DistributionMap& dist`]
- [
- The distribution parameter maps instances of degrees (numerically)
- to the number of vertices in the graph that exhibit that degree.
-
- The distribution output parameter has a number of strict typ requirements.
- First, it must be a model of the Sequence concept, specifically providing
- a `resize()` member function. They key (or index) type of this parameter
- should be the same as `degree_size_type` of the graph. Finally, the
- `value_type` of this method should be an integer type (preferrably
- unsigned). It is recommended to use `std::vector<degree_size_type>` for
- this parameter.
- ]
- ]
- [
- [out] [`HistogramMap& hist`]
- [
- The histogram parameter maps instances of degrees (numerically) to the
- set of vertices that exhibit that degree.
-
- The histogram parameter has fairly stringent type requirements due to
- its structure. First, the parameter must model the Sequence concept,
- providing a `resize()` member function. Seocnd, the key (index) of
- the type should be the same as `degree_size_type` of the graph. The
- `value_type` of this is required to model the BackInsertionSequence,
- and the `value_type` of that /must/ be the same as the `vertex_descriptor`
- of the graph parameter.
- ]
- ]
-]
-
-[heading Complexity]
-The complexity of this function is /O(V)/.
-
-[heading Notes]
-Because a graph may be a multigraph, there is no determinable upper bound on the
-size of the distribution or histogram parameters. As such they are required to
-be dynamically resized during the execution of the algorithm.
-
-For the distribution parameter, we recommend `std::vector<size_t>`. This satisfies
-all the requirements. For the histogram, we recommend using a `std::vector<Sequence<Vertex> >`
-where `Sequence` is one of `std::list`, `std::vector`, `std::deque`, or `std::queue`. The
-choice doesn't make much difference except that a `std::list` will require more allocations,
-but a `std::vector` will require more space. The `Vertex` type must be
-`graph_traits<Graph>::vertex_descriptor`.
-
-If `dist` is the name of the output distribution after a call to `degree_distribution()`
-then the maximum degree is `dist.size() - 1`. The minimum degree corresponds to the index
-in `dist` with the first non-zero value.
-
-[heading Examples]
-The first example show how to compute and print the degree distribution. Each
-element in the returned distribution corresponds to the number of instances
-of
-
- undirected_graph<> g;
- // add vertices and edges to g
-
- std::vector<size_t> dist;
- degree_distribution(g, dist);
- copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
-
-
-The following example shows how to access the vertex (or vertices) with the maximum
-degree by using the `degree_histogram()` algorithm. This prints the index of that
-vertex.
-
- undirected_graph<> g;
- // add vertice and edges to g
-
- typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
- typedef std::list<vertex_type> vertex_list;
-
- std::vector<vertex_list> hist;
- degree_histogram(g, hist);
- cout << get_vertex_index(hist.back().back()) << "\n";
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_strong_components.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,116 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Strongly Connected Components]
-
- template <class Graph, class ComponentMap, class P, class T, class R>
- typename property_traits<ComponentMap>::value_type
- strong_components(const Graph &g, ComponentMap c,
- const bgl_named_params<P,T,R>& params = ``/defaults/``);
-
-The `strong_components()` functions compute the strongly connected components of a
-directed graph using Tarjan's algorithm based on DFS \[41\].
-
-The output of the algorithm is recorded in the component property map, which will
-contain numbers giving the component number assigned to each vertex. This algorithm
-returns the number of strongly connected components in the graph.
-
-[heading Where Defined]
-`boost/graph/strong_components.hpp`
-
-[heading Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [in] [`const Graph& g`]
- [
- The /directed/ graph for which connected components are being found.
- This graph must be a model of VertexListGraph and Incidence Graph.
- ]
- ]
- [
- [out] [`ComponentMap c`]
- [
- The algorithm computes how many connected components are in the graph,
- and assigning each component an integer label. The algorithm then records
- which component each vertex in the graph belongs to by recording the
- component number in the component property map. The ComponentMap type
- must be a model of WritablePropertyMap. The value type shouch be an
- integer type, preferably the same as the `vertices_size_type` of the
- graph. The key type must be the graph's `vertex_descriptor` type.
- ]
- ]
-]
-
-[heading Named Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [util] [`root_map(RootMap root_map)`]
- [
- This is used by the algorithm to record the candidate root vertex for each
- vertex. By the end of the algorithm, there is a single root vertex for each
- component and `get(root_map, v)` returns the root vertex for whichever
- component vertex `v` is a member. The `RootMap` must be a ReadWritePropertyMap,
- where the key type and the value type are the vertex descriptor type of the
- graph.
-
- *Default* An iterator_property_map created from a `std::vector` of
- `vertex_descriptor`s of size `num_vertices(g)` and using the `index_map`
- for accessing root vertices.
- ]
- ]
- [
- [util] [`discover_time_map(TimeMap time_map)`]
- [
- This is used by the algorithm to keep track of the DFS ordering of the vertices.
- The `TimeMap` must be a model of ReadWritePropertyMap and its value type must
- be an integer type. The key type must be the vertex descriptor type of the graph.
-
- *Default* An iterator_property_map created from a `std::vector` of integers
- of size `num_vertices(g)` and using the `index_map` for accessing root vertices.
- ]
- ]
- [
- [util] [`color_map(ColorMap color)`]
- [
- This is used by the algorithm to keep track of its progress through the
- graph. The type ColorMap must be a model of ReadWritePropertyMap and
- its key type must be the graph's `vertex_descriptor` type and the value
- type of the color map must model ColorValue.
-
- *Default* An `iterator_property_map` create from a `std::vector` of
- `default_color_type` of size `num_vertices(g)` and using `index_map` as
- the index map (to access colors for a vertex).
- ]
- ]
- [
- [in] [`vertex_index_map(VertexIndexMap index_map)`]
- [
- This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
- This parameter is only necessary when the default color property map is
- used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
- value type of the map must be an integer type. The vertex descriptor type
- of the graph needs to be usable as the key type of the map.
-
- *Default* `get(vertex_index, g)`. Note if you use this default, make sure
- that your graph has an interior `vertex_index` property. For example
- `adjacency_list` with `VertexList=listS` does not have an interior
- `vertex_index` property.
- ]
- ]
-]
-
-[heading Complexity]
-This algorithm runs in /O(V + E)/.
-
-[heading Notes]
-This algorithm will not compile if passed a /directed/ graph.
-
-[heading Examples]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,718 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Undirected Graph]
-This section provides detailed information about the `undirected_graph` class,
-its associated types, member functions and non-member interface.
-
-[h4 Notation]
-The following notation is used in this documentation. The following type names
-are generally meant to mean the following:
-[table
- [[Used Type] [Actual Type]]
- [
- [`undirected_graph`]
- [
- `undirected_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
- arguments that correspond to user-defined or default verex properties,
- edge properties, and graph properties.
- ]
- ]
- [
- [`vertex_descriptor`]
- [`undirected_graph<VP,EP,GP>::vertex_descriptor`]
- ]
- [
- [`edge_descriptor`]
- [`undirected_graph<VP,EP,GP>::edge_descriptor`]
- ]
- [
- [`vertex_iterator`]
- [`undirected_graph<VP,EP,GP>::vertex_iterator`]
- ]
- [
- [`edge_iterator`]
- [`undirected_graph<VP,EP,GP>::edge_iterator`]
- ]
-]
-
-Moreover, objects with the following names are generally expected to have the
-following types.
-
-[table
- [[Object Name] [Type]]
- [[`g`] [`undirected_graph`]]
- [[`u`, `v`] [`vertex_descriptor`]]
- [[`e`] [`edge_descriptor`]]
- [[`i`] [`vertex_iterator` or `edge_iterator`]]
- [[`p`] [A property tag (usually a template parameter)]]
- [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
- [[`v`] [The value of a property (usually a template parameter)]]
-]
-
-[h4 Duplicitous Operations]
-Many of the original operations in the Boost Graph library are named in accordance
-with the terminology for directed graphs, specifically the use of out-edges as
-the canonical adjacencty list for vertices. As a result, undirected graphs also
-use the out-edge terminology to refern to its incident edges, but in-edge operations
-are identical in behavior to out-edge operations.
-
-There are three sets of operations that have multiple names and duplicate behavior:
-`*degree()`-computing functions, `*_edge()`-iterating accessors, and the `remove_*_edge()`
-predicate-based functions. These functions are grouped together in their reference
-sections.
-
-This class also introduces two new functions, `incident_edges(g)` that returns an
-iterator range to the incident edges of `g`, and `remove_incident_edges_if(v,p,g)`.
-These are identical in behavior to their `in` and `out` counterparts. These
-functions are only provided for semantic consistency so developers should be aware
-that these new functions are /not/ defined for any other graph classes in the
-Boost Graph Library.
-
-Developers of generic algoriths should be aware that, when generalizing an algorithm
-for both directed and undirected graphs, it is better to use the `out_degree(g)`
-function to access out-edges since it is guaranteed by every other graph class.
-
-[h4 Vertex and Edge Storage]
-The `undirected` graph class has three distinct storage compontents: one for each
-of vertices, edges, and incident-edges per vertex. Each of these storage components
-uses a `std::list`. This is important to remember when considering the performance
-of oeprations on these graphs.
-
-Note that mutating (modifying) edge operations on a graph must operate on both
-the edge list and incident edge lists. For example, adding an edge to the graph
-will insert the edge or descriptors into both the edge list and the incidence
-edge list of the edge's source and target.
-
-It is important to note that the use of the term /incident edges/ in this context
-generally refers to the /out/-edges of a vertex. Because the graph is undirected,
-every in-edge is also an out-edge, and so we use the term /incident/ to capture
-these semantics. As a result, the `out_edges(g)`, `in_edges(g)` and `incident_edges(g)`
-functions all return identical iterator ranges.
-
-[h4 Descriptor and Iterator Stability]
-With the `undirected_graph` class, descriptors and iterators remain stable after
-most operations. This is to say that removing a vertex or edge will not invalidate
-descriptors and iterators to other vertices or edges.
-
-[h4 Vertex Indexing and Stability]
-The `undirected_graph` class provides a built-in internal properties for vertex
-types, and will provide some degree of automated index management. Algorithms
-that use vertex indices generally assume that they are in the range
-\[0, `num_vertices(g)`). With the `undirected_graph` class vertex indices will
-be in this continuous range until a vertex is removed from the graph. This is
-the only operation that invalidates vertex indices, but the vertices will need
-to be renumbered using the `renumber_vertex_indices()` function.
-
-[h4 Template Parameters]
-There are only three parameters to the `undirected_graph` class.
-[table
- [[Parameter] [Description] [Default]]
- [
- [`VertexProperties`]
- [Specifies internal properties for vertices of the graph.]
- [`no_property`]
- ]
- [
- [`EdgeProperties`]
- [Specifies internal properties for edges of the graph.]
- [`no_property`]
- ]
- [
- [`GraphProperties`]
- [Specifies internal properties for the graph itself.]
- [`no_property`]
- ]
-]
-
-[h5 Model Of]
-VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
-
-[h5 Where Defined]
-`boost/graph/undirected_graph.hpp`
-
-[h4 Associated Types]
-There are a number of useful types associated with the `undirected_graph` class.
-Most of these are accessed through `graph_traits` or other template classes.
-For convenience these types have been grouped by purpose.
-
-[h5 Descriptor Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<undirected_graph>::vertex_descriptor`]
- [
- The type for the vertex descriptors associated with the graph.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::edge_descriptor`]
- [
- The type for the edge descriptors associated with the graph.
- ]
- ]
-]
-
-[h5 Iterator Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<undirected_graph>::vertex_iterator`]
- [
- The type for iterators returned by `vertices()`. Verex iterators are
- models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::edge_iterator`]
- [
- The type for iterators returned by `edges()`. Edge iterators are
- models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::out_edge_iterator`]
- [
- The type for iterators returned by `out_edges()`. Out-edge iterators
- are models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::in_edge_iterator`]
- [
- The type for iterators returned by `in_edges()`. In-edge iterators
- are models of the `BidirectionalIterator` concept.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::adjacency_iterator`]
- [
- The type for iterators returned by `adjacent_vertices`. Adjacency
- iterators are models of the `BidirectionalIterator` concept.
- ]
- ]
-]
-
-[h5 Miscellaneous Types]
-[table
- [[Type] [Description]]
- [
- [`graph_traits<undirected_graph>::vertices_size_type`]
- [The type used for dealing with the number of vertices in the graph.]
- ]
- [
- [`graph_traits<undirected_graph>::edge_size_type`]
- [The type used for dealing with the number of edges in the graph.]
- ]
- [
- [`graph_traits<undirected_graph>::degree_size_type`]
- [The type used for dealing with the number of edges incident to a vertex in the graph.]
- ]
- [
- [`undirected_graph::vertex_index_type`]
- [The integral type representing vertex indices (generally `unsigned int`).]
- ]
- [
- [
- `property_map<undirected_graph, Property>::type`
-
- `property_map<undirected_graph, Property>::const_type`
- ]
- [
- The property map type for vertex or edge properties in the graph. The specific
- property is specified by the `Property` template argument, and must match one of
- the properties specified in the `VertexProperties` or `EdgeProperties` for the
- graph.
- ]
- ]
- [
- [`graph_property<undirected_graph, Property>::type`]
- [
- The value type for the graph property specified by the `Property` parameter.
- `Property` must be one of the types in the `GraphProperties` template argument.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::directed_category`]
- [
- This is always `undirectedS`, indicating that the graph supports operations
- for undirected graphs.
- ]
- ]
- [
- [`graph_traits<undirected_graph>::edge_parallel_category`]
- [
- This is always `allow_parallel_edges_tag`, indicating that multiple edges
- may be added between two vertices (i.e., graphs can be /multigraphs/).
- ]
- ]
-]
-
-[h4 Member Functions]
-[table
- [[Function] [Description]]
- [
- [`undirected_graph(const GraphProperties& p = GraphProperties()`]
- [The default constructor creates a graph with no vertices or edges.]
- ]
- [
- [`undirected_graph(const undirected_graph& x`)]
- [The copy constructor creates a copy of the given graph `x`.]
- ]
- [
- [
-``
-undirected_graph(vertices_size_type n,
- const GraphProperties& p = GraphProperties())
-``
- ]
- [The default constructor creates a graph with `n` vertices and no edges.]
- ]
- [
- [`undirected_graph& operator =(const undirected_graph& x)`]
- [Copies the edges and vertices of the graph `x`.]
- ]
-]
-
-[h4 Non-member Functions]
-[h5 Non-member Accessors]
-[table
- [[Function] [Description]]
- [
- [
-``
-std::pair<vertex_iterator, vertex_iterator>
-vertices(const undirected_graph& g)
-``
- ]
- [Returns an iterator range providing access to the vertex list of `g`.]
- ]
- [
- [
-``
-std::pair<edge_iterator, edge_iterator>
-edges(const undirected_graph& g)
-``
- ]
- [Returns an iterator range providing access to the edge list of `g`.]
- ]
- [
- [
-``
-std::pair<out_edge_iterator, out_edge_iterator>
-incident_edges(vertex_descriptor v, const undirected_graph& g)
-``
-
-``
-std::pair<out_edge_iterator, out_edge_iterator>
-out_edges(vertex_descriptor v, const undirected_graph& g)
-``
-
-``
-std::pair<in_edge_iterator, in_edge_iterator>
-in_edges(vertex_descriptor v, const undirected_graph& g)
-``
- ]
- [
- Returns an iterator range providing access to the incident edges
- of the vertex `v`. Because `g` is an undirected graph, these three
- functions are guaranteed to return identical iterator ranges.
- ]
- ]
- [
- [
-``
-std::pair<adjacency_iterator, adjacency_iterator>
-adjacent_vertices(vertex_descriptor v,
- const undirected_graph& g)
-``
- ]
- [
- Returns an iterator range providing access to the adjacenct vertices
- of vertex `v` in the graph `g`. Note that this is functionally
- equivalent to iterating over the targets of all incident edges of `v`.
- ]
- ]
- [
- [
-``
-vertices_size_type
-num_vertices(const undirected_graph& g)
-``
- ]
- [Returns the number of vertices in the graph `g`.]
- ]
- [
- [
-``
-edge_size_type
-num_edges(const undirected_graph& g)
-``
- ]
- [Returns the number of edges the graph `g`.]
- ]
- [
- [
-``
-degree_size_type
-degree(vertex_descriptor v,
- const undirected_graph& g)
-``
-
-``
-degree_size_type
-out_degree(vertex_descriptor v,
- const undirected_graph& g)
-``
-
-``
-degree_size_type
-in_degree(vertex_descriptor v,
- const undirected_graph& g)
-``
- ]
- [
- Returns the degree of the vertex `v`, which is the number of
- edges incident to it. Because `g` is undirected, all three
- functions return equal values.
- ]
- ]
- [
- [
-``
-vertex_descriptor
-vertex(vertices_size_type n
- const undirected_graph& g)
-``
- ]
- [
- Returns the /nth/ vertex in the graph `g`. With undirected graphs,
- this method is /O(n)/. As such its use with this type of graph is
- discouraged.
- ]
- ]
- [
- [
-``
-std::pair<edge_descriptor, bool>
-edge(vertex_descriptor u,
- vertex_descriptor v,
- const undirected_graph& g)
-``
- ]
- [
- If the edge (`u`,`v`) is in `g`, then this function returns the
- descriptor for the edge connecting `u` and `v` with boolean value
- set to `true`. Otherwise, the boolean value is `false` and the
- edge descriptor is invalid.
- ]
- ]
- [
- [
-``
-vertex_size_type
-get_vertex_index(vertex_descriptor v,
- const undirected_graph& g)
-``
- ]
- [
- Returns the vertex index of the given vertex descriptor v. Note
- that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
- This function is an alias for `get(vertex_index,g,v)`.
- ]
- ]
- [
- [
-``
-vertex_size_type
-max_vertex_index(vertex_descriptor v,
- const undirected_graph& g)
-``
- ]
- [
- Returns the vertex index of the given vertex descriptor v. Note
- that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
- This function is an alias for `get(vertex_index,g,v)`.
- ]
- ]
-]
-
-[h5 Non-member Modifiers]
-[table
- [[Function] [Description]]
- [
- [
-``
-vertex_descriptor
-add_vertex(undirected_graph& g)
-``
- ]
- [Adds a vertex to `g` and returns a descriptors for the new vertex.]
- ]
- [
- [
-``
-void
-clear_vertex(vertex_descriptor v,
- undirected_graph& g)
-``
- ]
- [
- Removes all in- and out-edges of `v`, but leaves `v` in the graph `g`.
- This is functioanlly equivalent to invoking `remove_edge()` on all
- in- or out-edges of `v`, potentially invalidating descriptors and
- iterators.
- ]
- ]
- [
- [
-``
-vertex_descriptor
-remove_vertex(vertex_descriptor v,
- undirected_graph& g)
-``
- ]
- [
- Removes vertex `v` from the graph `g`. It is assumed that `v` has no
- incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
- before removing it.
-
- Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
- before calling this method, this operation will invalidate all vertex indices
- in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
- be renumbered using the `renumber_vertex_indices(g)` method. If possible,
- prefer to remove groups of vertices at one time before renumbering since
- renumbering is a /O(n)/ time operation.
- ]
- ]
- [
- [
-``
-void
-remove_vertex_and_renumber_indices(vertex_iterator i,
- undirected_graph& g)
-``
- ]
- [
- Removes the vertex indicated by the iterator `i` from the graph `g`. Like
- the `remove_vertex(v,g)` function, it is expected that `*i` have no
- incident edges at the time of removal.
-
- As indicated by the name, this method will also renumber vertex indices
- after the removal of `*i`. This operation iterates over vertices after
- `i`, decrementing their index by 1. If your program removes several
- vertices at once, prefer to call several `remove_vertex(v,g)` methods,
- followed by `renumber_vertices(g)` before using `g` in an algorithm.
- ]
- ]
- [
- [
-``
-void
-renumber_vertex_indices(undirected_graph& g)
-``
- ]
- [
- Renumbers all interior vertex indices such that each vertex has an index
- in the range \[0, `num_vertices(g)`). Generally, this function needs to
- be called after removing vertices and before invoking different graph
- algorithms.
- ]
- ]
- [
- [
-``
-std::pair<edge_descriptor, bool>
-add_edge(vertex_descriptor u,
- vertex_descriptor v,
- undirected_graph& g)
-``
- ]
- [
- Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
- edge. For `undirected_graph`s, the boolean value of the pair will always
- be true.
- ]
- ]
- [
- [
-``
-void
-remove_edge(vertex_descriptor u,
- vertex_descriptor v,
- undirected_graph& g)
-``
- ]
- [
- Removes the edge /(u,v)/ from the graph. This operation invalidates any
- descriptors or iterators referencing the edge. Note that `u` and `v` must
- be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
- (with multiple edges between /(u,v)/, this mehtod will cause the removal of
- all such edges connecting `u` and `v`.
- ]
- ]
- [
- [
-``
-void
-remove_edge(edge_descriptor e,
- undirected_graph& g)
-``
- ]
- [
- Removes the edge `e` from the graph. If multuple edges exist from
- (`source(e,g)`, `target(e,g)`), then this method will remove only
- the single, specified edge.
- ]
- ]
- [
- [
-``
-void
-remove_edge(out_edge_iterator i,
- undirected_graph& g)
-``
- ]
- [
- This is functionally equivalent to `remove_edge(*i, g)`.
- ]
- ]
- [
- [
-``
-template <class Predicate> void
-remove_edge_if(Predicate p, undirected_graph& g)
-``
- ]
- [
- Removes all edges from the graph that satisfy `predicate`. That is, if
- `p()` returns true when applied to an edge, then that edge is removed.
- The affect on descriptor and iterator is the same as that of invoking
- `remove_edge()` for on each of the removed vertices.
- ]
- ]
- [
- [
-``
-template <class Predicate> void
-remove_incident_edge_if(vertex_descriptor v, Predicate p
- undirected_graph& g)
-``
-
-``
-template <class Predicate> void
-remove_out_edge_if(vertex_descriptor v, Predicate p,
- undirected_graph& g)
-``
-
-``
-template <class Predicate> void
-remove_in_edge_if(vertex_descriptor v, Predicate p,
- undirected_graph& g)
-``
- ]
- [
- Removes all edges incident-edges from vertex`v` that satisfy `predicate`.
- That is, if `p()` returns true when applied to an edge, then that edge
- is removed. The affect on descriptor and iterator is the same as that
- of invoking `remove_edge()` for on each of the removed vertices.
-
- Because this graph is undirected, these three funtions are identical
- in behavior and run time.
- ]
- ]
-]
-
-[h5 Proprety Map Acessors]
-[table
- [[Function] [Description]]
- [
- [
-``
-template <class Property>
-property_map<undirected_graph, Property>::type
-get(Property,
- const undirected_graph& g)
-``
- ]
- [
- Returns the property map object for the vertex property specified by the
- type `Property`. This type must match one of the properties specified in
- the `VertexProperties` template argument.
- ]
- ]
- [
- [
-``
-template <class Property, class Descriptor>
-typename
- property_traits<
- property_map<undirected_graph, Property>::const_type
- >::value_type
-get(Property,
- const undirected_graph& g,
- Descriptor d)
-``
- ]
- [
- Returns the property value specified by the type `Property` for either
- the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
- ]
- ]
- [
- [
-``
-template <class Property, class Descriptor, class Value>
-void
-put(Property,
- const undirected_graph& g,
- Descriptor d,
- Value v)
-``
- ]
- [
- Sets the property value denoted by the type `Property` for either edge
- or vertex descriptor `d` to the given value `v`.
- ]
- ]
- [
- [
-``
-template <class GraphProperty>
-typename graph_property<undirected_graph, GraphProperty>::type&
-get_property(undirected_graph& g, GraphProperty)
-``
-
-``
-template <class GraphProperty>
-const typename graph_property<undirected_graph, GraphProperty>::type&
-get_property(const undirected_graph& g, GraphProperty)
-``
- ]
- [
- Returns the graph property specified by the type `GraphProperty` for
- the graph `g`. Here, GraphProperty must be one of the properties
- in the `GraphProperties` template argument.
- ]
- ]
- [
- [
-``
-template <class GraphProprety, class Value>
-void
-set_property(const undirected_graph& g, GraphProperty, Value v)
-``
- ]
- [
- Sets the graph proeprty specified by the type `GraphProperty` to
- the given value `v`. Note that `GraphProperty` must be one of
- the properties in the `GraphProperties` template argument.
- ]
- ]
-]
-
-[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk 2007-06-27 08:23:14 EDT (Wed, 27 Jun 2007)
+++ (empty file)
@@ -1,46 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
-
-[section Reference Guide]
-
-[section Graph Types]
-[include ref_undirected_graph.qbk]
-[include ref_directed_graph.qbk]
-[include ref_adjacency_list.qbk]
-[endsect]
-
-[section Algorithms]
-[section Core Algorithms]
-[endsect]
-
-[section Shortest Path Algorithms]
-[endsect]
-
-[section Minimum Spanning Tree Algorithms]
-[endsect]
-
-[section Connectivity Algorithms]
-[include ref_connected_components.qbk]
-[include ref_strong_components.qbk]
-[include ref_connectivity.qbk]
-[endsect]
-
-[section Maximum Flow Algorithms]
-[endsect]
-
-[section Sparse Matrix Ordering Algorithms]
-[endsect]
-
-[section Layout Algorithms]
-[endsect]
-
-[section Graph Measures]
-[include ref_distributions.qbk]
-[endsect]
-[endsect]
-
-[endsect]
\ No newline at end of file
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