[Boost-commit] svn:boost r7195

From: asutton_at_[hidden]
Date: 2007-06-27 10:55:27

Author: asutton
Date: 2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
New Revision: 7195
URL: http://svn.boost.org/trac/boost/changeset/7195

Log:
Added more concept documents and started x-linking them

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk           |    63 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk          |    11 ++++--                                  
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk                    |     7 +---                                    
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/adjacency_list.qbk |    25 +++++++++++----                         
   4 files changed, 89 insertions(+), 17 deletions(-)

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk	2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
@@ -0,0 +1,63 @@
+[/
+ / 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 Bidirectional Graph]
+The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient
+access to the in-edges of each vertex. This concept is separated from IncidenceGraph because for
+directed graphs efficient access to in-edges typically requires more storage space, and many
+algorithms do not require access to in-edges. For undirected graphs this is not an issue, since
+the in_edges() and out_edges() functions are the same, they both return the edges incident to
+the vertex.
+
+[heading Refinement Of]
+[link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]
+
+[heading Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `bidirectional_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::in_edge_iterator`]
+        [
+            An in-edge iterator for a vertex v provides access to the in-edges of a vertex. As
+            such, the value type of an in-edge iterator is the edge descriptor type of its graph.
+            An in-edge iterator must meet the requirements of MultiPassInputIterator.
+        ]
+    ]
+]
+
+[heading Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`in_edges(v,g)`]
+        [
+            Returns an iterator range providing access to the in-edges (for directed graphs)
+            or the incident edges (for undirected graphs). The target vertex of an edge obtained
+            via an in-edge iterator is guaranteed to be the vertex `v` in the call to
+            `in_edges(v,g)`, and the source vertex must be adjacenct to `v`.
+
+            *Returns* `std::pair<in_edge_iterator, in_edge_iterator>`
+        ]
+    ]
+    [
+        [`in_degree(v,g)`]
+        [
+            Returns the number of in-edges (for directed graphs) or the number of incident
+            edges (for undirected graphs) of the vertex `v`.
+
+            *Returns* `degree_size_type`.
+        ]
+    ]
+]
+
+[endsect]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk	2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
@@ -5,5 +5,66 @@
  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  /]
 
-[section Graph Concept]
+[section Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[heading Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::vertex_descriptor`]
+        [
+            A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+            must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+            descriptors are almost always passed by value.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_descriptor`]
+        [
+            An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+            must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+            are almost always passed by value.
+        ]
+    ]
+    [
+        [`graph_traits<G>::directed_category`]
+        [
+            This type shall be convertible to `directed_tag` or `undirected_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_parallel_category`]
+        [
+            This describes whether the graph class allows the insertion of parallel edges
+            (multiple edges between the same source and target vertices). The two tags are
+            `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This describes the ways in which the vertices and edge of the graph can be visited.
+            The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+            `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+        ]
+    ]
+]
+
+[heading Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`graph_traits<G>::null_vertex()`]
+        [
+            Returns a special `vertex_descriptor` which does not refer to any vertex for graphs
+            of type `G`. Note that default initialization of `vertex_descriptors` are /not/
+            guaranteed to be equal to then `null_vertex()`.
+        ]
+    ]
+]
+
 [endsect]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk	2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
@@ -27,7 +27,7 @@
 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.
+[$images/concepts/graph_concepts.png]
 
 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.
@@ -35,20 +35,20 @@
 
 [table
     [[Expression] [Return Type or Description]]
-    [[*Graph*]]
+    [[link boost_graph.concepts.graph_concepts.graph *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]]
+    [[[link boost_graph.concepts.graph_concepts.incidence_graph *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]]
+    [[[link boost_graph.concepts.graph_concepts.bidirectional_graph *Bidirectional Graph*] 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`]]
@@ -93,6 +93,9 @@
     [[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
 ]
 
+[include graph.qbk]
+[include incidence_graph.qbk]
+
 [*TODO]
 
 There are some functions missing like `get_property()` and `put/set_property()`.

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk	2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
@@ -0,0 +1,87 @@
+[/
+ / 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 Incidence Graph]
+The IncidenceGraph concept provides an interface for efficient access to the out-edges
+(for directed graphs) or incident edges (for undirected graphs) of each vertex in
+the graph.
+
+[heading Refinement Of]
+[link boost_graph.concepts.graph_concepts.graph Graph]
+
+[heading Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `incidence_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::degree_size_type`]
+        [
+            The unsigned integral type used for representing the number of edges incident
+            to a vertex. The `degree_size_type` must meet the requirements of the
+            UnsignedIntegral concept.
+        ]
+    ]
+    [
+        [`graph_traits<G>::out_edge_iterator`]
+        [
+            An out-edge iterator for a vertex /v/ provides access to the out-edges of the
+            vertex. As such, the value type of an out-edge iterator is the `edge_descriptor`
+            type of the graph. An out-edge iterator must meet the requirements of
+            MultiPassInputIterator.
+        ]
+    ]
+]
+
+[heading Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`source(e,g)`]
+        [
+            If `e` represents the edge /(u,v)/, this function returns the vertex descriptor
+            for /u/.
+
+            *Returns* `vertex_descriptor`.
+        ]
+    ]
+    [
+        [`target(e,g)`]
+        [
+            If `e` represents the edge /(u,v)/, this function returns the vertex descriptor
+            for /v/.
+
+            *Returns* `vertex_descriptor`.
+        ]
+    ]
+    [
+        [`out_edges(v,g)`]
+        [
+            Returns an iterator range providing access to the out-edges (for directed graphs)
+            or the incident edges (for undirected graphs). The source vertex of an edge obtained
+            via an out-edge iterator is guaranteed to be the vertex `v` in the call to
+            `out_edges(v,g)`, and the target vertex must be adjacenct to `v`.
+
+            *Returns* `std::pair<out_edge_iterator, out_edge_iterator>`
+        ]
+    ]
+    [
+        [`out_degree(v,g)`]
+        [
+            Returns the number of out-edges (for directed graphs) or the number of incident
+            edges (for undirected graphs) of the vertex `v`.
+
+            *Returns* `degree_size_type`.
+        ]
+    ]
+]
+
+[endsect]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk	2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
@@ -22,16 +22,13 @@
     ]
 ]
 
-[/ Contents ]
+[/ Templates /]
 
+[/ Contents ]
 [include introduction.qbk]
-
 [include history.qbk]
-
 [include guide/guide.qbk]
-
 [include concepts/concepts.qbk]
-
 [include reference/reference.qbk]
 
 [/ [include bibliography.qbk] /]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/adjacency_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/adjacency_list.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/adjacency_list.qbk	2007-06-27 10:55:26 EDT (Wed, 27 Jun 2007)
@@ -231,21 +231,31 @@
         [Valid]
         [Valid]
         [Valid]
-        [OEL = `vecS` && [br] Directed = `directedS`]
+        [
+            OEL = `vecS` &&
+
+            Directed = `directedS`]
         [OEL = `vecS`]
     ]
     [
         [
-            `remove_edge()`[br]
-            `remove_edge_if()`[br]
-            `remove_out_edge_if()`[br]
-            `remove_in_edge_if()`[br]
+            `remove_edge()`
+
+            `remove_edge_if()`
+
+            `remove_out_edge_if()`
+
+            `remove_in_edge_if()`
+
             `clear_vertex()`
         ]
         [Valid]
         [Valid]
         [Valid]
-        [OEL = `vecS` && [br] Directed = `directedS`]
+        [
+            OEL = `vecS` &&
+
+            Directed = `directedS`]
         [OEL = `vecS`]
     ]
     [
@@ -352,7 +362,8 @@
     ]
     [
         [
-            `property_map<adjacency_list, Property>::type` [br]
+            `property_map<adjacency_list, Property>::type`
+
             `property_map<adjacency_list, Property>::const_type`
         ]
         [