[parameter] Boost.Graph program not responding at run-time
Hello all, If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong? #include <boost/parameter.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/range/irange.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/type_traits/is_convertible.hpp> #include <boost/type_traits/is_integral.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/mpl/and.hpp> #include <boost/mpl/placeholders.hpp> #include <iostream> namespace graphs { template< typename G > struct vertex_descriptor { typedef typename boost::graph_traits<G>::vertex_descriptor type; }; template< typename T > struct is_incidence_and_vertex_list_graph : boost::mpl::and_< boost::is_convertible< typename boost::graph_traits<T>::traversal_category , boost::incidence_graph_tag > , boost::is_convertible< typename boost::graph_traits<T>::traversal_category , boost::vertex_list_graph_tag > > {}; template< typename T, typename Key > struct is_property_map_of_key : boost::is_same<Key, typename boost::property_traits<T>::key_type> {}; template< typename T, typename Key > struct is_integral_property_map_of_key { typedef typename boost::mpl::and_< boost::is_integral<typename boost::property_traits<T>::value_type> , is_property_map_of_key<T, typename Key::type> >::type type; static const bool value = type::value; }; template< typename Size, typename IndexMap > boost::iterator_property_map<boost::default_color_type*, IndexMap, boost::default_color_type, boost::default_color_type&> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { std::vector<boost::default_color_type> colors(num_vertices); return &colors[0]; } template< typename graph_type, typename visitor_type, typename root_vertex_type, typename index_map_type, typename color_map_type > void depth_first_search_impl ( graph_type graph, visitor_type visitor, root_vertex_type root_vertex, index_map_type index_map, color_map_type color_map ) { boost::depth_first_search(graph, boost::visitor(visitor). color_map(color_map).root_vertex(root_vertex). vertex_index_map(index_map)); } BOOST_PARAMETER_NAME(graph) BOOST_PARAMETER_NAME(visitor) BOOST_PARAMETER_NAME(root_vertex) BOOST_PARAMETER_NAME(index_map) BOOST_PARAMETER_NAME(color_map) BOOST_PARAMETER_FUNCTION( (void), depth_first_search, tag, (required (graph, *(is_incidence_and_vertex_list_graph<boost::mpl::_>)) ) (optional (visitor, *, boost::dfs_visitor<>()) (root_vertex, (vertex_descriptor<tag::graph::_>), *boost::vertices(graph).first) (index_map, *(is_integral_property_map_of_key< boost::mpl::_, vertex_descriptor<tag::graph::_> >), boost::get(boost::vertex_index, graph)) (in_out(color_map), *(is_property_map_of_key< boost::mpl::_, vertex_descriptor<tag::graph::_> >), default_color_map(boost::num_vertices(graph), index_map)) ) ) { return depth_first_search_impl<graph_type, visitor_type, root_vertex_type, index_map_type, color_map_type>(graph, visitor, root_vertex, index_map, color_map); } } // namespace graphs template< typename TimeMap > struct dfs_time_visitor : public boost::default_dfs_visitor { typedef typename boost::property_traits<TimeMap>::value_type T; dfs_time_visitor ( TimeMap dmap, TimeMap fmap, T& t ) : dmap_(dmap), fmap_(fmap), time_(t) {} template< typename V, typename G > void discover_vertex ( V u, G const& g ) const { put(dmap_, u, time_++); } template< typename V, typename G > void finish_vertex ( V u, G const& g ) const { put(fmap_, u, time_++); } private: TimeMap dmap_; TimeMap fmap_; T& time_; }; int main ( void ) { typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> G; typedef boost::graph_traits<G>::vertices_size_type size_type; enum {u, v, w, x, y, z, N}; char names[] = {'u', 'v', 'w', 'x', 'y', 'z'}; typedef std::pair<int, int> E; E edges[] = {E(u, v), E(u, x), E(x, v), E(y, x), E(v, y), E(w, y), E(w, z), E(z, z)}; G g(edges, edges + sizeof(edges) / sizeof(E), N); std::vector<size_type> dtime(boost::num_vertices(g)); std::vector<size_type> ftime(boost::num_vertices(g)); size_type t = 0; dfs_time_visitor<size_type*> vis(&dtime[0], &ftime[0], t); graphs::depth_first_search(g, vis); std::vector<size_type> dorder(N); boost::integer_range<size_type> r(0, N); std::copy(r.begin(), r.end(), dorder.begin()); std::sort(dorder.begin(), dorder.end(), boost::indirect_cmp<size_type*, std::less<size_type> >(&dtime[0])); std::cout << "order of discovery: "; for(int i = 0; i < N; ++i) std::cout << names[dorder[i]] << " "; std::cout << std::endl; std::vector<size_type> forder(N); std::copy(r.begin(), r.end(), forder.begin()); std::sort(forder.begin(), forder.end(), boost::indirect_cmp<size_type*, std::less<size_type> >(&ftime[0])); std::cout << "order of finish: "; for(int i = 0; i < N; ++i) std::cout << names[forder[i]] << " "; std::cout << std::endl; return 0; } Thanks. --Lorenzo
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
Hello all,
If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong?
I tried your code with GCC 4.6.0 and it worked just fine as you pasted it below. I get: order of discovery: u v y x w z order of finish: x y v u z w as the result. You are returning an invalid pointer from default_color_map(), though; &colors[0] becomes invalid when colors is destroyed at the end of the function. -- Jeremiah Willcock
On Sat, Dec 3, 2011 at 2:28 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong?
I tried your code with GCC 4.6.0 and it worked just fine as you pasted it below. I get:
order of discovery: u v y x w z order of finish: x y v u z w
as the result. You are returning an invalid pointer from default_color_map(), though; &colors[0] becomes invalid when colors is destroyed at the end of the function.
Oops... thanks, that was actually the issue, after I fixed the invalid pointer the code runs fine. BTW, what's the best way to generate a default_color_map for Boost.Graph like the one below? template< typename Size, typename IndexMap > boost::iterator_property_map<boost::default_color_type*, IndexMap, boost::default_color_type, boost::default_color_type&> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { std::vector<boost::default_color_type> colors(num_vertices); return &colors[0]; // *** Error: invalid ptr... *** } BOOST_PARAMETER_NAME(graph) BOOST_PARAMETER_NAME(visitor) BOOST_PARAMETER_NAME(root_vertex) BOOST_PARAMETER_NAME(index_map) BOOST_PARAMETER_NAME(color_map) BOOST_PARAMETER_FUNCTION( (void), depth_first_search, tag, (required (graph, *(is_incidence_and_vertex_list_graph<boost::mpl::_>)) ) (optional (visitor, *, boost::dfs_visitor<>()) (root_vertex, (vertex_descriptor<tag::graph::_>), *boost::vertices(graph).first) (index_map, *(is_integral_property_map_of_key< boost::mpl::_, vertex_descriptor<tag::graph::_> >), boost::get(boost::vertex_index, graph)) (in_out(color_map), *(is_property_map_of_key< boost::mpl::_, vertex_descriptor<tag::graph::_> >), default_color_map(boost::num_vertices(graph), index_map)) // *** Note: color map used here *** ) ) { return depth_first_search_impl<graph_type, visitor_type, root_vertex_type, index_map_type, color_map_type>(graph, visitor, root_vertex, index_map, color_map); } --Lorenzo
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
On Sat, Dec 3, 2011 at 2:28 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong?
I tried your code with GCC 4.6.0 and it worked just fine as you pasted it below. I get:
order of discovery: u v y x w z order of finish: x y v u z w
as the result. You are returning an invalid pointer from default_color_map(), though; &colors[0] becomes invalid when colors is destroyed at the end of the function.
Oops... thanks, that was actually the issue, after I fixed the invalid pointer the code runs fine.
BTW, what's the best way to generate a default_color_map for Boost.Graph like the one below?
Probably the simplest is to use shared_array_property_map; you can return those from functions as shallow copies. If you write the default code in your DFS function itself, you can create the vector there and pass an iterator_property_map to the underlying DFS code (that is what the current parameter defaulting code does). -- Jeremiah Willcock
On Sat, Dec 3, 2011 at 3:16 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
On Sat, Dec 3, 2011 at 2:28 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong?
I tried your code with GCC 4.6.0 and it worked just fine as you pasted it below. I get:
order of discovery: u v y x w z order of finish: x y v u z w
as the result. You are returning an invalid pointer from default_color_map(), though; &colors[0] becomes invalid when colors is destroyed at the end of the function.
Oops... thanks, that was actually the issue, after I fixed the invalid pointer the code runs fine.
BTW, what's the best way to generate a default_color_map for Boost.Graph like the one below?
Probably the simplest is to use shared_array_property_map; you can return those from functions as shallow copies. If you write the default code in
Something like this? But this gives me again the run-time error... template< typename Size, typename IndexMap > boost::iterator_property_map<boost::default_color_type*, IndexMap, boost::default_color_type, boost::default_color_type&> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { boost::shared_array_property_map<boost::default_color_type, IndexMap> colors(num_vertices, index_map); return &colors[0]; }
your DFS function itself, you can create the vector there and pass an iterator_property_map to the underlying DFS code (that is what the current parameter defaulting code does).
Thanks. --Lorenzo
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
On Sat, Dec 3, 2011 at 3:16 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
On Sat, Dec 3, 2011 at 2:28 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong?
I tried your code with GCC 4.6.0 and it worked just fine as you pasted it below. I get:
order of discovery: u v y x w z order of finish: x y v u z w
as the result. You are returning an invalid pointer from default_color_map(), though; &colors[0] becomes invalid when colors is destroyed at the end of the function.
Oops... thanks, that was actually the issue, after I fixed the invalid pointer the code runs fine.
BTW, what's the best way to generate a default_color_map for Boost.Graph like the one below?
Probably the simplest is to use shared_array_property_map; you can return those from functions as shallow copies. If you write the default code in
Something like this? But this gives me again the run-time error...
template< typename Size, typename IndexMap > boost::iterator_property_map<boost::default_color_type*, IndexMap, boost::default_color_type, boost::default_color_type&> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { boost::shared_array_property_map<boost::default_color_type, IndexMap> colors(num_vertices, index_map); return &colors[0]; }
You don't return the iterator_property_map here; you return the shared_array_property_map itself as the result of the function. -- Jeremiah Willcock
On Sat, Dec 3, 2011 at 4:14 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
On Sat, Dec 3, 2011 at 3:16 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
On Sat, Dec 3, 2011 at 2:28 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sat, 3 Dec 2011, Lorenzo Caminiti wrote:
If I move the call to boost::depth_first_search into a template depth_first_search_impl and out of the Boost.Parameter function body, the code compiles (both MSVC and GCC with latest Boost from trunk) but the executable runs forever and prints nothing to cout... What am I doing wrong?
I tried your code with GCC 4.6.0 and it worked just fine as you pasted it below. I get:
order of discovery: u v y x w z order of finish: x y v u z w
as the result. You are returning an invalid pointer from default_color_map(), though; &colors[0] becomes invalid when colors is destroyed at the end of the function.
Oops... thanks, that was actually the issue, after I fixed the invalid pointer the code runs fine.
BTW, what's the best way to generate a default_color_map for Boost.Graph like the one below?
Probably the simplest is to use shared_array_property_map; you can return those from functions as shallow copies. If you write the default code in
Something like this? But this gives me again the run-time error...
template< typename Size, typename IndexMap > boost::iterator_property_map<boost::default_color_type*, IndexMap, boost::default_color_type, boost::default_color_type&> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { boost::shared_array_property_map<boost::default_color_type, IndexMap> colors(num_vertices, index_map); return &colors[0]; }
You don't return the iterator_property_map here; you return the shared_array_property_map itself as the result of the function.
Yes, this works: template< typename Size, typename IndexMap > boost::shared_array_property_map<boost::default_color_type, IndexMap> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { return boost::make_shared_array_property_map(num_vertices, boost::default_color_type(), index_map); } Thanks a lot. --Lorenzo
participants (2)
-
Jeremiah Willcock -
Lorenzo Caminiti