# Boost-Commit :

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.

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(-)

==============================================================================
--- (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
+
+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.
+
+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.
+
+
+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]
+
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.
-