[BGL] Limited depth search without O(number_of_verices) complexity?
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
On Sat, 12 Jan 2013, Ilja Honkonen wrote:
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, ...>?
Look at depth_first_visit_impl in <boost/graph/depth_first_search.hpp>; that appears to have a way to terminate the search early. I have asked about getting the link mentioned in that code working again. -- Jeremiah Willcock
On Mon, Jan 14, 2013 at 11:18 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 12 Jan 2013, Ilja Honkonen wrote:
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, ...>?
Look at depth_first_visit_impl in <boost/graph/depth_first_search.hpp>; that appears to have a way to terminate the search early. I have asked about getting the link mentioned in that code working again.
-- Jeremiah Willcock
You can also supply a custom color map. I think if you look for examples using the two_bit_color_map, you'll be able to figure out how to do this using something like a boost::unordered_map, which should use on the order of the number of touched items memory. Brian
15.01.2013 11:23, Brian Budge kirjoitti:
You can also supply a custom color map. I think if you look for examples using the two_bit_color_map, you'll be able to figure out how to do this using something like a boost::unordered_map, which should use on the order of the number of touched items memory.
Would that be an internal or an external color map? According to documentation (http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/using_property_maps.html) an external color property must have space for the color of each vertex: ..."The random access iterator must point to the beginning of a range of property values, and the length of the range must be the number of vertices or edges in the graph"... Ilja
15.01.2013 11:23, Brian Budge пишет:
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, ...>? You can also supply a custom color map. I think if you look for examples using the two_bit_color_map, you'll be able to figure out how to do this using something like a boost::unordered_map, which should use on the order of the number of touched items memory.
I've been looking at various files for a while now and have only found examples where an external vector is used for the map and no hint on how to use something else. Or does the following code in bfs.hpp have something to do with this (use vertex_color or something)? choose_const_pmap(get_param(params, vertex_index), g, vertex_index)), The color map seems to be a template parameter everywhere except in places which add at least one more layer of indirection with bgl_named_params. Also it looks like the two_bit_color_map constructor always allocates memory for all vertices anyway. This page http://stackoverflow.com/questions/11666131/color-map-in-boost-graph-breadth... looks promising but even a simple program in that style doesn't compile: typedef adjacency_list<vecS, vecS, undirectedS> Graph_T; property_map<Graph_T, vertex_color_t>::type colors; /usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ”struct boost::vec_adj_list_any_vertex_pa::bind_<boost::vertex_color_t, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, boost::no_property>”: /usr/include/boost/graph/detail/adjacency_list.hpp:2592:12: required from ”struct boost::detail::vec_adj_list_choose_vertex_pa<boost::vertex_color_t, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, boost::no_property>” /usr/include/boost/graph/detail/adjacency_list.hpp:2718:12: required from ”struct boost::vec_adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, boost::no_property, boost::vertex_color_t>” /usr/include/boost/graph/properties.hpp:217:12: required from ”struct boost::detail::vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, boost::vertex_color_t>” /usr/include/boost/graph/properties.hpp:228:10: required from ”struct boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, boost::vertex_color_t>” graafitesti.cpp:38:46: required from here /usr/include/boost/graph/detail/adjacency_list.hpp:2541:29: virhe: forming reference to void typedef value_type& reference; ^ /usr/include/boost/graph/detail/adjacency_list.hpp:2542:35: virhe: forming reference to void typedef const value_type& const_reference; ^ /usr/include/boost/graph/detail/adjacency_list.hpp:2545:55: virhe: forming reference to void <Graph, Graph*, value_type, reference, Tag> type; ^ /usr/include/boost/graph/detail/adjacency_list.hpp:2547:67: virhe: forming reference to void <Graph, const Graph*, value_type, const_reference, Tag> const_type; ^ Something is apparently missing but what and from where? Or what should be the first parameter of property_map in this case? Ilja
On Jan 17, 2013 11:56 AM, "Ilja Honkonen" <ilja.honkonen@helsinki.fi> wrote:
15.01.2013 11:23, Brian Budge пишет:
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, ...>?
You can also supply a custom color map. I think if you look for
examples using the two_bit_color_map, you'll be able to figure out how to do this using something like a boost::unordered_map, which should use on the order of the number of touched items memory.
I've been looking at various files for a while now and have only found examples where an external vector is used for the map and no hint on how to use something else. Or does the following code in bfs.hpp have something to do with this (use vertex_color or something)? choose_const_pmap(get_param(params, vertex_index), g, vertex_index)),
The color map seems to be a template parameter everywhere except in places which add at least one more layer of indirection with bgl_named_params.
I am away from my computer for a while. My best suggestion is to look through the (very readable) source for depth_first_visit for how the template argument gets used. I supplied my own external map and had to supply get and put functions correspondingly. Brian
14.01.2013 21:18, Jeremiah Willcock kirjoitti:
Look at depth_first_visit_impl in <boost/graph/depth_first_search.hpp>; that appears to have a way to terminate the search early. I have asked about getting the link mentioned in that code working again.
I was using the terminator condition of depth_first_visit but couldn't figure out how to use the internal color property with that function. Is that possible? I looked in boost/graph/ but found only examples where the color map includes all vertices (and is external) instead of only those visited. Ilja
participants (3)
-
Brian Budge -
Ilja Honkonen -
Jeremiah Willcock