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?