[Boost-commit] svn:boost r47692 - sandbox/SOC/2008/graphs/trunk/libs/graphs/doc

From: asutton_at_[hidden]
Date: 2008-07-22 12:22:09

Author: asutton
Date: 2008-07-22 12:22:09 EDT (Tue, 22 Jul 2008)
New Revision: 47692
URL: http://svn.boost.org/trac/boost/changeset/47692

Log:
Started writing some documentation.

Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/algorithms.qbk   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graph.qbk |    16 ++--------------                        
   1 files changed, 2 insertions(+), 14 deletions(-)

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/algorithms.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/algorithms.qbk	2008-07-22 12:22:09 EDT (Tue, 22 Jul 2008)
@@ -0,0 +1,40 @@
+
+[section Algorithms and Algorithm Objects]
+
+The following definitions will be important in the discussion of graph algorithms
+and their implementations. These definitions are based 
+
+[heading Walks]
+A walk over a graph is a sequence of moves over connected edges and vertices
+/(v0, e1, v1, e2, v3, ..., vn)/ such that /v0/ is the starting vertex and each
+edge /ei/ is incident on both vertices /vi-1/ and /vi+1/. In this sense, /vi-1/
+is the source vertex and /vi+1/ is the target vertex.
+
+Here, the term walk is applied to any algorithm object that moves over the
+connected elements of a graph (i.e., not arbitrarily). Contrast this with the
+notion of a graph's vertex iterator where vertex /vi/ may not be adjacent to
+vertex /vi+1/. The implication is that walks are limited to movement over
+connected components of a graph.
+
+There are two types of walks: a vertex walk and an edge walk. A vertex is a walk
+that rests (between steps) on a vertex. Conversely an edge walk rests between
+edges.
+
+Note that the source and target vertices of edges in an edge walk can have
+meaning beyond that of the edges of the undirected graphs. Specifically, the
+source vertex is that which was already visted and the target is one that will
+(probably) be visited in the walk.
+
+[heading Traversals]
+We define a traversal as a sequence of walks that will potentially visit all
+elements in a graph, connected or not. A traversal is allowed to skip
+arbitrarily from component to component.
+
+A common application of traversals is to aggregate a series of walks over a
+graph to accomodate searches on the graph (e.g., breadth- or depth-first).
+
+Like walks, traversals are also classified as vertex and edge traversals.
+
+[heading Iterators]
+
+Walks and traversals are iterable.
\ No newline at end of file

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graph.qbk
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graph.qbk	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graph.qbk	2008-07-22 12:22:09 EDT (Tue, 22 Jul 2008)
@@ -12,6 +12,8 @@
 
 This graph library...
 
+[include descriptors.qbk]
+
 [section Adjacency Lists]
 One of the most common and flexible graph data structures is the adjacency list.
 The adjacenct list component of this library provides implementations for both
@@ -30,20 +32,6 @@
 typedef digraph<VertexLabel, EdgeLabel> Graph;      // A simple directed graph
 ``
 
-[section Descriptors]
-The vertices and edges of the graph are accessible via descriptor objects. A
-descriptor is a lightweight, opaque reference to an object. All operations on
-these graphs are defined in terms of these descriptors. Methods for getting
-and using descriptors will be shown throughout this manual.
-
-[heading Perspective]
-Descriptors can cause problems for programmers who expect a significant class
-interface for returned vertices and descriptors. In fact, most graph libraries
-prefer to return heavyweight vertex objects (or pointers to them) that define
-their own interfaces. This approach is not feasible when combined with the
-amount of genericism offered by this library.
-[endsect]
-
 [section Vertex and Edge Labels]
 Vertex and Edge labels allow you to attach data to the vertices and edges of the
 graph in much the same manner as creating standard containers. In general, you