DESIGNING GENERIC ALGORITHMS FOR OPERATIONS RESEARCH Test Package

The research report discusses various problems encountered when designing reusable, extensible, algorithms for operations research. It explains how to use object-oriented concepts and the notion of genericity to design algorithms that are independent of the data structures and the algorithms they handle, but that can still interact deeply together. The main goal is to explain how to design algorithms that are both generic and efficient. The solutions discussed in this report have been implemented in the C++ language, and a test package is proposed to allow efficiency comparisons between the different designs.

The package is decomposed in several files, corresponding to the discussion in the report. It implements three graph structures and most of the tests are performed using a shortest path algorithm.

• common.hpp
  Contains the common elements of the package.

• data.hpp
  Defines data to be carried by the graph structures.

• iterator.hpp
  Defines iterators on the graph structures.

• graph.hpp - graph.cpp
  Defines a non-template generic graph structure.

• tgraph.hpp
  Defines a template graph structure.

• extension.hpp
  Defines an extension mechanism for data structures.

• extend_tgraph.hpp
  Defines an extendable template graph structure.

• visitor.hpp
  Defines visitors for the shortest path algorithm.

• shortest_path.hpp
  Defines the shortest path algorithm for the various extension approaches.

• test.cpp
  Contains the test procedure of the various concepts presented in the report.

The first test series compares the efficiency of the inheritance and the generic approaches to design a graph structure. The impact of using iterators is also measured.

• Test (1): Tests the speed to access the getFlow() method of the arc data in the non-template graph structure. The necessary downcast is performed through a dynamic cast.

• Test (2): Tests the speed to access the getFlow() method of the arc data in the non-template graph structure. The necessary downcast is performed through a static cast.

• Test (3): Tests the speed to access the getFlow() method of the arc data in the template graph structure.

• Test (4): Tests the speed to access the getFlow() method of the arc data in the template graph structure using iterators.

The second test series compares the efficiency of the virtual method, the abstract visitor and the visitor interface approaches to extend an algorithm. The shortest path algorithm is extended to compute either a shortest distance path, or a shortest time path.

• Test (a): Tests the speed of the shortest path algorithm with the virtual method approach.

• Test (b): Tests the speed of the shortest path algorithm with the abstract visitor approach.

• Test (c): Tests the speed of the shortest path algorithm with the visitor interface approach.

• Test (d): Tests the speed of the shortest path algorithm with the classical approach (i.e. two separate algorithms).

The third test series measures the impact on efficiency of the extension mechanism proposed in the report to allow algorithms to extend data structures without breaking their encapsulation. Tests (3), (4) and (a) to (d) are performed again, in order to measure the impact of the extension mechanism when it is available but not really used. Then tests using the extension mechanism are performed.

• Test (e): Tests the speed of the shortest path algorithm with the visitor interface approach and the extension mechanism (using dynamic cast to access extensions).

• Test (f): Tests the speed of the shortest path algorithm with the visitor interface approach and the extension mechanism (using static cast to access extensions).

Here are the results (in seconds) obtained by an Athlon XP 1800+ processor, with a GCC 3.2 compiler under a Cygwin environment, and the -O2 option activated.

You can download the of the package and make your own tests. We only checked it on GCC compilers, but it should work on any other one, with only few minor changes (as the way to measure time).