Algorithms as objects
A discussion of using C++ classes to encapsulate certain algorithms that allow them to be dynamically replaceable. Two alternative approaches are presented: using inheritance or using delegation to separate objects.
- Introduction
- Algorithm and problem representation
- Defining a common algorithmic protocol
- The framework
- Conclusion
- References
- Listing 1: Declaration of algorithmic classes
- Listing 2: Implementation of backtrack searcher class
- Listing 3: Sample main() program
- Sidebar: Algorithmic objects and design patterns
Introduction
The implementation of algorithms is central to many computer programs. However, reusing algorithms other than by example (as exemplified by the books of Knuth, Press and Sedgewick, among others) is far from trivial. The recent ANSI/ISO C++ Standard Template Library illustrates one way to capture commonly used algorithms; in this article we’ll discuss another.
To make the discussion a bit more concrete, we’ll use an example taken from my research of the past few years. The research involved the use of object-oriented techniques to help solving Operations Research problems: problems such as production scheduling, railway timetable construction, and route planning. By their very nature, most of these problems are so complex (‘NP-hard’ is the mathematical term) that there are no known methods to solve them efficiently in general. (Although sometimes efficient algorithms are known for special cases.) To solve them nevertheless, we must revert to some form of searching, i.e. trying one combination after another until we have found an allowable combination (or an optimal one, depending on the situation).
What these problems share, then, is a common approach to solving them (i.e. searching); they obviously differ in what it is that must be solved. Sounds like a clear case of object-orientation, isn’t it? In fact, it is. What we therefore did was develop a small C++ framework that captured the common elements, while leaving the problem-specific parts for our clients. We applied the framework to various searching algorithms, but the overall pattern is general enough to be applied in many other settings as well (see the sidebar Algorithmic objects and design patterns for a discussion of the patterns present in the approach).
Algorithm and problem representation
The first step towards reuse of algorithms is to separate the algorithm proper from its application to a specific problem. Basically, there are two ways to do this, shown in Figure 1.
The most straightforward way is shown in Figure 1a. Design an algorithmic class that implements the problem-independent steps of the algorithm, and have it use deferred operations (i.e. pure virtual member functions in C++ terms) for the problem-dependent parts. Leave it up to the client to derive an applied class from this base class and provide implementations for the deferred operations, in effect delegating the responsibility for the problem representation to the derived class.
This approach works, no doubt about it. It may even be preferable in some situations. It is simple and direct, while leaving room for variations. However, it wasn’t good enough for our purposes. What we needed was more flexibility. In particular, we wanted to provide variations in two dimensions, not just one: we wanted to vary both the algorithm and the problem. If you consider the delegation-through-inheritance approach, you’ll notice that it is easy to vary the problem to which the algorithm is applied, but to vary the algorithm itself isn’t quite that simple. In fact, if you want n algorithmic variations applied to m problems, you need n algorithmic base classes plus n x m applied classes! Even worse, these n x m applied classes would have no more than m basic variations, repeated n times over.
The solution isn’t hard and requires the ubiquitious computer science panacea: add a level of indirection. Take a look at Figure 1b. There we have separated the algorithm and the problem representation into two separate classes. As before, the problem-independent steps of the algorithm are fully implemented, but this time they use deferred operations from a different class rather than from their own offspring. An abstract interface class for the problem-dependent operations is also provided, and it is this class from which applied versions are derived by the client. Then, when the algorithm is executed, it uses a pointer to an applied problem representation to perform the problem-dependent operations needed for its operation.
What has this level of indirection bought us? In one word: flexibility. As before, it allows us to provide different variations of the problem representation as long as they implement the abstract interface required from them. In addition, however, we can independently vary the algorithm as well, simply by substituting one algorithmic class for another. If each algorithmic class uses the same abstract problem representation interface, no one can tell the difference (except performancewise, perhaps). For the hypothetical n algorithms and m problems we now need only n + m + 1 classes, and there’s no duplication in the problem representation effort either! But wait, there is more to come, although we need to clear up some intermediate points first.
Defining a common algorithmic protocol
As it turns out, we can further enhance the capabilities of the algorithm by more formally defining the algorithmic protocol. Until now, the protocol was only implicit in the definition of the problem representation interface, but bringing it out allows us to add some new functionality.
A discussion of the protocol needs to be more concrete than the object interactions dealt with so far. From now on, we’ll use the searching example mentioned earlier to illustrate our points, but it should be clear that the same principles can be applied to virtually any algorithm.
The searching algorithms all employ some form of tree searching (the familiar backtrack search algorithm is one example; branch and bound search is another). What these tree searching algorithms have in common, is that they traverse all possible combinations of the problem’s variables in a tree-like fashion until a solution emerges. Going from one (partial) combination to another entails generating the combinations that start with the current one; this process is known, by its analogy to trees, as ‘branching’. It is possible to reduce the operations of the tree searching algorithms to a fairly limited set, which we have depicted in the event trace of Figure 2.
As the event trace shows, the Searcher object starts off with a request for the initial branches (i.e. combinations) of the problem, then repeatedly executes an ‘enter-process-leave’ cycle. The EnterState message shown in Figure 2 signals to the problem representation that it should change its state according to the given combination (we’ll get to that in a moment); Process lets it perform problem state-specific processing, such as checking whether an optimal solution has been found yet; and LeaveState tells it to release any resources it may have allocated for that state (many implementations use sophisticated subproblem solvers as part of their processing, which may need to be released at this point).
Between the Process and the LeaveState messages, the Searcher may decide that it needs more branches, or that the time has come to store a solution. The Searcher’s decision in this respect is based on information obtained as part of the protocol and the problem processing, but it needs the cooperation of the problem representation to effectuate these decisions. Hence the GenerateBranches and CreateSolution messages that may be sent to the ProblemRep.
As to the mysterious states ‘S’ shown in the event trace, these are artifacts from the fact that we have separated the algorithm from the problem representation. As a result, the Searcher knows when to explore a particular combination in the problem, but only the ProblemRep knows how to do so. For the Searcher to stay in control, it requires the ProblemRep to wrap up sufficient information about a combinations in a state packet when branches are generated, then doles out these packets one by one as part of EnterState etc. messages when their time has come. To the Searcher, these state packets are just opaque parcels; to the ProblemRep, they are precious bits of information that represent a restorable state.
The framework
Combining the previous ingredients and adding some new ones, our design starts to resemble a true framework. The result is shown in Figure 3; Listing 1 contains the corresponding class declarations.
The left half of this figure contains the algorithmic side of the whole operation. The algorithmic base class encapsulates the searcher side of the protocol defined earlier, with one or more concrete searcher algorithms using this protocol for their implementation. Listing 2 shows an implementation of the backtrack searching algorithm as an illustration of a concrete searcher. As can be seen in that listing, the concrete searcher uses the inherited search protocol to do its job.
The use of this protocol has two interesting side effects. For one, the derived searcher class isn’t even aware of the existence of a problem representation! Surprising though this may seem, it is the result of the encapsulation of the protocol by the searcher base class. Obviously, this gives the protocol implementation even more freedom in its interaction with the problem representation.
The second side effect follows from the first one: because the actual protocol communication is hidden from derived searcher classes, we can slip in another class of objects called Monitors. As their name implies, Monitors are objects that passively observe the algorithm. We use them for example to collect performance measures for different algorithms, which allows us to select the best algorithm for the job or investigate new algorithms. Because they can rely on the standard search protocol being used, it is quite easy to implement a whole range of these monitors and reuse them for each concrete algorithm.
The right half of Figure 3 deals with the problem representation classes. Apart from the classes mentioned earlier, we have also shown a ProblemStrategy class. This illustrates an aspect of the full version of the framework, where we provide several more or less specialized problem representations, whose behavior can be modified by substituting different objects for, say, processing or branch generation rules. With an ample supply of stock strategies, this greatly reduces the effort required from our clients to implement new problem representations, or experiment with different strategies.
Space constraints do not allow us to discuss an actual problem representation here, but Listing 3 contains a sample main() program that illustrates the use of the algorithms, given a suitable problem representation.
Conclusion
This article has shown the design of a small C++ framework that allows a range of algorithms to be encapsulated as objects and applied to any number of problems. While the details were oriented towards implementations of tree searching algorithms, the overall model is generic enough to allow application to different algorithms and problem domains as well.
References
E. Gamma, R. Helm, R. Johnson, J. Vlissides: Design patterns. Elements of reusable object-oriented software, Addison-Wesley 1995.
Listing 1: Declarations of algorithmic classes
// Opaque representation of a problem state
class ProblemState { };
// Helper class; assumes standard data structures
typedef List<ProblemState *> StateList;
// Opaque representation of a problem solution
class Solution { };
// Base class for all problem representations
class ProblemRep {
public:
// Required interface for derived classes
virtual bool InitialBranches(StateList &)=0;
virtual void EnterState(ProblemState *)=0;
virtual bool Process(ProblemState *)=0;
virtual void LeaveState(ProblemState *)=0;
virtual bool GenerateBranches(ProblemState *, StateList &)=0;
virtual Solution *CreateSolution(ProblemState *)=0;
};
// Base class for all search monitors
class Monitor {
public:
virtual OnSearchEvent(int, void *)=0;
};
// Helper class; assumes standard data structures
typedef List<Monitor *> MonitorList;
// Base class for all searchers
class Searcher {
public:
Searcher();
// Interface for ordinary clients
Solution *Solve(ProblemRep *);
// Functions to add and remove search monitors
void AddMonitor(Monitor *);
void RemoveMonitor(Monitor *);
protected:
// Mirror of algorithmic interface for derived classes
bool InitialBranches(StateList &);
void EnterState(ProblemState *);
bool Process(ProblemState *);
void LeaveState(ProblemState *);
bool GenerateBranches(ProblemState *, StateList &);
void CreateSolution(ProblemState *);
// Top-level search steps implemented by derived classes
virtual bool PreProcess()=0;
virtual bool Search()=0;
virtual void PostProcess()=0;
private:
// Current problem representation
ProblemRep *_rep;
// List of search monitors
MonitorList _monitors;
// Stored solution, if any
Solution *_sol;
};
// Sample search algorithm implementation
class Backtrack: public Searcher {
public:
Backtrack();
protected:
// Implementation of searching steps
virtual bool PreProcess() { return true; }
virtual bool Search();
virtual void PostProcess() {}
private:
// Recursive forward step
bool StepForward(StateList &);
};
Listing 2: Implementation of backtrack searcher class
// Top-level searching algorithm
bool Backtrack::Search()
{
StateList l;
// Create initial branch set
if (InitialBranches(l))
// Use recursive implementation to find solution
return StepForward(l);
else
return false;
}
// Recursive forward step in backtrack search
bool Backtrack::StepForward(StateList &l)
{
// Iterate over all states in the list
for (Iter<ProblemState *> i=l.begin(); i !=l.end(); ++i) {
EnterState(*i); // Activate the state
if (Process(*i)) {
// OK, try to extend the state
StateList l2;
if (GenerateBranches(*i, l2)) {
// New branches; see if we can step forward
if (StepForward(l2)) return true;
} else {
// No branches; must be solution
CreateSolution(*i);
return true; // Unwind with success
}
}
LeaveState(*i); // Deactivate the state
}
// If we get here, there were no solutions. Unwind.
return false;
}
Listing 3: Sample main() program
// Assume the existence of a ProblemRep implementation
void main()
{
// Instance of the problem representation
MyProblemRep problem;
// Solve the problem with backtrack search
Solution *sol=Backtrack().Solve(&problem);
}
Sidebar: Algorithmic objects and design patterns
One of the books on object-oriented design I enjoyed reading most last year, was Gamma et al.'s Design patterns. Although it is 'only' a catalog of existing design techniques, the mere fact of them being brought together in a single book, combined with their insightful descriptions are probably more valuable for learning about good object-oriented design than anything except several years of hard-won experience (and even then you're likely to miss at least some of the patterns of the book, let alone the masterly overview).
So what patterns do we find in the algorithmic objects approach? Quite a few, actually. It's not so much that the objects were designed with Design patterns in hand (the architecture was conceived in 1991 and hasn't changed much since 1993, by which time only a few conference papers on design patterns had appeared, but not the book); rather, they were arrived at after trying several approaches and sticking with the ones that worked best. Which is what Design patterns is all about, of course.
The basic algorithm/problem rep division is found in the Template Method pattern. In this pattern, overall behavior is determined by one class (the Application class in Gamma et al., the Algorithm base class in our example) that delegates part of its implementation to its derived classes (the concrete algorithms). Other parts of the required behavior are delegated to a second class hierarchy (the Document class in the book, the ProblemRep in our example), which allows for further variations in behavior.
In the tree searching example, we have another class: the ProblemState. This is at once an extension of the Template Method pattern (ProblemStates are used by the Searcher instead of the actual ProblemRep in some cases), as well as an example of the Memento pattern, where it serves to encapsulate the state of the ProblemRep (acting as the Originator in that case) for later restoration. Incidentally, the ProblemRep/Problem-State pair is itself an instance of the Factory Method pattern.
The way that Monitors keep track of the progress of the algorithm illustrates the use of the Observer pattern, with the Algorithm base class acting as the Subject, and each Monitor as an Observer, although in the interest of efficiency, we provide a partial algorithmic state rightaway to the Monitors, without going through the GetState() protocol that Design patterns describes.
The replaceable variable selection and constraint propagation objects that are used by specific ProblemReps show the Strategy pattern in action. Finally, we have used several instances of the Iterator pattern throughout the example.
Copyright © 2024 David Adams. All rights reserved. Page last modified on 2024-05-23 08:49
