[Boost-commit] svn:boost r48102 - in sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms: . depth_first

From: asutton_at_[hidden]
Date: 2008-08-12 11:36:29

Author: asutton
Date: 2008-08-12 11:36:29 EDT (Tue, 12 Aug 2008)
New Revision: 48102
URL: http://svn.boost.org/trac/boost/changeset/48102

Log:
Added missing (but soon to disappear) depth-first algorithm.
Finished a couple of touches oni the advanced search (i.e., search_for).

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first/algorithm.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/advanced_search.hpp |   305 +++++++++++++++++++++++++-------------- 
   1 files changed, 197 insertions(+), 108 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/advanced_search.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/advanced_search.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/advanced_search.hpp	2008-08-12 11:36:29 EDT (Tue, 12 Aug 2008)
@@ -1,6 +1,6 @@
 
-#ifndef SEARCH_HPP
-#define SEARCH_HPP
+#ifndef ADVANCED_SEARCH_HPP
+#define ADVANCED_SEARCH_HPP
 
 #include <stack>
 #include <queue>
@@ -12,10 +12,10 @@
 // TODO: One of the big TODO's here is improving the means of constructing
 // visitors. It would be nice to provide a set of functions that build and
 // aggregate visitors so we could do something like:
-// breadth_first_search(g, 
+// breadth_first_search(g,
 //                      on_start_vertex(lambda).
 //                      on_discover_vertex(labmda));
-// Or something like this. This would probably have to aggregate visitor 
+// Or something like this. This would probably have to aggregate visitor
 // functions through some kind visitor aggregator. Not really sure how to do
 // this yet.
 
@@ -24,7 +24,7 @@
  * to implement a number of various algorithms. Visitor functions can basically
  * be divided into two types:
  */
-struct search_visitor
+struct default_search_visitor
 {
     // Called when a search originates from a vertex. This is called once for
     // the root of each search tree.
@@ -86,38 +86,51 @@
     { }
 };
 
-// The default visit predicate always returns true, indicating that the target
-// vertex will be visited (discovered and pushed into the buffer).
-struct default_visit_predicate
-{
+// The default search strategy is the control counterpoint of the search
+// visitor. Specifically, it provides a number of functions that can be
+// implemented to control various aspects of the search. Note that strategies
+// work just like visitors - they are copied into eqch subsequent call.
+struct default_search_strategy
+{
+    // This control point is queried at the top of the search loop when the
+    // search buffer is not empty. Returning false will cause the search to
+    // end prematurely. This control point should not be called when the buffer
+    // is empty.
+    template <typename Graph>
+    inline bool continue_vertices(Graph const& g)
+    { return true; }
+
+    // This control point is queried for each incident of the the vertex v.
+    // The vertex here is the one that was most recently examined. Returning
+    // true will allow the search of edges to continue, returning false will
+    // cause the edge loop to end prematurely.
     template <typename Graph, typename Vertex>
-    inline bool operator()(Graph const&, Vertex)
+    inline bool continue_edges(Graph const& g, Vertex v)
     { return true; }
-};
 
-// The default end predicate always returns false, indicating that the search
-// will continue.
-struct default_end_predicate
-{
-    template <typename Graph>
-    inline bool operator()(Graph const&)
-    { return false; }
+    // This control point is when when a previousl undiscovered (white) vertex
+    // is found for the first time. Returning true allows the discovery of the
+    // vertex, returning false will prevent the search from proceeding along
+    // this edge.
+    template <typename Graph, typename Vertex>
+    inline bool allow_discovery(Graph const& g, Vertex v)
+    { return true; }
 };
 
 namespace detail
 {
-    // TODO: We need a concept that abstracts stacks and queues into a in/out 
+    // TODO: We need a concept that abstracts stacks and queues into a in/out
     // search buffer. Concept maps can easily provide default functions for
     // these things - or build a concept-class. For now, we're just sticking
     // a couple of overloads in this namespace.
 #if BOOST_HAS_CONCEPTS
-concept InOutSequence<typename Container>
+concept InOutBuffer<typename Container>
 {
     typename value_type;
-    
+
     void push(Container& c, value_type const& x)
     { c.push(x); }
-    
+
     void pop(Container& c)
     { c.pop(); }
 
@@ -125,24 +138,24 @@
 };
 
 template <typename T, typename Container>
-concept_map InOutSequence<std::stack<T, Container>>
+concept_map InOutBuffer<std::stack<T, Container>>
 {
     typedef std::stack<T, Container>::value_type value_type;
-    
+
     value_type const& peek(std::stack<T, Container>& c)
     { return c.top(); }
 };
 
 template <typename T, typename Container>
-concept_map InOutSequence<std::queue<T, Container>>
+concept_map InOutBuffer<std::queue<T, Container>>
 {
     typedef std::queue<T, Container>::value_type value_type;
-    
+
     value_type const& peek(std::queue<T, Container>& c)
     { return c.front(); }
 };
 #endif
-    
+
     // Adapters for getting the current element of a buffer.
     template <typename T, typename Seq>
     inline T& peek(std::stack<T, Seq>& s)
@@ -157,34 +170,34 @@
  * Examine the edge e rooted at vertex u to determine the search action to be
  * taken (or not) for the opposite vertex.
  *
- * The visit predicate is called to determine if undiscovered (white) vertices 
+ * The visit predicate is called to determine if undiscovered (white) vertices
  * should be visited. Default search actions will always visit white vertices,
  * but these visits can be constrained or deferred by providing a predicate
  * that examines the vertex and returns false.
  *
  * @requires ReadWritePropertyMap<ColorMap>
- * @requires InOutSequence<Buffer>
+ * @requires InOutBuffer<Buffer>
  * @requires Predicate<VisitPredicate, Graph, Vertex>
  *
  * @requires SameType<ColorMap::key_type, Vertex>
  * @requires SameType<Buffer::value_type, Vertex>
  */
 template <
-    typename Graph, 
-    typename Vertex, 
-    typename Edge, 
-    typename Visitor, 
+    typename Graph,
+    typename Vertex,
+    typename Edge,
     typename ColorMap,
     typename Buffer,
-    typename VisitPredicate>
+    typename Visitor,
+    typename Strategy>
 void
-search_edge(Graph const& g, 
-            Vertex u, 
-            Edge e, 
-            Visitor vis, 
-            ColorMap color, 
+search_edge(Graph const& g,
+            Vertex u,
+            Edge e,
+            ColorMap color,
             Buffer& buf,
-            VisitPredicate visit)
+            Visitor vis,
+            Strategy strat)
 {
     typedef color_traits<typename ColorMap::value_type> ColorTraits;
 
@@ -195,7 +208,7 @@
     // Vertices are only visited if the visit() predicate returns true.
     Vertex v = e.target();
     typename ColorMap::value_type c = color(v);
-    if(c == ColorTraits::white() && visit(g, v)) {
+    if(c == ColorTraits::white() && strat.allow_discovery(g, v)) {
         color(v, ColorTraits::gray());
         buf.push(v);
 
@@ -216,19 +229,19 @@
 }
 
 template <
-    typename Graph, 
-    typename Vertex, 
-    typename Visitor, 
-    typename ColorMap, 
+    typename Graph,
+    typename Vertex,
+    typename ColorMap,
     typename Buffer,
-    typename VisitPredicate>
+    typename Visitor,
+    typename Strategy>
 void
-search_vertex(Graph const& g, 
-              Vertex u, 
-              Visitor vis, 
-              ColorMap color, 
+search_vertex(Graph const& g,
+              Vertex u,
+              ColorMap color,
               Buffer& buf,
-              VisitPredicate visit)
+              Visitor vis,
+              Strategy strat)
 {
     typedef color_traits<typename ColorMap::value_type> ColorTraits;
     typedef typename Graph::edge_descriptor Edge;
@@ -237,11 +250,12 @@
     // Examine the vertex.
     vis.examine_vertex(g, u);
 
-    // Visit adjacent vertices
+    // Visit adjacent vertices.
     EdgeRange edges = g.incident_edges(u);
-    for( ; edges.first != edges.second; ++edges.first) {
+    while(edges.first != edges.second && strat.continue_edges(g, u)) {
         directional_edge<Edge> e(*edges.first, u);
-        search_edge(g, u, e, vis, color, buf, visit);
+        search_edge(g, u, e, color, buf, vis, strat);
+        ++edges.first;
     }
     color(u, ColorTraits::black());
     vis.finish_vertex(g, u);
@@ -252,7 +266,7 @@
  * over the vertices given in the queue. This is done by popping a vertex out
  * of the buffer, and searching its adjacent neighbors.
  *
- * The visit predicate is called to determine if undiscovered (white) vertices 
+ * The visit predicate is called to determine if undiscovered (white) vertices
  * should be visited. Default search actions will always visit white vertices,
  * but these visits can be constrained or deferred by providing a predicate
  * that examines the vertex and returns false.
@@ -266,27 +280,25 @@
  * @requries Predicate<EndPredicate, Graph>
  */
 template <
-    typename Graph, 
-    typename Visitor, 
-    typename ColorMap, 
+    typename Graph,
+    typename ColorMap,
     typename Buffer,
-    typename VisitPredicate,
-    typename EndPredicate>
+    typename Visitor,
+    typename Strategy>
 void
-search_vertices(Graph const& g, 
-                Visitor vis, 
-                ColorMap color, 
+search_vertices(Graph const& g,
+                ColorMap color,
                 Buffer& buf,
-                VisitPredicate visit,
-                EndPredicate end)
+                Visitor vis,
+                Strategy strat)
 {
     typedef typename Graph::vertex_descriptor Vertex;
 
     // Continue the search until we're done with the buf.
-    while(!buf.empty() && !end(g)) {
+    while(!buf.empty() && strat.continue_vertices(g)) {
         Vertex u = detail::peek(buf);
         buf.pop();
-        search_vertex(g, u, vis, color, buf, visit);
+        search_vertex(g, u, color, buf, vis, strat);
     }
 }
 
@@ -294,21 +306,19 @@
  * Search from the given vertex to all others connected to it.
  */
 template <
-    typename Graph, 
-    typename Vertex, 
-    typename Visitor, 
-    typename ColorMap, 
+    typename Graph,
+    typename Vertex,
+    typename ColorMap,
     typename Buffer,
-    typename VisitPredicate,
-    typename EndPredicate>
+    typename Visitor = default_search_visitor,
+    typename Strategy = default_search_strategy>
 void
-search_from_vertex(Graph const& g, 
-                   Vertex start, 
-                   Visitor vis, 
-                   ColorMap color, 
+search_from_vertex(Graph const& g,
+                   Vertex start,
+                   ColorMap color,
                    Buffer& buf,
-                   VisitPredicate visit = default_visit_predicate(),
-                   EndPredicate end = default_end_predicate())
+                   Visitor vis = Visitor(),
+                   Strategy strat = Strategy())
 {
     typedef color_traits<typename ColorMap::value_type> ColorTraits;
 
@@ -317,42 +327,40 @@
     buf.push(start);
     vis.start_vertex(g, start);
     vis.discover_vertex(g, start);
-    search_vertices(g, vis, color, buf, visit, end);
+    search_vertices(g, color, buf, vis, strat);
 }
 
 /**
- * Perform a multi-root search from the vertices given in the range [f, l). 
+ * Perform a multi-root search from the vertices given in the range [f, l).
  * This is done by seeding the search buffer with the given vertices prior
  * to executing a standard search.
  */
 template <
-    typename Graph, 
-    typename Iter, 
-    typename Visitor, 
-    typename ColorMap, 
-    typename Buffer,
-    typename VisitPredicate,
-    typename EndPredicate>
+    typename Graph,
+    typename Iter,
+    typename Visitor,
+    typename ColorMap,
+    typename Buffer = default_search_visitor,
+    typename Strategy = default_search_strategy>
 void
-search_from_vertices(Graph const& g, 
-                     Iter f, Iter l, 
-                     Visitor vis, 
-                     ColorMap color, 
+search_from_vertices(Graph const& g,
+                     Iter first, Iter last,
+                     ColorMap color,
                      Buffer buf,
-                     VisitPredicate visit = default_visit_predicate(),
-                     EndPredicate end = default_end_predicate())
+                     Visitor vis = Visitor(),
+                     Strategy strat = Strategy())
 {
     typedef color_traits<typename ColorMap::value_type> ColorTraits;
     typedef typename Graph::vertex_descriptor Vertex;
 
-    for( ; f != l; ++f) {
-        Vertex v = *f;
+    for( ; first != last; ++first) {
+        Vertex v = *first;
         color(v, ColorTraits::gray());
         buf.push(v);
         vis.start_vertex(g, v);
         vis.discover_vertex(g, v);
     }
-    search_vertices(g, vis, color, buf, visit, end);
+    search_vertices(g, color, buf, vis, strat);
 }
 
 /**
@@ -362,19 +370,17 @@
  * vertex set of the graph.
  */
 template <
-    typename Graph, 
-    typename Visitor, 
-    typename Buffer, 
+    typename Graph,
     typename ColorMap,
-    typename VisitPredicate,
-    typename EndPredicate>
+    typename Buffer,
+    typename Visitor = default_search_visitor,
+    typename Strategy = default_search_strategy>
 void
-search_graph(Graph const& g, 
-             Visitor vis, 
-             ColorMap color, 
+search_graph(Graph const& g,
+             ColorMap color,
              Buffer& buf,
-             VisitPredicate visit = default_visit_predicate(),
-             EndPredicate end = default_end_predicate())
+             Visitor vis = Visitor(),
+             Strategy strat = Strategy())
 {
     typedef color_traits<typename ColorMap::value_type> ColorTraits;
     typedef typename Graph::vertex_descriptor Vertex;
@@ -388,9 +394,92 @@
             // out edges, but can be reached from some other vertex v'. Here,
             // v will not be part of the tree rooted by v' even though it is
             // reachable.
-            search_from_vertex(g, v, vis, color, buf, visit, end);
+            search_from_vertex(g, v, color, buf, vis, strat);
         }
     }
 }
 
+// The search_for() functions use a specific search strategy that terminates
+// the search when a target vertex is located.
+
+// This strategy will continue the search until the target vertex has been
+// found. This strategy does not visit the target vertex.
+template <typename Graph, typename Vertex>
+struct search_for_strategy
+{
+    search_for_strategy(Vertex const& v, bool& f)
+        : target(v), found(f)
+    { }
+
+    // Return true if the target vertex has been found.
+    inline bool continue_vertices(Graph const& g)
+    { return !found; }
+
+    inline bool continue_edges(Graph const& g, Vertex v)
+    { return !found; }
+
+    // Set found to true if the target vertex has been found. Return 
+    inline bool allow_discovery(Graph const& g, Vertex v)
+    {
+        if(v == target) found = true;
+        return !found;
+    }
+
+    Vertex const& target;
+    bool& found;
+};
+
+/**
+ * Search for the target vertex tgt starting from the source vertex src. This
+ * function returns true if the vertex is found, false otherwise.
+ *
+ * This works best as a BFS.
+ */
+template <
+    typename Graph,
+    typename Vertex,
+    typename ColorMap,
+    typename Buffer,
+    typename Visitor = default_search_visitor>
+bool
+search_for(Graph const& g,
+           Vertex src,
+           Vertex tgt,
+           ColorMap color,
+           Buffer& buf,
+           Visitor vis = Visitor())
+{
+    bool found = (src == tgt);
+    search_for_strategy<Graph, Vertex> strat(tgt, found);
+    search_from_vertex(g, src, color, buf, vis, strat);
+    return strat.found;
+}
+
+/**
+ * Search for the target vertex tgt starting from the vertices given in the
+ * range [first, last). Return true if the vertex is found, false otherwise.
+ *
+ * This works best as a BFS.
+ */
+template <
+    typename Graph,
+    typename Vertex,
+    typename Iter,
+    typename ColorMap,
+    typename Buffer,
+    typename Visitor = default_search_visitor>
+bool
+search_for(Graph const& g,
+           Iter first, Iter last,
+           Vertex tgt,
+           ColorMap color,
+           Buffer& buf,
+           Visitor vis = Visitor())
+{
+    bool found = (std::find(first, last, tgt) != last);
+    search_for_strategy<Graph, Vertex> strat(tgt, found);
+    search_from_vertices(g, first, last, color, buf, vis, strat);
+    return strat.found;
+}
+
 #endif

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first/algorithm.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first/algorithm.hpp	2008-08-12 11:36:29 EDT (Tue, 12 Aug 2008)
@@ -0,0 +1,120 @@
+
+#ifndef DEPTH_FIRST_ALGORITHM_HPP
+#define DEPTH_FIRST_ALGORITHM_HPP
+
+#include <stack>
+
+template <typename Graph, typename Vertex, typename Edge, typename Visitor, typename ColorMap, typename Stack>
+void
+depth_first_visit_edge(Graph const& g, Vertex u, Edge e, Visitor vis, ColorMap color, Stack& stack)
+{
+    typedef color_traits<typename ColorMap::value_type> ColorTraits;
+
+    // Examine the edge before checking it.
+    vis.examine_edge(g, e);
+
+    // Look at the color of the target vertex and decide what to do with it.
+    Vertex v = e.target();
+    typename ColorMap::value_type c = color(v);
+    if(c == ColorTraits::white()) {
+        color(v) = ColorTraits::gray();
+        stack.push(v);
+
+        // Discover the vertex and claim that its a tree edge.
+        vis.discover_vertex(g, v);
+        vis.tree_edge(g, e);
+    }
+    else {
+        // Handle other cases - nontree edges, gray targets, black, etc.
+        if(c == ColorTraits::gray()) {
+            vis.back_edge(g, e);
+        }
+        else {
+            vis.cross_edge(g, e);
+        }
+    }
+}
+
+template <typename Graph, typename Vertex, typename Visitor, typename ColorMap, typename Stack>
+void
+depth_first_visit_vertex(Graph const& g, Vertex u, Visitor vis, ColorMap color, Stack& stack)
+{
+    typedef color_traits<typename ColorMap::value_type> ColorTraits;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef typename Graph::incident_edge_range EdgeRange;
+
+    // Examine the vertex.
+    vis.examine_vertex(g, u);
+
+    // Visit adjacent vertices
+    EdgeRange edges = g.incident_edges(u);
+    for( ; edges.first != edges.second; ++edges.first) {
+        directional_edge<Edge> e(*edges.first, u);
+        depth_first_visit_edge(g, u, e, vis, color, stack);
+    }
+    color(u) = ColorTraits::black();
+    vis.finish_vertex(g, u);
+}
+
+template <typename Graph, typename Visitor, typename ColorMap, typename Stack>
+void
+depth_first_walk(Graph const& g, Visitor vis, ColorMap color, Stack& stack)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+
+    // Continue the search until we're done with the stack.
+    while(!stack.empty()) {
+        Vertex u = stack.top();
+        stack.pop();
+        depth_first_visit_vertex(g, u, vis, color, stack);
+    }
+}
+
+template <
+    typename Graph,
+    typename Vertex,
+    typename Visitor,
+    typename ColorMap = optional_vertex_map<Graph, color>,
+    typename Stack = std::stack<typename Graph::vertex_descriptor>>
+void
+depth_first_visit(Graph const& g, Vertex start, Visitor vis, ColorMap color = ColorMap(), Stack stack = Stack())
+{
+    typedef color_traits<typename ColorMap::value_type> ColorTraits;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef typename Graph::incident_edge_range EdgeRange;
+
+    detail::optional_prop_init(g, color, ColorTraits::white());
+
+    // Initialize the start vertex and put it in the stack.
+    color(start) = ColorTraits::gray();
+    stack.push(start);
+    vis.discover_vertex(g, start);
+    depth_first_walk(g, vis, color, stack);
+}
+
+template <
+    typename Graph,
+    typename Iter,
+    typename Visitor,
+    typename ColorMap = optional_vertex_map<Graph, color>,
+    typename Stack = std::stack<typename Graph::vertex_descriptor>>
+void
+depth_first_visit(Graph const& g, Iter f, Iter l, Visitor vis, ColorMap color = ColorMap(), Stack stack = Stack())
+{
+    typedef color_traits<typename ColorMap::value_type> ColorTraits;
+    typedef typename Graph::vertex_descriptor Vertex;
+
+    detail::optional_prop_init(g, color, ColorTraits::white());
+
+    // Initialize the start vertices and put them into the stack.
+    for( ; f != l; ++f) {
+        Vertex v = *f;
+        color(v) = ColorTraits::gray();
+        stack.push(v);
+        vis.discover_vertex(g, *f);
+    }
+    depth_first_walk(g, vis, color, stack);
+}
+
+
+#endif