[Boost-commit] svn:boost r7336

From: asutton_at_[hidden]
Date: 2007-07-02 09:22:55

Author: asutton
Date: 2007-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
New Revision: 7336
URL: http://svn.boost.org/trac/boost/changeset/7336

Log:
Added concept docs for EventVisitor/EventVisitorList. Finshed docs for
depth_first_search()

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk         |   161 ++++++++++++++++++++++++++++++++------- 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk              |     1                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk                          |     9 ++                                      
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk |     2                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk   |   144 ++++++++++++++++++----------------      
   5 files changed, 219 insertions(+), 98 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk	2007-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
@@ -5,51 +5,147 @@
  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  /]
 
-[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).
+[section Event Visitor]
+This concept defines the interface for single-event visitors. An EventVisitor has an
+/apply/ member function (`operator()`) which is invoked within the graph algorithm
+at the event-point specified by the `event_filter` typedef within the type modeling
+the EventVisitor concept. EventVisitors can be combined into an [BoostEventVistorList].
 
-[h4 Associated Types]
+The following is the list of event tags that can be invoked in Boost.Graph algorithms.
+Each tag corresponds to a member function of the visitor for an algorithm. For example,
+the [BoostBFSVisitor] of [boost_breadth_first_search] has a `cycle_edge()` member function.
+The corresponding tag is `on_cycle_edge`. The first argument in the event visitor's
+`operator()` must be either an edge or vertex depending on the event tag.
+
+[h4 Event Tags]
 [table
     [[Type] [Description]]
     [
-        [`graph_traits<G>::vertex_descriptor`]
+        [on_initialize_vertex]
+        [
+            An event tag corresponding to the initialization of a vertex. The parameter
+            type associated with this event is `vertex_descriptor`.
+        ]
+    ]
+    [
+        [on_start_vertex]
         [
-            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.
+            In algorithms that without explicit starting points, this event tag
+            corresponds to the selection of a starting vertex. The parameter
+            type associated with this event is `vertex_descriptor`.
         ]
     ]
     [
-        [`graph_traits<G>::edge_descriptor`]
+        [on_discover_vertex]
         [
-            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.
+            An event tag that corresponds to a vertex that is being used for
+            the first time. The parameter type associated with this event is
+            `vertex_descriptor`.
         ]
     ]
     [
-        [`graph_traits<G>::directed_category`]
+        [on_examine_edge]
         [
-            This type shall be convertible to `directed_tag` or `undirected_tag`.
+            An event tag that corresponds to the examination of edges for recently
+            discovered vertices. The parameter type associated with this event
+            is `edge_descriptor`.
         ]
     ]
     [
-        [`graph_traits<G>::edge_parallel_category`]
+        [on_tree_edge]
         [
-            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`.
+            For algorithms whose iterations of a vertex set implicitly define a
+            tree (such as [boost_breadth_first_search] or [boost_depth_first_search]),
+            this event tag corresponds to the identification of an edge that acts
+            as an edge in the search tree. The parameter type associated with this
+            event is `edge_descriptor`.
         ]
     ]
     [
-        [`graph_traits<G>::traversal_category`]
+        [on_cycle_edge]
         [
-            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`.
+            For algorithms capable of detecting cycles in graphs such as
+            [boost_depth_first_search], this event tag is associated with discovery
+            of an edge that creates a cycle within the graph. The parameter type
+            associated with this event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_forward_or_cross_edge]
+        [
+            Forward and cross edges refer to types of edges that can be found by
+            different types of searches on graph (e.g., [boost_depth_first_search]).
+            This event tag corresponds to the identification of such an edge by
+            the algorithm. The parameter type associated with this event is
+            `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_back_edge]
+        [
+            Back edges refer to types of edges that can be found by different types
+            of searches on a graph (e.g., [boost_breadth_first_search] and
+            [boost_depth_first_search]). This event tag corresponds to the identification
+            of such an edge by the algorithm. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_finish_vertex]
+        [
+            The inverse event of `on_discover_vertex`, this event tag corresponds to
+            the completion of an iteration of an algorithm that is operating on a
+            vertex. The parametet type associated with this event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_relaxed]
+        [
+            For algorithms implementing edge relaxation (e.g.,
+            [boost_dijkstra_shortest_paths]), this event corresponds to the case
+            where an edge is relaxed. The parameter type associated with this event
+            is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_not_relaxed]
+        [
+            For algorithms implementing edge relaxation (e.g.,
+            [boost_dijkstra_shortest_paths]), this event corresponds to the case
+            where an edge is not relaxed. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_minimized]
+        [
+            For algorithms implementing edge minimization (e.g.,
+            [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+            where an edge is minimized. The parameter type associated with this event
+            is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_not_minimized]
+        [
+            For algorithms implementing edge minimization (e.g.,
+            [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+            where an edge is not minimized. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+]
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`V::event_filter`]
+        [
+            A tag to specify on which even the visitor should be invoked.
         ]
     ]
 ]
@@ -58,15 +154,22 @@
 [table
     [[Expression] [Description]]
     [
-        [`graph_traits<G>::null_vertex()`]
+        [`vis(x,g)`]
         [
-            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()`.
+            Invokes the `operator()` member function of an object `vis` of type
+            `V`. The parameter `x` is either a vertex or edge of the graph `g`. The
+            specific type of parameter depends on `V::event_filter`.
 
-            *Returns* `vertex_descriptor`
+            *Returns* `void`
         ]
     ]
 ]
 
+[h4 Models]
+* [boost_predecessor_recorder]
+* [boost_distance_recorder]
+* [boost_time_stamper]
+* [boost_property_writer]
+* [boost_null_visitor]
+
 [endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor_list.qbk	2007-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
@@ -0,0 +1,70 @@
+[/
+ / 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 Event Visitor List]
+An EventVisitorList is either an [BoostEventVisitor], or a list of [BoostEventVisitor]
+combined using `std::pair`. Each graph algorithm defines visitor adaptors that convert an
+EventVisitorList into the particular kind of visitor needed by the algorithm. In the
+following example we will show how to combine event visitors into a list using `std::pair`
+and how to use an algorithm's visitor adaptor class.
+
+Suppose we would like to print out the parenthesis structure of the discover/finish times
+of vertices in a depth-first search. We can use the Boost.Graph algorithm `depth_first_search()`
+and two event visitors to accomplish this. The complete source code for the following example
+is in `examples/dfs_parenthesis.cpp`. First we define the two event visitors. We use
+`on_discover_vertex` and `on_finish_vertex` as the event points, selected from the list of
+event points specified in [BoostDFSVisitor].
+
+    struct open_paren : public base_visitor<open_paren>
+    {
+        typedef on_discover_vertex event_filter;
+
+        template <class Vertex, class Graph>
+        void operator ()(Vertex v, Graph& G)
+        {
+            cout << "(" << v;
+        }
+    };
+
+
+    struct close_paren : public base_visitor<clsoe_paren>
+    {
+        typedef on_discover_vertex event_filter;
+
+        template <class Vertex, class Graph>
+        void operator ()(Vertex v, Graph& G)
+        {
+            cout << v << ")";
+        }
+    };
+
+Next, we create two event visitor objects and combine them so the resultant type models
+the EventVisitorList concept.
+
+    make_pair(open_paren(), close_paren());
+
+Next we want to pass this list into `depth_first_search()`, but `depth_first_search()` is
+expecting a [BoostDFSVisitor], not a [EventVisitorList]. We therefore use the [boost_dfs_visitor]
+adaptor which turns an [BoostEventVisitor] list into a [BoostDFSVisitor]. Like all of the visitor
+adaptors, [dfs_visitor] has a creation function called [boost_make_dfs_visitor].
+
+    make_dfs_visitor((open_paren(), close_paren()));
+
+Now we can pass the resulting visitor object into `depth_first_search()` as follows.
+
+    depth_first_search(
+        G,
+        make_dfs_visitor(make_pair(open_paren(), close_paren())));
+
+For creating a list of more than two event visitors, nest calls to `make_pair` in the following way
+to recursively produce an EventVisitorList.
+
+    make_pair(visitor1,
+        make_pair(visitor2, ...
+            make_pair(visitorN - 1, visitorN)...))
+
+[endsect]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk	2007-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
@@ -19,5 +19,6 @@
 [include visitor.qbk]
 [include bfs_visitor.qbk]
 [include dfs_visitor.qbk]
+[include event_visitor.qbk]
 
 [endsect]
\ No newline at end of file

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-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
@@ -76,6 +76,8 @@
 [template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
 [template BoostBFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
 [template BoostDFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
+[template BoostEventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
+[template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
 
 [/ Boost Reference Documentation]
 [template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph `undirected_graph`]]
@@ -83,11 +85,18 @@
 [template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list `adjacecncy_list`]]
 [template boost_edge_list[] [link boost_graph.reference_guide.graph_types.edge_list `edge_list`]]
 
+[template boost_null_visitor[] [link boost_graph.reference_guide.visitor_types.null_visitor `null_visitor`]]
 [template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor `bfs_visitor`]]
 [template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor `dfs_visitor`]]
+[template boost_predecessor_recorder[] [link boost.graph_reference_guide.event_visitors.predecessor_recorder `predecessor_recorder`]]
+[template boost_distance_recorder[] [link boost.graph_reference_guide.event_visitors.distance_recorder `distance_recorder`]]
+[template boost_time_stamper[] [link boost.graph_reference_guide.event_visitors.time_stamper `time_stamper`]]
+[template boost_property_writer[] [link boost.graph_reference_guide.event_visitors.property_writer `property_writer`]]
 
 [template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search `breadth_first_search()`]]
 [template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search `depth_first_search()`]]
+[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths `dijkstra_shortest_paths`]]
+[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths `bellman_ford_shortest_paths`]]
 
 [/ Contents ]
 [include introduction.qbk]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk	2007-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
@@ -17,7 +17,7 @@
     breadth_first_search(Graph& g,
                         typename graph_traits<Graph>::vertex_descriptor s,
                         Buffer& q,
-                        Visitor v,
+                        Visitor vis,
                         bgl_named_params<P,T,R>& params = ``/defaults/``)
 
 The `breadth_first_search()` function performs a breadth-first traversal \[49\] of a directed or

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk	2007-07-02 09:22:54 EDT (Mon, 02 Jul 2007)
@@ -8,67 +8,81 @@
 [section Depth-First Search]
     template <class Graph, class P, class T, class R>
     void
-    breadth_first_search(Graph& g,
-                        typename graph_traits<Graph>::vertex_descriptor s,
-                        bgl_named_params<P,T,R>& params = ``/defaults/``)
+    depth_first_search(Graph& g,
+                       bgl_named_params<P,T,R>& params = ``/defaults/``)
 
-    template <class Graph, class Buffer, class Visitor, class P, class T, class R>
+    template <class Graph, class Visitor, class ColorMap>
     void
-    breadth_first_search(Graph& g,
-                        typename graph_traits<Graph>::vertex_descriptor s,
-                        Buffer& q,
-                        Visitor v,
-                        bgl_named_params<P,T,R>& params = ``/defaults/``)
-
-The `breadth_first_search()` function performs a breadth-first traversal \[49\] of a directed or
-undirected graph. A breadth-first traversal visits vertices that are closer to the source before
-visiting vertices that are further away. In this context "distance" is defined as the number of edges
-in the shortest path from the source vertex. The `breadth_first_search()` function can be used to
-compute the shortest path from the source to all reachable vertices and the resulting shortest-path
-distances. For more definitions related to BFS, see section Breadth-First Search.
-
-BFS uses two data structures to to implement the traversal: a color marker for each vertex and
-a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered
-adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray
-vertices. The algorithm proceeds by removing a vertex /u/ from the queue and examining each out-edge
-/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
-queue. After all of the out-edges are examined, vertex u is colored black and the process is
-repeated. Pseudo-code for the BFS algorithm is a listed below.
+    depth_first_search(Graph& g,
+                        Visitor vis,
+                        ColorMap color,
+                        typename graph_traits<Graph>::vertex_descriptor s)
+
+The `depth_first_search()` function performs a depth-first traversal of the vertices
+in a directed graph. When possible, a depth-first traversal chooses a vertex adjacent
+to the current vertex to visit next. If all adjacent vertices have already been
+discovered, or there are no adjacent vertices, then the algorithm backtracks to the
+last vertex that had undiscovered neighbors. Once all reachable vertices have been
+visited, the algorithm selects from any remaining undiscovered vertices and continues
+the traversal. The algorithm finishes when all vertices have been visited. Depth-first
+search is useful for categorizing edges in a graph, and for imposing an ordering on the
+vertices. Section /Depth-First Search/ describes the various properties of DFS and
+walks through an example.
+
+Similar to BFS, color markers are used to keep track of which vertices have been
+discovered. White marks vertices that have yet to be discovered, gray marks a
+vertex that is discovered but still has vertices adjacent to it that are undiscovered.
+A black vertex is discovered vertex that is not adjacent to any white vertices.
+
+The `depth_first_search()` function invokes user-defined actions at certain event-points
+within the algorithm. This provides a mechanism for adapting the generic DFS algorithm
+to the many situations in which it can be used. In the pseudo-code below, the event
+points for DFS are indicated in by the triangles and labels on the right. The user-defined
+actions must be provided in the form of a visitor object, that is, an object whose type
+meets the requirements for a [BoostDFSVisitor]. In the pseudo-code we show the algorithm
+computing predecessors /p/, discovery time /d/ and finish time /t/. By default, the
+`depth_first_search()` function does not compute these properties, however there are
+pre-defined visitors such as [boost_predecessor_recorder] and [boost_time_stamper] that
+can be used to do this.
 
 [pre
-BFS(G, s)
-    for each vertex u in V\[G\]           initialize vertex u
+DFS(G)
+    for each vertex u in V              initialize vertex u
         color\[u\] := WHITE
-        d\[u\] := infinity
-        p\[u\] := u
+        p\[u\] = u
     end for
 
-    color\[s\] := GRAY
-    d\[s\] := 0
-    ENQUEUE(Q, s)                       discover vertex s
-
-    while not EMPTY(Q)
-        u := DEQUEUE(Q)                 examine vertex u
-        for each vertex v in adj\[u\]     examine edge /(u,v)/
-            if(color\[v\] = WHITE)        /(u,v)/ is a tree edge
-                color\[v\] := GRAY
-                d\[v\] := d\[u\] + 1
-                p\[v\] := u
-                ENQUEUE(Q, v)           discover vertex v
-            else                        /(u,v)/ is a non-tree edge
-                if (color\[v\] = GRAY)    /(u,v)/ has a gray target
-                ...
-                else                    /(u,v)/ has a black target
-                ...
-            end if
-        end for
-        color\[u\] := BLACK               finsih vertex u
-    end while
-    return (d, p)
+    time := 0
+    if there is a starting vertex s
+        call DFS-VISIT(G, s)            start vertex /s/
+
+    for each vertex u in V
+        if color\[u\] = WHITE             start vertex /u/
+        call DFS-VISIT(G, u)
+    end for
+
+    return (p,d_time,f_time)
+
+DFS-VISIT(G, u)
+    color\[u\] := GRAY                    discover vertex /u/
+    d_time\[u\] := time := time + 1
+
+    for each v in Adj\[u\]                examine edge /(u,v)/
+        if (color\[v\] = WHITE)           /(u,v)/ is a tree edge
+            p\[v\] = u
+            call DFS-VISIT(G, v)
+        else if (color\[v\] = GRAY)       /(u,v)/ is a back edge
+            ...
+        else if (color\[v\] = BLACK)      /(u,v)/ is a cross or forward edge
+            ...
+    end for
+
+    color\[u\] := BLACK                   finish vertex /u/
+    f_time\[u\] := time := time + 1
 ]
 
 [heading Where Defined]
-`boost/graph/breadth_first_search.hpp`
+`boost/graph/depth_first_search.hpp`
 
 [heading Parameters]
 [table
@@ -83,8 +97,8 @@
     [
         [in] [`vertex_descriptor s`]
         [
-            The source vertex where the search is started. This must be a valid vertex descriptor of
-            `g`.
+            This specifies the vertex that the depth-first search should originate from. Note
+            that this can also be given as a named parameter.
         ]
     ]
 ]
@@ -96,12 +110,20 @@
         [in] [`visitor(Visitor vis)`]
         [
             A visitor object that is inovked inside the algorithm at event points specified by the
-            [BoostBFSVisitor]. The `vis` object must be model the [BoostBFSVisitor] concept.
+            [BoostDFSVisitor]. The `vis` object must be model the [BoostDFSVisitor] concept.
 
             *Default* `bfs_visitor<null_visitor>`.
         ]
     ]
     [
+        [in] [`root_vertex(vertex_descriptor s)`]
+        [
+            This specifies the vertex that the depth-first search should originate from.
+
+            *Default* `*vertices(g).first`
+        ]
+    ]
+    [
         [in] [`vertex_index_map(VeretxIndexMap index_map)`]
         [
             This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
@@ -129,20 +151,6 @@
             the index map (to access colors for a vertex).
         ]
     ]
-    [
-        [util] [`buffer(Buffer& q)`]
-        [
-            The queue used to determine the order in which vertices will be discovered.
-            If a FIFO queue is used, then the traversal will be according to the usual
-            BFS ordering. Other types of queues can be used, but the traversal order will
-            be different. For example Dijkstra's algorithm can be implemented using a
-            priority queue. The type Buffer must be a model of [NoConcept Buffer].
-
-            The `value_type` of the buffer must be the vertex_descriptor type for the graph.
-
-            *Default* `boost::queue`
-        ]
-    ]
 ]
 
 [heading Complexity]