Function pointer to in/out_degree in BGL
Hi, I have a question regarding the boost graph library. I'd like to write a set of depth first search visitors to determine the maximum in/out-degree of a graph. The code should look pretty similar for both cases except for the function call to get the property of the visited node. boost:in_degree(node_id, graph) vs. boost:out_degree(vertexId, graph) At first glance the function signature pretty much the same, maybe: template<class Graph> graph_traits<Graph>::degree_size_type function(graph_traits<Graph>::vertex_descriptor u, const Graph &g) When looking at the BGL headers however, things seem to be a bit more complex, though. I tried to implement a generic dfs_visitor taking a general function pointer to get the in/out degree property of the visited node but I couldn't work out the type of the function pointer to be passed. All my attemtps failed badly. Hopefully, there is anybody on this list who has a better understanding of this business and could provide some help. Any hints/comments are appreciated! Thank you so much, Matthias -- View this message in context: http://boost.2283326.n4.nabble.com/Function-pointer-to-in-out-degree-in-BGL-... Sent from the Boost - Users mailing list archive at Nabble.com.
On Tue, 26 Oct 2010, langermatze wrote:
Although using a function pointer would not perform well, you could probably make it work. What errors are you getting? Most likely, you might need an explicit cast from &in_degree to the correct function pointer type for your graph; otherwise, you might get an error like "improper use of overloaded function" or such. -- Jeremiah Willcock
I tried this: typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS> Graph; typedef typename boost::graph_traits<Graph>::degree_size_type (*FuncPtrType)(typename boost::graph_traits<Graph>::vertex_descriptor, const Graph &); FuncPtrType funcPtr = boost::in_degree<Graph>; The error I'm getting: error: no matches converting function ‘in_degree’ to type ‘size_t (*)(long unsigned int, const class boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::no_property, boost::no_property, boost::listS>&)’ /usr/include/boost/graph/detail/adjacency_list.hpp:1058: error: candidates are: template<class Config> typename Config::degree_size_type boost::in_degree(typename Config::vertex_descriptor, const boost::undirected_graph_helper<C>&) /usr/include/boost/graph/detail/adjacency_list.hpp:1649: error: template<class Config> typename Config::degree_size_type boost::in_degree(typename Config::vertex_descriptor, const boost::directed_edges_helper<Config>&) Sounds reasonable since the signature of in_degree is way more complex than my function pointer signature. I couldn't find a way to get the correct Config template for my Graph class, that's why I tried to pass the Graph class itself but apparently that's not how it works. I also tried casting which ends up in the "improper use of overloaded function" error that you mentioned: FuncPtrType funcPtr = static_cast<FuncPtrType>(boost::in_degree<Graph>); error: invalid static_cast from type ‘<unresolved overloaded function type>’ to type ‘size_t (*)(long unsigned int, const boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::no_property, boost::no_property, boost::listS>&)’ As for your concerns about efficiency, I'd ultimately use the function pointer as an additional template for the visitor which then shouldn't affect code efficiency at all but avoid code duplication only. ~Matthias -- View this message in context: http://boost.2283326.n4.nabble.com/Function-pointer-to-in-out-degree-in-BGL-... Sent from the Boost - Users mailing list archive at Nabble.com.
On Wed, 27 Oct 2010, langermatze wrote:
If you're doing that, you might as well make your own function objects (that are not function pointers) that call in_degree and/or out_degree directly in their operator()() implementations. That will be faster and avoid the casting problems you are having. -- Jeremiah Willcock
On 10/27/2010 10:08 AM, Jeremiah Willcock wrote:
Thanks for this hint, Jeremiah! I haven't used function objects so far. It seems like the function object cannot be used as a template parameter directly: template<typename Graph, typename NodeProperty, boost::function<NodeProperty (const typename boost::graph_traits<Graph>::vertex_descriptor&, const Graph&)> func> struct dfs_find_max_node_property_func: public boost::default_dfs_visitor { [...] } error: ‘struct boost::function<NodeProperty ()(const typename boost::graph_traits<G>::vertex_descriptor&, const Graph&), std::allocator<void> >’ is not a valid type for a template constant parameter What happens if the function object is passed to the constructor of the dfs visitor and stored as a member variable. If this function object is called somewhere in a member function of the visitor is it actually as fast as calling the corresponding boost function directly? If the function object cannot be passed as template it seems like it is not completely known at compile. I highly doubt that the call of the function object is actually inlined. template<typename Graph, typename NodeProperty> struct dfs_find_max_node_property_func: public boost::default_dfs_visitor { public: typedef typename boost::graph_traits<Graph>::vertex_descriptor NodeId; typedef typename boost::function<NodeProperty (const NodeId&, const Graph&)> FuncType; dfs_find_max_node_property_func(FuncType f) : func(f) { }; NodeProperty some_member(const NodeId &id, const Graph &g) { return func(id,g); } NodeProperty some_other_member(const NodeId &id, const Graph &g) { return boost::in_degree(id,g); } private: FuncType func; [...] } template<class Graph> struct foo { typename boost::graph_traits<Graph>::degree_size_type operator()(const typename boost::graph_traits<Graph>::vertex_descriptor &id, const Graph &g) const { return boost::in_degree(id, g); } }; dfs_find_max_node_property_func<Graph, boost::graph_traits<Graph>::degree_size_type> dfs_find_max_in_degree(foo()); I am wondering if dfs_find_max_node_property_func::some_member and dfs_find_max_node_property_func::some_other_member really perform equally well despite the additional function object wrapping. ~Matthias
participants (3)
-
Jeremiah Willcock -
langermatze -
Matthias Schneider