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?
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.