Subject: [Boost-commit] svn:boost r55997 - in trunk/libs/graph/quickbook: . reference
From: asutton_at_[hidden]
Date: 2009-09-03 09:44:55
Author: asutton
Date: 2009-09-03 09:44:54 EDT (Thu, 03 Sep 2009)
New Revision: 55997
URL: http://svn.boost.org/trac/boost/changeset/55997
Log:
Added partial content for edge_list.
Considering alternative documentation structure for adjacency_list.
Text files modified:
trunk/libs/graph/quickbook/boost_concepts.qbk | 1
trunk/libs/graph/quickbook/reference/adjacency_list.qbk | 108 +++++++++++-------------
trunk/libs/graph/quickbook/reference/edge_list.qbk | 169 ++++++++++++++++++++++++++++++++++++++++
3 files changed, 220 insertions(+), 58 deletions(-)
Modified: trunk/libs/graph/quickbook/boost_concepts.qbk
==============================================================================
--- trunk/libs/graph/quickbook/boost_concepts.qbk (original)
+++ trunk/libs/graph/quickbook/boost_concepts.qbk 2009-09-03 09:44:54 EDT (Thu, 03 Sep 2009)
@@ -19,6 +19,7 @@
[template BidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph [^BidirectionalGraph]]]
[template VertexListGraph[] [link boost_graph.concepts.graph_concepts.vertex_list_graph [^VertexListGraph]]]
[template EdgeListGraph[] [link boost_graph.concepts.graph_concepts.edge_list_graph [^EdgeListGraph]]]
+[template VertexAndEdgeListGraph[] [link boost_graph.concepts.graph_concepts.vertex_and_edge_list_graph [^VertexAndEdgeListGraph]]]
[template AdjacencyGraph[] [link boost_graph.concepts.graph_concepts.adjacency_graph [^AdjacencyGraph]]]
[template AdjacencyMatrix[] [link boost_graph.concepts.graph_concepts.adjacency_matrix [^AdjacencyMatrix]]]
[template MutableGraph[] [link boost_graph.concepts.graph_concepts.mutable_graph [^MutableGraph]]]
Modified: trunk/libs/graph/quickbook/reference/adjacency_list.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/adjacency_list.qbk (original)
+++ trunk/libs/graph/quickbook/reference/adjacency_list.qbk 2009-09-03 09:44:54 EDT (Thu, 03 Sep 2009)
@@ -193,7 +193,7 @@
[
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
+ the properties specified in the `VertexProperty` or `EdgeProperty` for the
graph.
]
]
@@ -222,63 +222,55 @@
]
[heading Member Functions]
-[table
- [[Member Function] [Description]]
- [
- [`adjacency_list(const GraphProperty& p = GraphProperty())`]
- [
- The default constructor creates an empty graph with no vertices or edges,
- optionally assigning the given graph properties `p`.
- ]
- ]
- [
- [`adjacency_list(const adjacency_list& x)`]
- [ ]
- ]
- [
- [
- ``
- adjacency_list(vertices_size_type n,
- const GraphProperty& p = GraphProperty())
- ``
- ]
- [ ]
- ]
- [
- [
- ``
- template <typename Iter>
- adjacency_list(Iter f, Iter l,
- vertices_size_type n, edges_size_type m = 0,
- const GraphProperty& p = GraphProperty())
- ``
- ]
- [ ]
- ]
- [
- [
- ``
- template <typename EdgeIter, typename PropIter>
- adjacency_list(EdgeIter f, EgeIter l, PropIter p,
- vertices_size_type n, edges_size_type m = 0,
- const GraphProperty& p = GraphProperty())
- ``
- ]
- [ ]
- ]
- [
- [`adjacency_list& operator=(adjacency_list const& x)`]
- [ ]
- ]
- [
- [`void swap(adjacency_list& x)`]
- [ ]
- ]
- [
- [`void clear()`]
- [ ]
- ]
-]
+
+[/ Constructors ]
+ adjacency_list(const GraphProperty& p = GraphProperty())
+
+The default constructor creates an empty graph with no vertices or edges, optionally
+assigning the given graph properties `p`.
+
+ adjacency_list(const adjacency_list& x)
+
+Construct the graph as a copy of `x`.
+
+ adjacency_list(vertices_size_type n, const GraphProperty& p = GraphProperty())
+
+Construct the graph with `n` vertices and no edges. An optional graph property
+may be given.
+
+ template <typename Iter>
+ adjacency_list(Iter f, Iter l,
+ vertices_size_type n, edges_size_type m = 0,
+ const GraphProperty& p = GraphProperty())
+
+Construct the graph over `n` vertices and the edges given in the range \[f, l).
+The `Iter` type must be an [InputIterator] and its `value_type` must be a `pair`
+of integral types. The integral values of each `pair` refer to vertices in the
+range \[0, n).
+
+ template <typename EdgeIter, typename PropIter>
+ adjacency_list(EdgeIter f, EgeIter l, PropIter p,
+ vertices_size_type n, edges_size_type m = 0,
+ const GraphProperty& p = GraphProperty())
+
+[/ Assignment Operator]
+Construct the graph over `n` vertices and the edges given in the range \[f, l).
+The `EdgeIter` and `PropIter` types must model the [InputIterator] concept. The
+`value_type` of `EdgeIter` must be a `pair` of integral types. The integral
+values of each `pair` refer to vertices in the range \[0, n). The `value_type`
+of `PropIter` must be `EdgeProperty`.
+
+ adjacency_list& operator=(adjacency_list const& x)
+
+Assign this graph to be a copy of `x`.
+
+ void swap(adjacency_list& x)
+
+Swap this graph with `x`.
+
+ void clear()
+
+Reset the graph so that it has no vertices or edges.
[heading Non-Member Observers]
[table
Modified: trunk/libs/graph/quickbook/reference/edge_list.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/edge_list.qbk (original)
+++ trunk/libs/graph/quickbook/reference/edge_list.qbk 2009-09-03 09:44:54 EDT (Thu, 03 Sep 2009)
@@ -7,4 +7,173 @@
[section Edge List]
+ template <
+ typename EdgeIter,
+ typename ValueType = typename iterator_traits<EdgeIter>::value_type,
+ typename DiffereneType = typename iterator_traits<EdgeIter>::difference_type
+ typename Category = typename iterator_traits<EdgeIter>::iterator_category>
+ class edge_list;
+
+The `edge_list` class is an adaptor that turns a pair of edge iterators into a
+graph type that models the [EdgeListGraph] concept. The `value_type` of the edge
+iterator must be a `pair` (or at least have `first` and `second` members). The
+`first_type` and `second_type` of the pair must be the same and they will be
+used for the graph's `vertex_descriptor`. The `ValueType` and `DifferenceType`
+template parameters are only needed if your compiler does not support partial
+specialization. Otherwise they default to the correct types.
+
+[heading Where Defined]
+
+ #incldue <boost/graph/edge_list.hpp>
+
+[heading Template Parameters]
+[table
+ [[Parameter] [Description] [Default]]
+ [
+ [`EdgeIter`]
+ [
+ Must be a model of [SgiInputIterator], and its `value_type` must be
+ `pair<vertex_descriptor, vertex_descriptor>`.
+ ]
+ [ ]
+ ]
+ [
+ [`ValueType`]
+ [The `value_type` of `EdgeIter`.]
+ [`iterator_traits<EdgeIter>::value_type`]
+ ]
+ [
+ [`DifferenceType`]
+ [The `difference_type` of `EdgeIter`.]
+ [`iterator_traits<EdgeIter>::difference_type`]
+ ]
+ [
+ [`Category`]
+ [The `iterator_category` of `EdgeIter`.]
+ [`iterator_traits<EdgeIter>::iterator_category`]
+ ]
+]
+
+[heading Model Of]
+[EdgeListGraph]
+
+[heading Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<adjancency_list>::vertex_descriptor`]
+ [The type of vertex descriptors associated with the `edge_list`.]
+ ]
+ [
+ [`graph_traits<adjancency_list>::edge_descriptor`]
+ [The type of edge descriptors associated with the `edge_list`.]
+ ]
+ [
+ [`graph_traits<edge_list>::edge_size_type`]
+ [The type used for dealing with the number of edges in the graph.]
+ ]
+ [
+ [`graph_traits<edge_list>::edge_iterator`]
+ [The type used for iterating over edges in the graph. The same as `EdgeIter`.]
+ ]
+]
+
+[/
+
+<h3>Member Functions</h3>
+
+<hr>
+
+<tt>
+edge_list(EdgeIterator first, EdgeIterator last)
+</tt>
+<br><br>
+Creates a graph object with `n` vertices and with the
+edges specified in the edge list given by the range \first,last).
+
+<hr>
+
+<H3>Non-Member Functions</H3>
+
+<hr>
+
+<tt>
+std::pair<edge_iterator, edge_iterator><br>
+edges(const edge_list& g)
+</tt>
+<br><br>
+Returns an iterator-range providing access to the edge set of graph `g`.
+
+<hr>
+
+<tt>
+vertex_descriptor<br>
+source(edge_descriptor e, const edge_list& g)
+</tt>
+<br><br>
+Returns the source vertex of edge `e`.
+
+<hr>
+
+<tt>
+vertex_descriptor<br>
+target(edge_descriptor e, const edge_list& g)
+</tt>
+<br><br>
+Returns the target vertex of edge `e`.
+
+<hr>
+]
+
+[heading Example]
+
+Applying the Bellman-Ford shortest paths algorithm to an `edge_list`.
+
+ enum { u, v, x, y, z, N };
+ char name[] = { 'u', 'v', 'x', 'y', 'z' };
+
+ typedef std::pair<int,int> E;
+ E edges[] = { E(u,y), E(u,x), E(u,v),
+ E(v,u),
+ E(x,y), E(x,v),
+ E(y,v), E(y,z),
+ E(z,u), E(z,x) };
+
+ int weight[] = { -4, 8, 5,
+ -2,
+ 9, -3,
+ 7, 2,
+ 6, 7 };
+
+ typedef boost::edge_list<E*> Graph;
+ Graph g(edges, edges + sizeof(edges) / sizeof(E));
+
+ std::vector<int> distance(N, std::numeric_limits<short>::max());
+ std::vector<int> parent(N,-1);
+
+ distance[z] = 0;
+ parent[z] = z;
+ bool r = boost::bellman_ford_shortest_paths(g, int(N), weight,
+ distance.begin(),
+ parent.begin());
+ if(r) {
+ for(int i = 0; i < N; ++i) {
+ std::cout << name[i] << ": " << distance[i]
+ << " " << name[parent[i]] << std::endl;
+ }
+ } else {
+ std::cout << "negative cycle" << std::endl;
+ }
+
+The output is the distance from the root and the parent of each vertex in the
+shortest paths tree.
+
+[pre
+u: 2 v
+v: 4 x
+x: 7 z
+y: -2 u
+z: 0 z
+]
+
[endsect]
\ No newline at end of file