Date: 2008-07-22 12:22:09
Date: 2008-07-22 12:22:09 EDT (Tue, 22 Jul 2008)
New Revision: 47692
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
+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
--- 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...
[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
-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.
-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.
[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
Boost-Commit 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