
BoostCommit : 
From: asutton_at_[hidden]
Date: 20080722 12:22:09
Author: asutton
Date: 20080722 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 20080722 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 /vi1/ and /vi+1/. In this sense, /vi1/
+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 depthfirst).
+
+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 20080722 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
BoostCommit 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