Structure: Algorithms

Introduction

The following assumes that the reader has some familiarity with the basic concepts of matching algorithms. Note: We exclude SPA-P in our discussion here as it falls outside of my (Whitehead) level four project, involves an IP model rather than a polynomial-time algorithm, and exists for the purpose of experimentation.

Basic Structure

Each problem is defined in a file named <problem acronym lowercase>Abstract.py. Its responsibility is the setup of the problem so it uses a reader to take in the preferences on initialisation and defines the goal of the algorithm by providing methods for stability checking. The reading of the preferences is delegated to <problem acronym lowercase>PreferenceInstance.py. This further delegates parsing the dictionary or file to dictionaryReader or fileReader respectively. The preference instance class also checks that the given preference form a valid instance and cleans any unacceptable pairs, i.e. one agent's list contains the other but not vice versa. From here we simply implement each algorithm for the problem class in its own file. These are then exposed through the interface files <full name of problem class>.py in src/algmatch, which takes the algorithm orientation and, if relevant, stability type (i.e. super, strong) and calls the correct algorithm.

Abstract Classes for Readers

We currently only have three abstract classes. The AbstractReader is an interface for all our reader classes, dictionary or file. AbstractPreferenceInstance is built around the template method _general_setup_procedure for preference instances. Both it and AbstractPreferenceInstanceWithTies provide a few utilities for the three steps:

1. Checking the validity of each preference list,
2. Cleaning unacceptable pairs as mentioned above,
3. Setting up the ranking dictionary. The ranking dictionary for each agent maps the agents in their preference list to an integer. More preferrable agents have lower values and agents between which the agent is indifferent have the same value. This makes comparison of two agents simpler and easier.

Errors

We have a suite of custom errors for possible issues encountered during:

1. the parsing of file or dictionaries, in ReaderErrors.py,
2. the checking of lists in the preference instance class, in InstanceSetupErrors.py. The goal of these is to provide an informative message to the user, so that they can more easily find and correct the bug in their instance.