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