[Boost-users] [BGL] Limited depth search without O(number_of_verices) complexity?

Subject: [Boost-users] [BGL] Limited depth search without O(number_of_verices) complexity?
From: Ilja Honkonen (ilja.honkonen_at_[hidden])
Date: 2013-01-12 13:27:20

Hello

Is it possible to do a limited depth depth first search without using 
O(N) additional memory? The following code seems to visit only a part of 
the graph but it still requires O(N) memory for the external color map. 
Could that be avoided with an internal color map? I didn't manage to get 
depth_first_visit(...) to use an internal color map. Would the solution 
work also with other graph types besides <vecS, vecS, ...>?

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;
using namespace boost;

struct custom_dfs_visitor : public default_dfs_visitor
{
     template < typename Vertex, typename Graph >
     void discover_vertex(const Vertex& v, const Graph& g) const
     {
         cout << v << endl;
     }
};

struct Terminator {
     template<class Vertex, class Graph>
     bool operator()(const Vertex& v, const Graph& g)
     {
         return v > 2;
     }
};

int main()
{
     typedef adjacency_list<
         vecS,
         vecS,
         undirectedS
     > Graph_T;

     Graph_T g(6);
     add_edge(0, 1, g);
     add_edge(1, 2, g);
     add_edge(2, 3, g);
     add_edge(3, 4, g);
     add_edge(4, 5, g);

     vector<default_color_type> color_map(num_vertices(g));
     depth_first_visit(
         g,
         vertex(0, g),
         custom_dfs_visitor(),
         make_iterator_property_map(
             color_map.begin(),
             get(vertex_index, g),
             color_map[0]
         ),
         Terminator()
     );
     cout << "size: " << color_map.size() << endl;

     return 0;
}

Thanks
Ilja