C++ and generic graph distance algorithm

Question

My problem is the following. I am learning C++ by writing a graph library and want to make use of as much generic programming techniques as possible; hence, answering my question through "use BOOST" will not help me; in fact, I tried looking through BOOST's code for an answer to my question, but it was a humbling experience, since I can't even figure out where certain functions are defined; just way too high level of C++ for learning from it at my level.

That said, my library is templated in the following way:

class edge { ... };

template <class edge_T>
class node { ... };

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

and I am creating more complex graphs by using classes derived from edge or node, so a weighted edge class would be simply

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

   ...
};

The problem now is that I want to implement an algorithm on this structure that computes the shortest distance between two vertices. I could easily write two of these, one for weighted edges and one for unweighted, but the change is tiny: one would access a member field of weighted_edge (or derived classes) and the other would assume unitary weight.

Is there a way of doing this, so that I can have just one piece of code for both cases?

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

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

which is not exactly user-friendly, or at least confusing, since you don't expect that there should be any weights involved.

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

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 would happen if one passed a derived class? Is there a C++ mechanism that would select the 'closer' base class out of these two?

Answer 1

_{Up front: I assume you have thought of making getWeight() a virtual method in the base edge class (and make the default implementation return 1). I'm aware of the limitations in flexibility of this approach, just wanted to check.}

---

Because I didn't understand the purpose of your return type templae, I assumed that you wanted to deduce the return type, which you can do using my solution.

The usual way to make get_weight select the right implementation is to use template specialization (note that the code you show specializes by return type; by definition this type would never be deduced 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 could employ result_of<edge::weight> (boost/TR1) or decltype(edge::weight) (C++0x) to avoid hardcoding the result_type typedefs. This would be true induction.

Update 2 To get the overload for weighted_edge const& to 'service' derived edge types as well apply a little 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;
}

Answer 2

Thanks for the response, sehe; I figured out the optimal solution for my problem. It is 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); }

This way, when I write a shortest-path algorithm it can ask for the weight of either of these two classes or any derived ones, which is important to me because I might want to add properties to the base edge classes later on (like colors, etc.). Hence, 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 would not be able to use the prescribed behavior on all classes descending from edge, and distinguishing that from the behavior for weighted_edge.