[boost] [BGL] Proposal to add 'buffer' parameter to dfs algorithms

From: Bruce Barr (schmoost_at_[hidden])
Date: 2003-08-14 15:33:05

                               The problem

Now that the BGL algorithms based on depth first search are non-recursive,
there is an opportunity to optimize things a little.  The disadvantages with
the current setup are:

1) The stack vector in depth_first_visit_impl() in depth_first_search.hpp is
   created and destroyed with every call, which results in a lot of repeated
   and unnecessary reallocations of the vector.

2) There's no way for the user to reserve a certain capacity for the vector.

3) There's no way to use another container type, such as std::deque, to
   represent the stack.

                              The solution

These problems could all be solved by allowing the user to optionally
instantiate a container that conforms to a certain interface and pass it into
the algorithm to be used in place of the hard-wired vector.  The interface
needed has already been defined as the Buffer concept
(http://boost.org/libs/graph/doc/Buffer.html).

For example, if the user happens to know ahead of time that the search depth
will never go deeper than N, a preallocated vector-based container could be
passed in.  The container might look like the following:

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

and the usage might look like the following:

int main()
{
  // ...

  typedef MyStack<buffer_value_type> stack_type;
  const stack_type::size_type N = 100;
  stack_type s;
  s.reserve(N);
  depth_first_search(g, visitor(vis).buffer(s));
        
  // ...
}

In depth_first_visit_impl(), push(), pop(), and top() would be used in place
of push_back(), pop_back(), and back() to handle the stack.

Alternatively, an instance of stack<buffer_value_type> (or
stack<buffer_value_type, deque<buffer_value_type> >) might be passed in if
allocating the entire stack in one block of memory is a bad idea.

                        The problem with the solution

The problem with this approach is that buffer_value_type (which would need to
be pair<vertex_descriptor, pair<out_edge_iterator, out_edge_iterator> >) is
just an implementation detail that might need to change in the future.

                 The solution to the problem with the solution

This problem, in turn, can be dealt with by creating a traits class like the
following:

template <typename G>
class dfs_traits {
        typedef typename graph_traits<G>::vertex_descriptor Vertex;
        typedef typename graph_traits<G>::out_edge_iterator Iter;

public:
        typedef std::pair<Vertex, std::pair<Iter, Iter> > buffer_value_type;
};

which could be used like this:

int main()
{
  // ...

  typedef dfs_traits<MyGraph>::buffer_value_type buf_val_t;
  std::stack<buf_val_t> buff;
  depth_first_search(g, visitor(vis).buffer(buff));

  // ...
}

                          The default container type

If the buffer parameter is omitted, I think the default container type should
be std::stack<buffer_value_type, std::vector<buffer_value_type> >, although a
case could be made for using deque in place of vector
(http://gotw.ca/gotw/054.htm).

                             Like and unlike BFS

The buffer parameter usage I'm proposing here is like that used with
breadth_first_search(), but not exactly.  The difference is that BFS only
stores vertex descriptors in the buffer and has no need for a traits class
like dfs_traits.  DFS, on the other hand, needs to store a pair of out-edge
iterators along with each vertex descriptor and needs the traits class keep
some flexibility in the implementation.  The inconsistency is simply due to
the way each algorithm was implemented.

                          What would need to be done

The buffer parameter could be added to each of the DFS based algorithms:
connected_components(), strong_components(), topological_sort(),
depth_first_visit(), and depth_first_search().  Also, non-named parameter
overloads could be added to use a buffer parameter.

                                What was missed

It seems that the algorithms defined in undirected_dfs.hpp are still
implemented recursively.  It might be good idea to make the same sort of
updates to it that were (and are being) made to depth_first_search.hpp.

Adding a buffer parameter to each of this algorithms will take some effort and
will probably require some work-arounds here and there to accomodate some
compilers, but I think the added flexibility is worth it.

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