Setup

I have a graph library where I am trying to decompose things as much as possible, and the cleanest way to describe it that I found is the following: there is a vanilla type node implementing only a list of edges:

class node
{
   public:
      int* edges;
      int edge_count;
};

Then, I would like to be able to add interfaces to this whole mix, like so:

template <class T>
class node_weight
{
   public:
      T weight;
};

template <class T>
class node_position
{
   public:
      T x;
      T y;
};

and so on. Then, the actual graph class comes in, which is templated on the actual type of node:

template <class node_T>
class graph
{
   protected:
      node_T* nodes;

   public:
      static graph cartesian(int n, int m)
      {
         graph r; 

         r.nodes = new node_T[n * m];

         return r;
      }
};

The twist is that it has named constructors which construct some special graphs, like a Cartesian lattice. In this case, I would like to be able to add some extra information into the graph, depending on what interfaces are implemented by node_T.

What would be the best way to accomplish this?

Possible solution

I thought of the following humble solution, through dynamic_cast<>:

template <class node_T, class weight_T, class position_T>
class graph
{
   protected:
      node_T* nodes;

   public:
      static graph cartesian(int n, int m)
      {
         graph r;

         r.nodes = new node_T[n * m];

         if (dynamic_cast<node_weight<weight_T>>(r.nodes[0]) != nullptr)
         {
            // do stuff knowing you can add weights
         }

         if (dynamic_cast<node_position<positionT>>(r.nodes[0]) != nullptr)
         {
            // do stuff knowing you can set position
         }

         return r;
      }
};

which would operate on node_T being the following:

template <class weight_T, class position_T>
class node_weight_position : 
      public node, public node_weight<weight_T>, public node_position<position_T>
{
    // ...
};

Questions

Is this -- philosophically -- the right way to go? I know people don't look nicely at multiple inheritance, though with "interfaces" like these it should all be fine.

There are unfortunately problems with this. From what I know at least, dynamic_cast<> involves quite a bit of run-time overhead. Hence, I run into a problem with what I had solved earlier: writing graph algorithms that require weights independently of whether the actual node_T class has weights or not. The solution with this 'interface' approach would be to write a function:

template <class node_T, class weight_T>
inline weight_T get_weight(node_T const & n)
{
   if (dynamic_cast<node_weight<weight_T>>(n) != nullptr)
   {
      return dynamic_cast<node_weight<weight_T>>(n).weight;
   }

   return T(1);
}

but the issue with it is that it works using run-time information (dynamic_cast), yet in principle I would like to decide it at compile-time and thus make the code more efficient.

If there is a different solution that would solve both problems, especially a cleaner and better one than what I have, I would love to hear about it!