Verification

Introduction

We make use of the instance generation to produce a number of random instances, the solution enumeration utilities to generate all the stable solutions for each instance, and then test the correctness of the algorithms' results against this set of solutions.

Verification

These form the basis for all our testing of bipartite problems. Our testing for SR is separate due to its fundamentally different nature but analogous.

1. AbstractVerifier is a template class, describing the above process in general. It has the abstract methods run and show_results.
2. For each problem, <problem name>Verifier has the single responsibility of bringing together the correct utilities and filling in the template.
3. The responsibility for implementing run, which tracks hits and misses for a single process, falls to AbstractVerifier children:
   1. AbstractSingleVeriifer, which works for exactly one process, and
   2. AbstractMultiVeriifer, which uses the multiprocessing module to allow the process to update a shared dictionary.
4. In order to get the complete set of verifiers, we create <problem name>SingleVerifier and <problem name>MultiVerifier using dual inheritance with:
   1. either AbstractSingleVeriifer or AbstractMultiVeriifer respectively and,
   2. <problem name>Verifier

The responsibility for implementing show_results is part of (4) since it depends both on the manner of execution (whether there is a shared dictionary object) and on the problem class. We include in files of type (4) a main function which can be manually configured to test that individual algorithm, to aid with debugging. We therefore also try various tie densities in the cases with indifference, since some bugs are more easily found in cases with very few ties and some in cases with very many ties.