Parallel inheritance trees, where classes from one tree have containers of classes from another

Question

I really didn't know how to specify the problem in the title, so here's the gist of it.

I am writing graph classes Graph, Node, and Edge, and then subclassing them into VisGraph, VisNode and VisEdge to obtain a drawable graph (in C++). I then need to further subclass those into specific classes that depend on certain data. So I have a lot of parallel inheritance:

Graph -- VisGraph -- RouteGraph

Node  -- VisNode  -- RouteNode

Edge  -- VisEdge  -- RouteEdge

This is pretty ugly and I started out doing this, so that I would implement functionality incrementally, but there are a lot of problems. One of them, for example, is that the base class has a container of all the Node instances in the graph. The problem is, if I am in a function in VisGraph dealing with a VisNode, that requires functionality unique to VisNode, I have to do a dynamic_cast on the Nodes that I get from the container in the base class.

Perhaps I should write a "Vis" class that holds a Graph and draws it? I found inheritance convenient because each node/edge could easily draw itself instead of me storing extra information outside about position etc. and drawing them all individually.

Do you have any suggestions/design patterns that could make this more elegant?

Thank you in advance.

Answer 1

If in doubt, throw templates at the problem until it surrenders:

template <typename N, typename E>
class Graph {
    std::vector<N> nodes;
    std::vector<E> edges;
};

typedef Graph<VisNode, VisEdge> VisGraph;
typedef Graph<RouteNode, RouteEdge> RouteGraph;

You lose the inheritance (RouteGraph no longer inherits from VisGraph), but that's normal in C++ for container types, and Graph is somewhat like a container. You can keep the inheritance between Node -> VisNode -> RouteNode, though.

Since nodes and edges are supposed to be of matching types, you could go even further, and give Graph a single template parameter, which itself is a class containing the edge and node types as typedefs. I'm not sure it's worth it, though.

Edit

Since you want to successively add functions, you could keep a form of inheritance but lose the polymorphism:

template <typename N, typename E>
class GraphImpl {
    std::vector<N> nodes;
    std::vector<E> edges;
};

template <typename N, typename E>
class VisGraphImpl : public GraphImpl<N, E> {
    // constructors

    // extra functions
};

template <typename N, typename E>
class RouteGraphImpl : public VisGraphImpl<N, E> {
    // constructors

    // extra functions
};

typedef GraphImpl<Node, Edge> Graph;
typedef VisGraphImpl<VisNode, VisEdge> VisGraph;
typedef RouteGraphImpl<RouteNode, RouteEdge> RouteGraph;

There might be a better way, though, by bundling these extra functions up into sensible mixins and using CRTP:

template<typename Derived>
class VisFunctions {
    void somfunc() {
        myself = static_cast<Derived&>(*this);
        // do stuff
    }
};

Then:

class VisGraph : public Graph<VisNode, VisEdge>, public VisFunctions<VisGraph> {
    friend class VisFunctions<VisGraph>;
};

class RouteGraph : public Graph<RouteNode, RouteEdge>, public VisFunctions<RouteGraph>, public RouteFunctions<RouteGraph> {
    friend class VisFunctions<RouteGraph>;
    friend class RouteFunctions<RouteGraph>;
};

Not sure how that'll look for your real circumstances, though. Btw, if you don't want/need the friend declaration for the extra functions, then you don't need those extra functions to be members at all - just make them free functions that take a VisGraph or RouteGraph parameter.