|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-08-12 11:52:21
Author: asutton
Date: 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
New Revision: 48103
URL: http://svn.boost.org/trac/boost/changeset/48103
Log:
Migrated the advanced search over the old search and exploded it into an
algorithm module. Also, completely rewrote the visitor aspect to use
composable visitors employing the latest in variadic templates.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/algorithm.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/detail.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/strategy.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/visitor.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/advanced_search.hpp | 485 ----------------------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search.hpp | 212 ----------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 4
sandbox/SOC/2008/graphs/trunk/libs/graphs/README | 13
4 files changed, 21 insertions(+), 693 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:52:20 EDT (Tue, 12 Aug 2008)
@@ -1,485 +0,0 @@
-
-#ifndef ADVANCED_SEARCH_HPP
-#define ADVANCED_SEARCH_HPP
-
-#include <stack>
-#include <queue>
-
-#include <boost/graphs/colors.hpp>
-#include <boost/graphs/properties.hpp>
-#include <boost/graphs/algorithms/utility.hpp>
-
-// 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,
-// on_start_vertex(lambda).
-// on_discover_vertex(labmda));
-// 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.
-
-/**
- * The default search visitor provdes a number of "hooks" that can be overridden
- * to implement a number of various algorithms. Visitor functions can basically
- * be divided into two types:
- */
-struct default_search_visitor
-{
- // Called when a search originates from a vertex. This is called once for
- // the root of each search tree.
- template <typename Graph, typename Vertex>
- inline void start_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when the vertex is popped from the stack. Not all examined
- // vertices are discovered (e.g., a start vertex). Use this event to
- // record the depth-first ordering of vertices.
- template <typename Graph, typename Vertex>
- inline void examine_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when a vertex is encountered for the first time. Discovered
- // vertices are examined unless the algorithm terminates before they are
- // popped from the stack.
- template <typename Graph, typename Vertex>
- inline void discover_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when all of the incident edges of the vertex have been examined.
- template <typename Graph, typename Vertex>
- inline void finish_vertex(Graph const& g, Vertex v)
- { }
-
- // Called for every incident edge of a vertex being examined. Examined
- // edges are classified by the color of their targets at the time of
- // investigation.
- template <typename Graph, typename Edge>
- inline void examine_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge that becomes part of the search tree. A
- // tree edge is one whose source is being examined and whose target is
- // discovered.
- template <typename Graph, typename Edge>
- inline void tree_edge(Graph const& g, Edge e)
- { }
-
- // Called for eacch edge that is not a tree edge (i.e., whose target has
- // already been discovered). Specific types of non-tree edges can be
- // classified as back or cross edges depending on the color of the target.
- template <typename Graph, typename Edge>
- inline void non_tree_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge whose target is in the search buffer. Back
- // edges, cross edges, and forward edges are nontree edges.
- template <typename Graph, typename Edge>
- inline void back_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge whose target has already been removed from
- // the search buffer. Technically, this is either a cross edge or a forward
- // edge, but there's no way to easily distinguish them.
- template <typename Graph, typename Edge>
- inline void cross_edge(Graph const& g, Edge e)
- { }
-};
-
-// 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 continue_edges(Graph const& g, Vertex v)
- { return true; }
-
- // 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
- // 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 InOutBuffer<typename Container>
-{
- typename value_type;
-
- void push(Container& c, value_type const& x)
- { c.push(x); }
-
- void pop(Container& c)
- { c.pop(); }
-
- value_type const& peek(Container&);
-};
-
-template <typename T, typename 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 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)
- { return s.top(); }
-
- template <typename T, typename Seq>
- inline T& peek(std::queue<T, Seq>& s)
- { return s.front(); }
-}
-
-/**
- * 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
- * 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 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 ColorMap,
- typename Buffer,
- typename Visitor,
- typename Strategy>
-void
-search_edge(Graph const& g,
- Vertex u,
- Edge e,
- ColorMap color,
- Buffer& buf,
- Visitor vis,
- Strategy strat)
-{
- 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.
- // 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() && strat.allow_discovery(g, v)) {
- color(v, ColorTraits::gray());
- buf.push(v);
-
- // Discover the vertex and claim that its a tree edge.
- vis.discover_vertex(g, v);
- vis.tree_edge(g, e);
- }
- else {
- // Signal a non-tree edge and classify it.
- vis.non_tree_edge(g, e);
- if(c == ColorTraits::gray()) {
- vis.back_edge(g, e);
- }
- else {
- vis.cross_edge(g, e);
- }
- }
-}
-
-template <
- typename Graph,
- typename Vertex,
- typename ColorMap,
- typename Buffer,
- typename Visitor,
- typename Strategy>
-void
-search_vertex(Graph const& g,
- Vertex u,
- ColorMap color,
- Buffer& buf,
- Visitor vis,
- Strategy strat)
-{
- 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);
- while(edges.first != edges.second && strat.continue_edges(g, u)) {
- directional_edge<Edge> e(*edges.first, u);
- search_edge(g, u, e, color, buf, vis, strat);
- ++edges.first;
- }
- color(u, ColorTraits::black());
- vis.finish_vertex(g, u);
-}
-
-/**
- * Exucte a search (either breadth or depth, depending on the search buffer)
- * 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
- * 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.
- *
- * The end predicate is called to determine if the search should continue or
- * not. The end predicate returning true will end the search prematurely.
- * Default search actions will not end prematurely.
- *
- * @requires ReadWritePropertyMap<ColorMap>
- * @requires Predicate<VisitPredicate, Graph, Vertex>
- * @requries Predicate<EndPredicate, Graph>
- */
-template <
- typename Graph,
- typename ColorMap,
- typename Buffer,
- typename Visitor,
- typename Strategy>
-void
-search_vertices(Graph const& g,
- ColorMap color,
- Buffer& buf,
- Visitor vis,
- Strategy strat)
-{
- typedef typename Graph::vertex_descriptor Vertex;
-
- // Continue the search until we're done with the buf.
- while(!buf.empty() && strat.continue_vertices(g)) {
- Vertex u = detail::peek(buf);
- buf.pop();
- search_vertex(g, u, color, buf, vis, strat);
- }
-}
-
-/**
- * Search from the given vertex to all others connected to it.
- */
-template <
- typename Graph,
- typename Vertex,
- typename ColorMap,
- typename Buffer,
- typename Visitor = default_search_visitor,
- typename Strategy = default_search_strategy>
-void
-search_from_vertex(Graph const& g,
- Vertex start,
- ColorMap color,
- Buffer& buf,
- Visitor vis = Visitor(),
- Strategy strat = Strategy())
-{
- typedef color_traits<typename ColorMap::value_type> ColorTraits;
-
- // Initialize the start vertex and put it in the buf.
- color(start, ColorTraits::gray());
- buf.push(start);
- vis.start_vertex(g, start);
- vis.discover_vertex(g, start);
- search_vertices(g, color, buf, vis, strat);
-}
-
-/**
- * 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 = default_search_visitor,
- typename Strategy = default_search_strategy>
-void
-search_from_vertices(Graph const& g,
- Iter first, Iter last,
- ColorMap color,
- Buffer buf,
- Visitor vis = Visitor(),
- Strategy strat = Strategy())
-{
- typedef color_traits<typename ColorMap::value_type> ColorTraits;
- typedef typename Graph::vertex_descriptor Vertex;
-
- 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, color, buf, vis, strat);
-}
-
-/**
- * Perform a search over the entire graph, visiting all vertices.
- *
- * This is done by performing a search at each undiscovered vertex in the
- * vertex set of the graph.
- */
-template <
- typename Graph,
- typename ColorMap,
- typename Buffer,
- typename Visitor = default_search_visitor,
- typename Strategy = default_search_strategy>
-void
-search_graph(Graph const& g,
- ColorMap color,
- Buffer& buf,
- Visitor vis = Visitor(),
- Strategy strat = Strategy())
-{
- typedef color_traits<typename ColorMap::value_type> ColorTraits;
- typedef typename Graph::vertex_descriptor Vertex;
- typedef typename Graph::vertex_range VertexRange;
-
- VertexRange verts = g.vertices();
- for( ; verts.first != verts.second; ++verts.first) {
- Vertex v = *verts.first;
- if(color(v) == ColorTraits::white()) {
- // TODO: Interesting problemm... Suppose v is white, but has no
- // 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, 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
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-12 11:52:20 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>
@@ -9,209 +9,9 @@
#include <boost/graphs/properties.hpp>
#include <boost/graphs/algorithms/utility.hpp>
-// Things to consider:
-// A predicate for visiting vertices. Can only visit if white and pred(v).
-// A predicate for stopping, invoked
-
-/**
- * The default search visitor provdes a number of "hooks" that can be overridden
- * to implement a number of various algorithms. Visitor functions can basically
- * be divided into two types:
- */
-struct search_visitor
-{
- // Called when a search originates from a vertex. This is called once for
- // the root of each search tree.
- template <typename Graph, typename Vertex>
- inline void start_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when the vertex is popped from the stack. Not all examined
- // vertices are discovered (e.g., a start vertex). Use this event to
- // record the depth-first ordering of vertices.
- template <typename Graph, typename Vertex>
- inline void examine_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when a vertex is encountered for the first time. Discovered
- // vertices are examined unless the algorithm terminates before they are
- // popped from the stack.
- template <typename Graph, typename Vertex>
- inline void discover_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when all of the incident edges of the vertex have been examined.
- template <typename Graph, typename Vertex>
- inline void finish_vertex(Graph const& g, Vertex v)
- { }
-
- // Called for every incident edge of a vertex being examined. Examined
- // edges are classified by the color of their targets at the time of
- // investigation.
- template <typename Graph, typename Edge>
- inline void examine_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge that becomes part of the search tree. A
- // tree edge is one whose source is being examined and whose target is
- // discovered.
- template <typename Graph, typename Edge>
- inline void tree_edge(Graph const& g, Edge e)
- { }
-
- // Called for eacch edge that is not a tree edge (i.e., whose target has
- // already been discovered). Specific types of non-tree edges can be
- // classified as back or cross edges depending on the color of the target.
- template <typename Graph, typename Edge>
- inline void non_tree_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge whose target is in the search buffer. Back
- // edges, cross edges, and forward edges are nontree edges.
- template <typename Graph, typename Edge>
- inline void back_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge whose target has already been removed from
- // the search buffer. Technically, this is either a cross edge or a forward
- // edge, but there's no way to easily distinguish them.
- template <typename Graph, typename Edge>
- inline void cross_edge(Graph const& g, Edge e)
- { }
-};
-
-namespace detail
-{
- // Adapters for getting the current element of a buffer.
- template <typename T, typename Seq>
- inline T& peek(std::stack<T, Seq>& s)
- { return s.top(); }
-
- template <typename T, typename Seq>
- inline T& peek(std::queue<T, Seq>& s)
- { return s.front(); }
-}
-
-template <typename Graph, typename Vertex, typename Edge, typename Visitor, typename ColorMap, typename Buffer>
-void
-search_edge(Graph const& g, Vertex u, Edge e, Visitor vis, ColorMap color, Buffer& buf)
-{
- 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());
- buf.push(v);
-
- // Discover the vertex and claim that its a tree edge.
- vis.discover_vertex(g, v);
- vis.tree_edge(g, e);
- }
- else {
- // Signal a non-tree edge and classify it.
- vis.non_tree_edge(g, e);
- 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 Buffer>
-void
-search_vertex(Graph const& g, Vertex u, Visitor vis, ColorMap color, Buffer& buf)
-{
- 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);
- search_edge(g, u, e, vis, color, buf);
- }
- color(u, ColorTraits::black());
- vis.finish_vertex(g, u);
-}
-
-template <typename Graph, typename Visitor, typename ColorMap, typename Buffer>
-void
-search_vertices(Graph const& g, Visitor vis, ColorMap color, Buffer& buf)
-{
- typedef typename Graph::vertex_descriptor Vertex;
-
- // Continue the search until we're done with the buf.
- while(!buf.empty()) {
- Vertex u = detail::peek(buf);
- buf.pop();
- search_vertex(g, u, vis, color, buf);
- }
-}
-
-// @requires SameType<Vertex, Graph::vertex_descriptor>
-template <typename Graph, typename Vertex, typename Visitor, typename ColorMap, typename Buffer>
-void
-search_from_vertex(Graph const& g, Vertex start, Visitor vis, ColorMap color, Buffer& buf)
-{
- typedef color_traits<typename ColorMap::value_type> ColorTraits;
-
- // Initialize the start vertex and put it in the buf.
- color(start, ColorTraits::gray());
- buf.push(start);
- vis.start_vertex(g, start);
- vis.discover_vertex(g, start);
- search_vertices(g, vis, color, buf);
-}
-
-// @requires InputIterator Iter
-// @requires SameType<Dereferenceable<Iter>::reference, Graph::vertex_descriptor>
-template <typename Graph, typename Iter, typename Visitor, typename ColorMap, typename Buffer>
-void
-search_from_vertices(Graph const& g, Iter f, Iter l, Visitor vis, ColorMap color, Buffer buf)
-{
- typedef color_traits<typename ColorMap::value_type> ColorTraits;
- typedef typename Graph::vertex_descriptor Vertex;
-
- for( ; f != l; ++f) {
- Vertex v = *f;
- color(v, ColorTraits::gray());
- buf.push(v);
- vis.start_vertex(g, v);
- vis.discover_vertex(g, v);
- }
- search_vertices(g, vis, color, buf);
-}
-
-template <typename Graph, typename Visitor, typename Buffer, typename ColorMap>
-void
-search_graph(Graph const& g, Visitor vis, ColorMap color, Buffer& buf)
-{
- typedef color_traits<typename ColorMap::value_type> ColorTraits;
- typedef typename Graph::vertex_descriptor Vertex;
- typedef typename Graph::vertex_range VertexRange;
-
- VertexRange verts = g.vertices();
- for( ; verts.first != verts.second; ++verts.first) {
- Vertex v = *verts.first;
- if(color(v) == ColorTraits::white()) {
- // TODO: Interesting problemm... Suppose v is white, but has no
- // 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);
- }
- }
-}
+// 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>
#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/algorithm.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/algorithm.hpp 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
@@ -0,0 +1,333 @@
+
+#ifndef BOOST_GRAPHS_ALGORITHMS_SEARCH_ALGORITHM_HPP
+#define BOOST_GRAPHS_ALGORITHMS_SEARCH_ALGORITHM_HPP
+
+#include <boost/graphs/algorithms/search/detail.hpp>
+
+// This file contains the implementatin of the search core. Specifically, this
+// includes:
+// - search_edge
+// - search_vertex
+// - search_vertices
+// - search_from_vertex
+// - search_from_vertices
+// - search_graph
+// - search_for (x2)
+
+/**
+ * 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
+ * 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 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 ColorMap,
+ typename Buffer,
+ typename Visitor,
+ typename Strategy>
+void
+search_edge(Graph const& g,
+ Vertex u,
+ Edge e,
+ ColorMap color,
+ Buffer& buf,
+ Visitor vis,
+ Strategy strat)
+{
+ 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.
+ // 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() && strat.allow_discovery(g, v)) {
+ color(v, ColorTraits::gray());
+ buf.push(v);
+
+ // Discover the vertex and claim that its a tree edge.
+ vis.discover_vertex(g, v);
+ vis.tree_edge(g, e);
+ }
+ else {
+ // Signal a non-tree edge and classify it.
+ vis.non_tree_edge(g, e);
+ if(c == ColorTraits::gray()) {
+ vis.back_edge(g, e);
+ }
+ else {
+ vis.cross_edge(g, e);
+ }
+ }
+}
+
+template <
+ typename Graph,
+ typename Vertex,
+ typename ColorMap,
+ typename Buffer,
+ typename Visitor,
+ typename Strategy>
+void
+search_vertex(Graph const& g,
+ Vertex u,
+ ColorMap color,
+ Buffer& buf,
+ Visitor vis,
+ Strategy strat)
+{
+ 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);
+ while(edges.first != edges.second && strat.continue_edges(g, u)) {
+ directional_edge<Edge> e(*edges.first, u);
+ search_edge(g, u, e, color, buf, vis, strat);
+ ++edges.first;
+ }
+ color(u, ColorTraits::black());
+ vis.finish_vertex(g, u);
+}
+
+/**
+ * Exucte a search (either breadth or depth, depending on the search buffer)
+ * 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
+ * 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.
+ *
+ * The end predicate is called to determine if the search should continue or
+ * not. The end predicate returning true will end the search prematurely.
+ * Default search actions will not end prematurely.
+ *
+ * @requires ReadWritePropertyMap<ColorMap>
+ * @requires Predicate<VisitPredicate, Graph, Vertex>
+ * @requries Predicate<EndPredicate, Graph>
+ */
+template <
+ typename Graph,
+ typename ColorMap,
+ typename Buffer,
+ typename Visitor,
+ typename Strategy>
+void
+search_vertices(Graph const& g,
+ ColorMap color,
+ Buffer& buf,
+ Visitor vis,
+ Strategy strat)
+{
+ typedef typename Graph::vertex_descriptor Vertex;
+
+ // Continue the search until we're done with the buf.
+ while(!buf.empty() && strat.continue_vertices(g)) {
+ Vertex u = detail::peek(buf);
+ buf.pop();
+ search_vertex(g, u, color, buf, vis, strat);
+ }
+}
+
+/**
+ * Search from the given vertex to all others connected to it.
+ */
+template <
+ typename Graph,
+ typename Vertex,
+ typename ColorMap,
+ typename Buffer,
+ typename Visitor = default_search_visitor,
+ typename Strategy = default_search_strategy>
+void
+search_from_vertex(Graph const& g,
+ Vertex start,
+ ColorMap color,
+ Buffer& buf,
+ Visitor vis = Visitor(),
+ Strategy strat = Strategy())
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+
+ // Initialize the start vertex and put it in the buf.
+ color(start, ColorTraits::gray());
+ buf.push(start);
+ vis.start_vertex(g, start);
+ vis.discover_vertex(g, start);
+ search_vertices(g, color, buf, vis, strat);
+}
+
+/**
+ * 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 = default_search_visitor,
+ typename Strategy = default_search_strategy>
+void
+search_from_vertices(Graph const& g,
+ Iter first, Iter last,
+ ColorMap color,
+ Buffer buf,
+ Visitor vis = Visitor(),
+ Strategy strat = Strategy())
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::vertex_descriptor Vertex;
+
+ 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, color, buf, vis, strat);
+}
+
+/**
+ * Perform a search over the entire graph, visiting all vertices.
+ *
+ * This is done by performing a search at each undiscovered vertex in the
+ * vertex set of the graph.
+ */
+template <
+ typename Graph,
+ typename ColorMap,
+ typename Buffer,
+ typename Visitor = default_search_visitor,
+ typename Strategy = default_search_strategy>
+void
+search_graph(Graph const& g,
+ ColorMap color,
+ Buffer& buf,
+ Visitor vis = Visitor(),
+ Strategy strat = Strategy())
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::vertex_range VertexRange;
+
+ VertexRange verts = g.vertices();
+ for( ; verts.first != verts.second; ++verts.first) {
+ Vertex v = *verts.first;
+ if(color(v) == ColorTraits::white()) {
+ // TODO: Interesting problemm... Suppose v is white, but has no
+ // 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, 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/search/detail.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/detail.hpp 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
@@ -0,0 +1,55 @@
+
+#ifndef BOOST_GRAPHS_ALGORITHMS_SEARCH_DETAIL_HPP
+#define BOOST_GRAPHS_ALGORITHMS_SEARCH_DETAIL_HPP
+
+
+namespace detail
+{
+ // 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 InOutBuffer<typename Container>
+{
+ typename value_type;
+
+ void push(Container& c, value_type const& x)
+ { c.push(x); }
+
+ void pop(Container& c)
+ { c.pop(); }
+
+ value_type const& peek(Container&);
+};
+
+template <typename T, typename 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 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)
+ { return s.top(); }
+
+ template <typename T, typename Seq>
+ inline T& peek(std::queue<T, Seq>& s)
+ { return s.front(); }
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/strategy.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/strategy.hpp 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
@@ -0,0 +1,44 @@
+
+#ifndef BOOST_GRAPHS_ALGORITHMS_SEARCH_STRATEGY_HPP
+#define BOOST_GRAPHS_ALGORITHMS_SEARCH_STRATEGY_HPP
+
+/**
+ * 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 continue_edges(Graph const& g, Vertex v)
+ { return true; }
+
+ /**
+ * 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; }
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/visitor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/search/visitor.hpp 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
@@ -0,0 +1,288 @@
+
+#ifndef BOOST_GRAPHS_ALGORITHMS_SEARCH_VISITOR_HPP
+#define BOOST_GRAPHS_ALGORITHMS_SEARCH_VISITOR_HPP
+
+
+/**
+ * The default search visitor provdes a number of "hooks" that can be overridden
+ * to implement a number of various algorithms. Visitor functions can basically
+ * be divided into two types:
+ */
+struct default_search_visitor
+{
+ /**
+ * Called when a search originates from a vertex. This is called once for
+ * the root of each search tree.
+ */
+ template <typename Graph, typename Vertex>
+ inline void start_vertex(Graph const& g, Vertex v)
+ { }
+
+ /**
+ * Called when the vertex is popped from the stack. Not all examined
+ * vertices are discovered (e.g., a start vertex). Use this event to
+ * record the depth-first ordering of vertices.
+ */
+ template <typename Graph, typename Vertex>
+ inline void examine_vertex(Graph const& g, Vertex v)
+ { }
+
+ /**
+ * Called when a vertex is encountered for the first time. Discovered
+ * vertices are examined unless the algorithm terminates before they are
+ * popped from the stack.
+ */
+ template <typename Graph, typename Vertex>
+ inline void discover_vertex(Graph const& g, Vertex v)
+ { }
+
+ /**
+ * Called when all of the incident edges of the vertex have been examined.
+ */
+ template <typename Graph, typename Vertex>
+ inline void finish_vertex(Graph const& g, Vertex v)
+ { }
+
+ /**
+ * Called for every incident edge of a vertex being examined. Examined
+ * edges are classified by the color of their targets at the time of
+ * investigation.
+ */
+ template <typename Graph, typename Edge>
+ inline void examine_edge(Graph const& g, Edge e)
+ { }
+
+ /**
+ * Called for each examined edge that becomes part of the search tree. A
+ * tree edge is one whose source is being examined and whose target is
+ * discovered.
+ */
+ template <typename Graph, typename Edge>
+ inline void tree_edge(Graph const& g, Edge e)
+ { }
+
+ /**
+ * Called for eacch edge that is not a tree edge (i.e., whose target has
+ * already been discovered). Specific types of non-tree edges can be
+ * classified as back or cross edges depending on the color of the target.
+ */
+ template <typename Graph, typename Edge>
+ inline void non_tree_edge(Graph const& g, Edge e)
+ { }
+
+ /**
+ * Called for each examined edge whose target is in the search buffer. Back
+ * edges, cross edges, and forward edges are nontree edges.
+ */
+ template <typename Graph, typename Edge>
+ inline void back_edge(Graph const& g, Edge e)
+ { }
+
+ /**
+ * Called for each examined edge whose target has already been removed from
+ * the search buffer. Technically, this is either a cross edge or a forward
+ * edge, but there's no way to easily distinguish them.
+ */
+ template <typename Graph, typename Edge>
+ inline void cross_edge(Graph const& g, Edge e)
+ { }
+};
+
+
+/**
+ * The search visitor provides a framework for housing an aggregation of other
+ * search visitors. This enables users to construct compound visitors on the
+ * fly. Use the make_search_visitor function to aggregate visitors at the
+ * call site.
+ */
+template <typename... Visitors> struct search_visitor;
+
+// Defines the base case for the visitor. The base case is derived from the
+// default visitor, which implements a number of empty functions.
+template<> struct search_visitor<> : default_search_visitor { };
+
+// The recursive case splits the the visitors into the head and tail and derives
+// from the dispatch as a mixin. The dispatch type implements the functions
+// that are responsible for the executution of the visitors.
+template <typename Head, typename... Tail>
+struct search_visitor<Head, Tail...> : private search_visitor<Tail...>
+{
+ search_visitor()
+ : search_visitor<Tail...>(), vis()
+ { }
+
+ search_visitor(Head head, Tail... tail)
+ : search_visitor<Tail...>(tail...), vis(head)
+ { }
+
+ // This is the basic dispatch interface. Each of these functions dispatches
+ // the visit call to the head, then distributes it to all other visitors
+ // in the tail.
+ template <typename Graph, typename Vertex>
+ inline void start_vertex(Graph const& g, Vertex v)
+ { vis.start_vertex(g, v); search_visitor<Tail...>(*this).start_vertex(g, v); }
+
+ template <typename Graph, typename Vertex>
+ inline void examine_vertex(Graph const& g, Vertex v)
+ { vis.examine_vertex(g, v); search_visitor<Tail...>(*this).examine_vertex(g, v); }
+
+ template <typename Graph, typename Vertex>
+ inline void discover_vertex(Graph const& g, Vertex v)
+ { vis.discover_vertex(g, v); search_visitor<Tail...>(*this).discover_vertex(g, v); }
+
+ template <typename Graph, typename Vertex>
+ inline void finish_vertex(Graph const& g, Vertex v)
+ { vis.finish_vertex(g, v); search_visitor<Tail...>(*this).finish_vertex(g, v); }
+
+ template <typename Graph, typename Edge>
+ inline void examine_edge(Graph const& g, Edge e)
+ { vis.examine_edge(g, e); search_visitor<Tail...>(*this).examine_edge(g, e); }
+
+ template <typename Graph, typename Edge>
+ inline void tree_edge(Graph const& g, Edge e)
+ { vis.tree_edge(g, e); search_visitor<Tail...>(*this).tree_edge(g, e); }
+
+ template <typename Graph, typename Edge>
+ inline void non_tree_edge(Graph const& g, Edge e)
+ { vis.non_tree_edge(g, e); search_visitor<Tail...>(*this).non_tree_edge(g, e); }
+
+ template <typename Graph, typename Edge>
+ inline void back_edge(Graph const& g, Edge e)
+ { vis.back_edge(g, e); search_visitor<Tail...>(*this).back_edge(g, e); }
+
+ template <typename Graph, typename Edge>
+ inline void cross_edge(Graph const& g, Edge e)
+ { vis.cross_edge(g, e); search_visitor<Tail...>(*this).cross_edge(g, e); }
+
+ Head vis;
+};
+
+// The make function....
+template <typename... Visitors>
+search_visitor<Visitors...>
+make_search_visitor(Visitors const&... visitors)
+{ return search_visitor<Visitors...>(visitors...); }
+
+
+// These are a bunch of helpers that can turn function objects (free functions,
+// Boost.Functions, and lambda functions?) into search visitors. This is done
+// by overriding the member function call in the default visitor with a function
+// object defined in the derived visitor. For the time being, it would seem that
+// we need to have visitor objects for each desired overload.
+//
+// NOTE: Although these functions don't really give signatures, they certainly
+// have to follow certian conventsion. Specifically:
+// - Vertex visiting functions must have the signature void (Graph, Vertex).
+// - Edge visiting functions must have the signature void (Graph, Edge).
+//
+// TODO: Extend these visitors with overloads that accept Boost.Lambda objects.
+
+template <typename Function>
+struct start_vertex_visitor : default_search_visitor
+{
+ start_vertex_visitor(Function f) : start_vertex(f) { }
+ Function start_vertex;
+};
+
+template <typename Function>
+struct examine_vertex_visitor : default_search_visitor
+{
+ examine_vertex_visitor(Function f) : examine_vertex(f) { }
+ Function examine_vertex;
+};
+
+template <typename Function>
+struct discover_vertex_visitor : default_search_visitor
+{
+ discover_vertex_visitor(Function f) : discover_vertex(f) { }
+ Function discover_vertex;
+};
+
+template <typename Function>
+struct finish_vertex_visitor : default_search_visitor
+{
+ finish_vertex_visitor(Function f) : finish_vertex(f) { }
+ Function finish_vertex;
+};
+
+template <typename Function>
+struct examine_edge_visitor : default_search_visitor
+{
+ examine_edge_visitor(Function f) : examine_edge(f) { }
+ Function examine_edge;
+};
+
+template <typename Function>
+struct tree_edge_visitor : default_search_visitor
+{
+ tree_edge_visitor(Function f) : tree_edge(f) { }
+ Function tree_edge;
+};
+
+template <typename Function>
+struct non_tree_edge_visitor : default_search_visitor
+{
+ non_tree_edge_visitor(Function f) : non_tree_edge(f) { }
+ Function non_tree_edge;
+};
+
+template <typename Function>
+struct cross_edge_visitor : default_search_visitor
+{
+ cross_edge_visitor(Function f) : cross_edge(f) { }
+ Function cross_edge;
+};
+
+template <typename Function>
+struct back_edge_visitor : default_search_visitor
+{
+ back_edge_visitor(Function f) : back_edge(f) { }
+ Function back_edge;
+};
+
+template <typename Function>
+start_vertex_visitor<Function>
+on_start_vertex(Function f)
+{ return start_vertex_visitor<Function>(f); }
+
+template <typename Function>
+examine_vertex_visitor<Function>
+on_examine_vertex(Function f)
+{ return examine_vertex_visitor<Function>(f); }
+
+template <typename Function>
+discover_vertex_visitor<Function>
+on_discover_vertex(Function f)
+{ return discover_vertex_visitor<Function>(f); }
+
+template <typename Function>
+finish_vertex_visitor<Function>
+on_finish_vertex(Function f)
+{ return finish_vertex_visitor<Function>(f); }
+
+template <typename Function>
+examine_edge_visitor<Function>
+on_examine_edge(Function f)
+{ return examine_edge_visitor<Function>(f); }
+
+template <typename Function>
+tree_edge_visitor<Function>
+on_tree_edge(Function f)
+{ return tree_edge_visitor<Function>(f); }
+
+template <typename Function>
+non_tree_edge_visitor<Function>
+on_non_tree_edge(Function f)
+{ return non_tree_edge_visitor<Function>(f); }
+
+template <typename Function>
+cross_edge_visitor<Function>
+on_cross_edge(Function f)
+{ return cross_edge_visitor<Function>(f); }
+
+template <typename Function>
+back_edge_visitor<Function>
+on_back_edge(Function f)
+{ return back_edge_visitor<Function>(f); }
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
@@ -19,4 +19,6 @@
# exe bfs : bfs.cpp ;
# exe dfs : dfs.cpp ;
-exe search : search.cpp ;
\ No newline at end of file
+# exe search : search.cpp ;
+exe adv_search : adv_search.cpp ;
+exe vis : visitors.cpp ;
\ No newline at end of file
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/README
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/README (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/README 2008-08-12 11:52:20 EDT (Tue, 12 Aug 2008)
@@ -59,4 +59,15 @@
Q: Why does the out iterator need a pointer back to the out store?
Because you can't translate between the wrapped iterator and a descriptor to
the wrapped iterator without a reference to the container. If descritpors were
-self-translating, this wouldn't be a problem...
\ No newline at end of file
+self-translating, this wouldn't be a problem...
+
+
+Q: Why did you give up on the idea of iterable algorithms? Several reasons.
+First, it's important to know exactly where to divide the algorithm - what's
+the current status of the algorithm at each step. This is extremely difficult
+to generalize because each algorithm does things a little bit differently. It's
+not terribly hard for BFS/DFS, but it doesn't make a lot of sense for spanning
+trees or shortest paths. Second, splitting the algorithm adds a lot of overhead,
+causing the implemetnation to be significantly slower than a function. Finally,
+with lamdba expressions and variadic templates, it shouldn't be too hard to
+simply inline your visitors... Ideally, anyway.
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk