[Boost-commit] svn:boost r48393 - in sandbox/SOC/2008/graphs: branches/walking trunk/boost/graphs trunk/boost/graphs/algorithms

From: asutton_at_[hidden]
Date: 2008-08-26 11:27:35

Author: asutton
Date: 2008-08-26 11:27:34 EDT (Tue, 26 Aug 2008)
New Revision: 48393
URL: http://svn.boost.org/trac/boost/changeset/48393

Log:
Rewrote the BFS/DFS search implementations to use the search core. Not
entirely happy with the interface (it's a little incomplete). Needs
polishing.

Moved the optinal property initialization code out to properties.hpp.

Added:
   sandbox/SOC/2008/graphs/branches/walking/
      - copied from r48390, /sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/old/
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp |    25 +++++++++++++++++--------               
   sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp   |    27 +++++++++++++++++----------             
   sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search.hpp        |     1 -                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp       |    30 ------------------------------          
   sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp               |    34 ++++++++++++++++++++++++++++++++++      
   5 files changed, 68 insertions(+), 49 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp	2008-08-26 11:27:34 EDT (Tue, 26 Aug 2008)
@@ -11,17 +11,26 @@
 
 #include <boost/graphs/algorithms/search.hpp>
 
-// A BFS search visitor is a basically just a search visitor.
-struct bfs_visitor : search_visitor { };
 
-
-template <typename Graph, typename Visitor, typename ColorMap = optional_vertex_map<Graph, color>>
+/**
+ * Execute a breadth-first search over the graph.
+ */
+template <
+    typename Graph,
+    typename Visitor = default_search_visitor,
+    typename ColorMap = optional_vertex_map<Graph, color>>
 void
-breadth_first_search(Graph const& g, Visitor vis, ColorMap color = ColorMap())
+breadth_first_search(Graph const& g,
+                     Visitor vis = Visitor(),
+                     ColorMap color = ColorMap())
 {
-    std::queue<typename Graph::vertex_descriptor> buf;
-    detail::optional_prop_init(g, color, color_traits<typename ColorMap::value_type>::white());
-    search_graph(g, vis, color, buf);
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef std::queue<Vertex> Queue;
+    typedef color_traits<typename ColorMap::value_type> ColorTraits;
+
+    Queue q;
+    initialize(g, color, ColorTraits::white());
+    search_graph(g, color, q, vis);
 }
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp	2008-08-26 11:27:34 EDT (Tue, 26 Aug 2008)
@@ -11,18 +11,25 @@
 
 #include <boost/graphs/algorithms/search.hpp>
 
-// A DFS search visitor is a just a search visitor.
-struct dfs_visitor : search_visitor { };
-
-
-template <typename Graph, typename Visitor, typename ColorMap = optional_vertex_map<Graph, color>>
+/**
+ * Execute a breadth-first search over the graph.
+ */
+template <
+    typename Graph,
+    typename Visitor = default_search_visitor,
+    typename ColorMap = optional_vertex_map<Graph, color>>
 void
-depth_first_search(Graph const& g, Visitor vis, ColorMap color = ColorMap())
+depth_first_search(Graph const& g,
+                   Visitor vis = Visitor(),
+                   ColorMap color = ColorMap())
 {
-    std::stack<typename Graph::vertex_descriptor> buf;
-    detail::optional_prop_init(g, color, color_traits<typename ColorMap::value_type>::white());
-    search(g, vis, buf, color);
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef std::stack<Vertex> Stack;
+    typedef color_traits<typename ColorMap::value_type> ColorTraits;
+
+    Stack s;
+    initialize(g, color, ColorTraits::white());
+    search_graph(g, color, s, vis);
 }
 
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search.hpp	2008-08-26 11:27:34 EDT (Tue, 26 Aug 2008)
@@ -9,7 +9,6 @@
 #include <boost/graphs/properties.hpp>
 #include <boost/graphs/algorithms/utility.hpp>
 
-// Include the search algorithm.
 #include <boost/graphs/algorithms/search/visitor.hpp>
 #include <boost/graphs/algorithms/search/strategy.hpp>
 #include <boost/graphs/algorithms/search/algorithm.hpp>

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp	2008-08-26 11:27:34 EDT (Tue, 26 Aug 2008)
@@ -2,34 +2,4 @@
 #ifndef ALGORITHM_UTILITY_HPP
 #define ALGORITHM_UTILITY_HPP
 
-namespace detail
-{
-    // Optionally initialize the container, but not if the map is already
-    // initialized.
-    template <typename Graph, typename Map>
-    void do_opt_init(Graph const& g, Map& map, typename Map::value_type x)
-    {
-        if(!map.container) {
-            Map t(g, x);
-            map.swap(t);
-        }
-    }
-
-    // Delayed initialization of optional property maps. The default solution
-    // is to do nothing (i.e,. the map is already initialized). Specialized
-    // variants simply swap the given map with one that's actually initialized.
-    template <typename Graph, typename Map>
-    void optional_prop_init(Graph const&, Map&, typename Map::value_type)
-    { }
-
-    template <typename Graph, typename Prop>
-    void optional_prop_init(Graph const& g, optional_vertex_map<Graph, Prop>& map, Prop x)
-    { do_opt_init(g, map, x); }
-
-    template <typename Graph, typename Prop>
-    void optional_prop_init(Graph const g, optional_edge_map<Graph, Prop>& map, Prop x)
-    { do_opt_init(g, map, x); }
-
-}
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp	2008-08-26 11:27:34 EDT (Tue, 26 Aug 2008)
@@ -249,4 +249,38 @@
     { }
 };
 
+
+namespace detail
+{
+    // Optionally initialize the container, but not if the map is already
+    // initialized.
+    template <typename Graph, typename Map>
+    void optional_init(Graph const& g, Map& map, typename Map::value_type x)
+    {
+        if(!map.container) {
+            Map tmp(g, x);
+            map.swap(tmp);
+        }
+    }
+}
+
+/**
+ * Delayed initialization of optional property maps. The default solution
+ * is to do nothing (i.e,. the map is already initialized). Specialized
+ * variants simply swap the given map with one that's actually initialized.
+ */
+template <typename Graph, typename Map>
+void initialize(Graph const&, Map&, typename Map::value_type)
+{ }
+
+template <typename Graph, typename Prop>
+void initialize(Graph const& g, optional_vertex_map<Graph, Prop>& map, Prop x)
+{ detail::optional_init(g, map, x); }
+
+template <typename Graph, typename Prop>
+void initialize(Graph const g, optional_edge_map<Graph, Prop>& map, Prop x)
+{ detail::optional_init(g, map, x); }
+
+
+
 #endif