[boost] [BGL] Patch to add buffer parameter to dfs

From: Bruce Barr (schmoost_at_[hidden])
Date: 2003-09-01 00:29:33

Here's a patch to depth_first_search.hpp that allows a buffer parameter to be
used with depth_first_search().  I'm also including a patch to
depth_first_search.html to update the documentation.  The patches apply to CVS
revision 1.37 of depth_first_search.hpp, and 1.14 of depth_first_search.html.

The patch allows the named parameter version of depth_first_search() to have an
optional buffer(Buffer& S) parameter included among the other named parameters.
 Also, the non-named parameter version allows an additional Buffer& S
parameter.

Actually, I was all set to add an overload to depth_first_visit() too, but it
seems that to add another parameter after the func parameter, you'd have to
pass detail::nontruth2() as the value for func.  I'd rather add a Buffer
parameter before TerminatorFunc, but that would screw up other people's code.

The changes are generally patterned after the way the buffer parameter is
handled in breadth_first_search().

I've also create an additional traits class, dfs_buffer_traits, to allow the
user to declare the correct value_type for the buffer.

If no buffer parameter is used, reallocations of the search stack will be
greatly reduced, especially with large graphs.  However, if the user happens to
know in advance that the search depth will not go beyond a certain point,
reallocations can be eliminated by passing in a custom buffer as follows:

template <typename T>
struct ReserveStack : public std::stack<T, std::vector<T> > {
  void reserve(size_type size) { c.reserve(size); }
};

int main()
{
  // ...
  typedef dfs_buffer_traits<Graph>::value_type BufferValueType;
  typedef ReserveStack<BufferValueType> StackType;
  const StackType::size_type maxSearchDepth = 100;
  StackType s;
  s.reserve(maxSearchDepth);
  depth_first_search(g, visitor(vis).buffer(s));
  // ...
}

Also, if allocating the entire stack in one block of memory is a bad idea, a
deque-based stack could be used instead:

int main()
{
  // ...
  typedef dfs_buffer_traits<Graph>::value_type BufferValueType;
  std::stack<BufferValueType> s;
  depth_first_search(g, visitor(vis).buffer(s));
  // ...
}

If the user defines BOOST_RECURSIVE_DFS, the older recursive code is used, but
the behavior of the search will have nothing to do with whatever type of Buffer
parameter is passed in.  So, this could be a source of future "unexpected
behavior".

The modifications to the HTML file includes the addition of the new parameter,
a reworking the of the starting vertex parameter to match the actual code, and
a few other minor fixes.

Bruce Barr,
schmoost <at> yahoo.com,
visit ubcomputer.com

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com