C ++ and the general graph distance algorithm

Question

My problem is as follows. I learn C ++ by writing a graph library and want to use as many common programming methods as possible; therefore, the answer to my question through “using BOOST” will not help me; in fact, I tried to look at the BOOST code to answer my question, but it was a humble experience, since I cannot even determine where certain functions are defined; just too high a level of C ++ for training at my level.

However, my library is templated as follows:

class edge { ... }; template <class edge_T> class node { ... }; template <class edge_T, class node_T> class graph { ... }; 

and I create more complex graphs using classes derived from edge or node, so the weighted edge class will be just

 template <class T> class weighted_edge : public edge { public: T weight; ... }; 

Now the problem is that I want to implement an algorithm of this structure that calculates the shortest distance between two vertices. I could easily write two of them: one for weighted edges and one for unweighted ones, but the change is tiny: you could access the field of the weighted_edge element (or derived classes), and the other a unitary weight.

Is there a way to do this, so that I can only have one piece of code for both cases?

One solution is to use the member function edge::get_weight() , which will return the weight (or "1" in the unweighted case), but that would force me to use a certain type of weight for the edge class, which is unweighted, so it smells funny. I mean, the template should be

 template <class T> class edge { public: ... virtual T get_weight(void) { return T(1); } } 

which is not entirely user friendly or at least confusing, as you do not expect any weights to be there.

BGL uses the get() function to get the weight; I could write a function that returns 1 or weight depending on edge_T , but my concern is what happens when it comes from edge or weighted_edge ? If you write:

 template <class T> inline T get_weight(edge & e) { return T(1); } template <class T> inline T get_weight(weighted_edge & e) { return T(e.weight); } 

what happens if you pass a derived class? Is there a C ++ mechanism that would choose a “closer” base class from these two?

Answer 1

Thanks for the answer, sehe; I decided the best solution for my problem. He has to write two functions,

 template <class T> inline T get_weight(edge const & e) { return T(1); } template <class T> inline T get_weight(weighted_edge const & e) { return T(e.weight); } 

Thus, when I write the shortest path algorithm, it can ask for the weight of either of these two classes or any derivatives , which is important for me because I might want to add properties to the base edge classes later (for example, colors, etc.) . Therefore, when I write

 class my_edge : public edge { ... }; my_edge e; 

and use get_weight(e) I will get the behavior for the unweighted edge. Templating on the edge type would not help here, because it could not use the prescribed behavior for all classes descending from edge , and differences from the behavior for weighted_edge .

Answer 2

_{Upstairs . I assume that you were getWeight() making getWeight() virtual method in the base class edge (and making the default implementation implement 1). I know about the limitations in the flexibility of this approach, I just wanted to check. Sub>}

---

Since I did not understand the purpose of your return type templae type, I assumed that you want to infer a return value type that you can do using my solution.

The usual way to make get_weight choose the correct implementation is to use specialized specialization (note that the code you show specializes in the return type; by definition, this type will never be output by the compiler):

 namespace detail { template <class Edge> struct get_weight_impl; template <> struct get_weight_impl<edge> { typedef typename result_type int; result_type operator()(const edge& e) const { return result_type(1); } }; template <> struct get_weight_impl<weighted_edge> { typedef typename result_type int; result_type operator()(const weighted_edge& e) const { return result_type(e.weight); } }; } 

Update 1 . You can use result_of<edge::weight> (boost / TR1) or decltype(edge::weight) (C ++ 0x) to avoid hard coding typedefs result_type . This will be true induction.

Update 2 . To get the overload for weighted_edge const& for the "related" derived edge types, apply a bit of type_trait magic:

http://ideone.com/AqmsL

 struct edge {}; struct weighted_edge : edge { virtual double get_weight() const { return 3.14; } }; struct derived_edge : weighted_edge { virtual double get_weight() const { return 42; } }; template <typename E, bool is_weighted> struct edge_weight_impl; template <typename E> struct edge_weight_impl<E, false> { typedef int result_type; int operator()(const E& e) const { return 1; } }; template <typename E> struct edge_weight_impl<E, true> { // typedef decltype(E().weight()) result_type; // c++0x typedef double result_type; result_type operator()(const E& e) const { return e.get_weight(); } }; template <typename E> typename edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>::result_type get_weight(const E& e) { return edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>()(e); } int main() { edge e; weighted_edge we; derived_edge de; std::cout << "--- static polymorphism" << std::endl; std::cout << "edge:\t" << get_weight(e) << std::endl; std::cout << "weighted_edge:\t" << get_weight(we) << std::endl; std::cout << "derived_edge:\t" << get_weight(de) << std::endl; // use some additional enable_if to get rid of this: std::cout << "bogus:\t" << get_weight("bogus") << std::endl; std::cout << "\n--- runtime polymorphism" << std::endl; edge* ep = &e; std::cout << "edge:\t" << get_weight(*ep) << std::endl; weighted_edge* wep = &we; std::cout << "weighted_edge:\t" << get_weight(*wep) << std::endl; wep = &de; std::cout << "bogus:\t" << get_weight(*wep) << std::endl; }