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