I'm trying to figure out a class design for a library that operates on a weighted graph. Various algorithms may be performed on this graph, for example, finding the shortest distance between two nodes, the longest distance between two nodes, the number of paths of between two nodes where the distance is less than 10 (say), etc.
My concern is NOT how to implement the algorithm or the data structures for the graphs as I know how to do this, rather it is on the overall high-level class design. The point being that in the future we may want to add other algorithms, so the solution should be easily extensible. One option for implementing is just to write a single class that has methods for implementing each of these algorithms. Then in the future additional methods can be added to this class for any new algorithms.
public class GraphCalculator
{
Graph _graph;
public int GetLongestDistance(string startPlaceName, string endPlaceName)
{
}
public int GetShortestDistance(string startPlaceName, string endPlaceName)
{
}
public int GetNumberOfPaths(int minimumDistance)
{
}
//any new algorithms will be implemented as new methods added to this class
}
My concern is that this violates the SOLID Open/Closed principle. Should each algorithm instead be implemented in its own class? If so, what is the recommended class structure to achieve this, so that it is loosely coupled and easily testable, and how would it be called from the public API layer? Are there any recommended design patterns for this?
The answer to your question Should each algorithm instead be implemented in its own class is definitely yes! You are stating, that you want easily extensible solution. A single class that has methods for implementing each of these algorithms. Then in the future additional methods can be added to this class for any new algorithms. it not extensible at all! Your are changing the code and you need to modify your current base implementation! This is exactly the opposite of the OOP principle - closed for modification, but open for extension!
Every single algorithm you have to implement (at present or in future) is a behaviour and should be defined using an interface. All implementations should implement this common interface. This way you will also be able to test every single algorithm implementation easily on its own. This allows you also to define one list of algorithms, that is easily maintained dynamically (via code or configuration). Considering all this, what you need is some kind of a plug-in architecture.
One design pattern that matches your need could be the Visitor pattern, since it adds new operations (= algorithms like shortest path, longest path, etc.) to existing data structures (graph object).
Another option could be the PlugIn design pattern, although IMO this pattern could be more challenging to implement than the visitor. If it is alright to use 3th party software and existing frameworks, you could have a look at the Sprint plugin project, that uses the Spring framework and defines a pluggable architecture helper. A (somewhat) similar solution for .NET is the Managed Extensibility Framework and/or the Enterprise Library - Unity Application Block.