C++ generic graph search algorithm with generic data types

Question

I'm trying to implement a generic graph search algorithm in C++, as part of assignment at university, and I encountered problems when trying to implement it, mostly struggling with templates. this is the basic UML of what I'm trying to implement

Currently I have the bfs implemented, but our instructor told us we might be requested to change the algorithm, I created the GraphAlgorithm interface which will have the findPath function, which returns vector of GraphNodes. The problem is, because GraphNode is a template class, I need to supply the template type to the algorithm, but the algorithm has nothing to do with the data type, it works with the nodes and doesn't use the data in any way. Later though, I need to access the data inside the GraphNodes. I feel that this is bad design, creating an instance of the algorithm and supplying it with the type of the nodes it is searching on.

I tried searching a type-safe generic data container in C++ without using those damned templates, and could not find anything.

Is there any alternative for this need? mainly, the GraphNode holds Point object (not specified in the UML above), but again, I prefer to make the GraphNode generic.

How would you guys implement this?

Answer 1

You don't have to directly supply the contained type to the algorithm.

There are a few choices:

Algorithm Template

The search algorithm really only needs to know that it operates on some node type, that has neighbours.

template<typename GraphNode> class GraphSearchAlgorithm { findPath(GraphNode * source, GraphNode * dest); //... } template<typename GraphNode> GraphSearchAlgorithm::findPath(GraphNode * source, GraphNode * dest) { // stuff vector<GraphNode *> neighbours = current->getNeighbours(); // more stuff } 

At the point of instantiation of this template, the compiler has to verify that GraphNode::getNeighbours fits the call site there

Type Erasure

Hide that GraphNode has a template parameter behind a non-templated base class, and use that base in the algorithm

class GraphNodeBase { virtual std::vector<GraphNodeBase *> getNeighbours() = 0; } template<typename T> class GraphNode : public GraphNodeBase { /*...*/ }