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

newer
[MultiIndex] strange problem with...

Ilja Honkonen

12 Jan 2013 12 Jan '13

6:27 p.m.

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 ? #include <iostream> #include #include 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 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 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

Show replies by date

Jeremiah Willcock

14 Jan 14 Jan

7:18 p.m.

New subject: [BGL] Limited depth search without O(number_of_verices) complexity?

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 ?

Look at depth_first_visit_impl in ; 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

Brian Budge

15 Jan 15 Jan

9:23 a.m.

New subject: [BGL] Limited depth search without O(number_of_verices) complexity?

On Mon, Jan 14, 2013 at 11:18 AM, Jeremiah Willcock 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 ?

Look at depth_first_visit_impl in ; 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

Ilja Honkonen

11:42 a.m.

New subject: [BGL] Limited depth search without O(number_of_verices) complexity?

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

Ilja Honkonen

17 Jan 17 Jan

7:55 p.m.

New subject: [BGL] Limited depth search without O(number_of_verices) complexity?

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 ? 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 Graph_T; property_map::type colors; /usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ”struct boost::vec_adj_list_any_vertex_pa::bind_, 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::no_property>” /usr/include/boost/graph/detail/adjacency_list.hpp:2718:12: required from ”struct boost::vec_adj_list_vertex_property_selector::bind_, boost::no_property, boost::vertex_color_t>” /usr/include/boost/graph/properties.hpp:217:12: required from ”struct boost::detail::vertex_property_map, boost::vertex_color_t>” /usr/include/boost/graph/properties.hpp:228:10: required from ”struct boost::property_map, 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 type; ^ /usr/include/boost/graph/detail/adjacency_list.hpp:2547:67: virhe: forming reference to void 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

Brian Budge

18 Jan 18 Jan

1:02 a.m.

New subject: [BGL] Limited depth search without O(number_of_verices) complexity?

On Jan 17, 2013 11:56 AM, "Ilja Honkonen" 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.

...

...
...
...
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 ?

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

Could 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

Ilja Honkonen

15 Jan 15 Jan

10:35 a.m.

New subject: [BGL] Limited depth search without O(number_of_verices) complexity?

14.01.2013 21:18, Jeremiah Willcock kirjoitti:

...

Look at depth_first_visit_impl in ; 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

4418

Age (days ago)

4424

Last active (days ago)

List overview

Download

6 comments

3 participants

participants (3)

Brian Budge
Ilja Honkonen
Jeremiah Willcock