Re: [Boost-users] Function pointer to in/out_degree in BGL

Subject: Re: [Boost-users] Function pointer to in/out_degree in BGL
From: Matthias Schneider (langer.matze_at_[hidden])
Date: 2010-10-27 08:06:48

On 10/27/2010 10:08 AM, Jeremiah Willcock wrote:
> On Wed, 27 Oct 2010, langermatze wrote:
>
>>
>> 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.
>
> 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

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