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