a class inheritance hierarchy design issue

Question

I have the following class hierarchy for graphs:

typedef vector<int> ArrayI;
typedef vector<Array<long>> Mat2DB;
typedef vector<ArrayI> adjList;

class baseGraph {
    int nodes;
    ArrayI degree;
    //some member functions.
}

class matGraph: public baseGraph {
    Mat2DB matrix;
    //member functions.
}

class lMatGraph: public matGraph {
    ArrayI labels;
    //member functions.
}

class listGraph: public baseGraph {
    adjList list;
    //member functions.
}

class lListGraph: public listGraph {
    ArrayI labels;
    //member functions.
}

Now in this class I have many other functions, mostly virtual, so that when I get to call the proper function while using the base class pointer.

For example I have a function sssp(int node) which implements single source shortest path. The implementation are both different for class matGraph and class listGraph which are adjacency matrix representation and adjacency list representation of graphs respectively. Now there is not need to change the definition for labelled version of these graphs so I do not define these functions again in lListGraph and lMatGraph

Now the only problem I am havin is with setLabel(const ArratI &) in lListGraph and lMatGraph classes. I need this function to be virtual so that it gets called through base class pointer, but at the same time I do not have anything such as labels for classes matGraph and listGraph.

I do not know if my design hierarchy is correct or not, but it seemed intuitive to me. So any comments on that would be good. What can I do with the setLabel function. Is it okay to have such a function(to me it looks like kind of a workaround so this question) or do I need to reconsider my class hierarchy.

P.S.: I would also love if there are some books from which I can practice design questions like these. I run into these delimma offten and am not sure what to do of them.

EDIT:

Use of class graph is used in another class clustering where I have a member baseGraph *graph i.e.

class clustering {
    baseGraph *graph;
}

I am storing the pointer to base class here so that I can use the different algorithms(implemented as functions) from class graph. For clustering class it again depends what type of graph I want to use.

Answer 1

Maybe this ?

typedef vector<int> ArrayI;
typedef vector<Array<long>> Mat2DB;
typedef vector<ArrayI> adjList;

class baseGraph {
    int nodes;
    ArrayI degree;
    virtual void sssp(int node);
    //some member functions.
}

class labeledGraph: public virtual baseGraph {
    ArrayI labels;
    virtual void setLabel(const ArratI &);
    //member functions.
}

class matGraph: public virtual baseGraph {
    Mat2DB matrix;
    //member functions.
}

class lMatGraph: public virtual matGraph, public virtual labeledGraph {
    //member functions.
}

class listGraph: public virtual baseGraph {
    adjList list;
    //member functions.
}

class lListGraph: public virtual listGraph, public virtual labeledGraph {
    //member functions.
}

I'm assuming here that you incorrectly inherited from graph when you should have been inheriting from baseGraph (typeo) - though even if not it comes down to same point.

Also rough coding, if you have questions or if there are mistakes feel free to ask.

Answer 2

You say that setLabel should be called through base class pointer, so this necessarily means that it should be declared in the base class, even though it doesn't make sense. You can implement setLabel for graphs that are not labelled in two possible ways:

• Do nothing - just ignore the request for setting the labels
• Throw an exception (e.g. abort) - something is probably wrong, so the user should know that!

Each way is a workaround, so you should consider why setLabel should be called through base class pointer, and possibly change this decision. I'd expect, if you really need a labelled graph for your algorithm, use the appropriate type instead of a base-class type - then you don't need to do any hacks to the base class.

Note that if you keep adding stuff to the base class that corresponds to each derived class, you are going to end up with a lot of mess in the base class - no good!

---

In addition, the following may solve your problem with setLabel and make your class hierarchy "healthier".

Consider moving your basic algorithms like sssp away from the class declarations - make them overloaded free-standing functions instead of member functions. This way you won't need to declare sssp in the base class either. If you adopt this guideline, when you implement a new algorithm, the compiler will check all function calls, and issue an error if one is missing (this is better than a crash or getting incorrect results).

class baseGraph {
    int nodes;
    ArrayI degree;
    // a minimum number of member functions (e.g. getNode; getEdges)
}

class matGraph: public graph {
    Mat2DB matrix;
}

class lMatGraph: public matGraph {
    ArrayI labels;
    void setLabel(const ArrayI &);
}

int sssp(const matGraph& graph, int node)
{
    // Some code
}

int sssp(const lMatGraph& graph, int node)
{
    // Some code; here you can use labels
}

This is discussed in the Effective C++ book (Effective C++ Item 23 Prefer non-member non-friend functions to member functions)

Answer 3

It all boils down to a simple choice. What should happen if I try to set a label in a graph that does not in fact support labels?

1. Nothing (the attempt may be logged but is otherwise ignored)
2. A catastrophic failure
3. I should not be able to even try (the compiler should not let me)

That's it. These are all your options.

The first two options are easy, you just write a virtual function that reports an error (logs it, or throws an exception).

The third one is interesting. It means there is no corresponding virtual function at all. Not in your class and not in any base class. This goes against your design but your design is not necessarily perfect.

So how do you set a label then? Through something that is not a pointer to your base class :) It can be a pointer to another base class (a mixin ― you use multiple inheritance to add labeling functionality to graphs). Or you may templatize your design so that the hierarchy does not really matter and you always statically know the most derived type of your objects.