Crate matchmaker

This library can be used to fairly match students to categories (or activities). Or students to schools. Or anything to anything else.

Background

The matching problem this library solves is mathematically know as the residence problem and is a subset of the stable marriage problem. There are sereval known algorithms that solve this problem, each with there own pros and cons. For more information about the subject see also Matching algorithms for the secondary school admission problem in Amsterdam.

Algorithm

At this time this library only implements the Deferred Acceptance - Single Tie Break algorithm. The library has been designed to make the implementation of other algorithms possible (it just needs to be done ;).

Usage

Default matching

Students are distributed over multiple categories, but each student can only be placed once.

use matchmaker::da_stb::match_students;
use matchmaker::{Category, Student};
use rand::thread_rng;
use std::collections::VecDeque;

// Create categories
let cooking = Category::new("Cooking", 10);
let reading = Category::new("Reading", 10);
let walking = Category::new("Walking", 5);

// Create student Bert
// Bert wishes to be placed in category cooking or reading (in that order)
let bert = Student::new(
    "Bert",
    VecDeque::from(vec![cooking.clone(), reading.clone()]),
    Vec::new(),
);

// Create student Suze
// Suze wishes to be placed in category cooking or reading (in that order),
// but does not wish to be placed in category walking
let suze = Student::new(
    "Suze",
    VecDeque::from(vec![reading.clone(), cooking.clone()]),
    Vec::from([walking.clone()]),
);

let mut rng = thread_rng();
let categories = Vec::from([cooking, reading, walking]);

let match_result = match_students(Vec::from([bert, suze]), &categories, &mut rng);

println!("Students matched to categories:");
println!();
for category in &categories {
    println!("{}:", &category.name);
    for student in match_result
        .placed
        .get(&category.name)
        .unwrap_or(&Vec::new())
    {
        println!(" - {}", &student.name);
    }
}

if match_result.not_placable.is_empty() {
    println!();
    println!("All students could be placed.");
}

This should the following result:

Students matched to categories:

Cooking:
 - Bert
Reading:
 - Suze
Walking:

All students could be placed.

Place students in multiple categories

Students are distributed over multiple categories. A single student can be placed in more than one category.

Example

use matchmaker::{Category, Student};
use matchmaker::da_stb::match_students_to_multiple_categories;
use rand::thread_rng;
use std::collections::VecDeque;

// Create categories
let cooking = Category::new("Cooking", 10);
let reading = Category::new("Reading", 10);
let walking = Category::new("Walking", 5);

// Create student Bert
// Bert wishes to be placed in category cooking or reading (in that order)
let bert = Student::new(
    "Bert",
    VecDeque::from(vec![cooking.clone(), reading.clone()]),
    Vec::new(),
);

// Create student Suze
// Suze wishes to be placed in category cooking or reading (in that order),
// but does not wish to be placed in category walking
let suze = Student::new(
    "Suze",
    VecDeque::from(vec![cooking.clone(), reading.clone()]),
    Vec::from([walking.clone()]),
);

let mut rng = thread_rng();
let categories = Vec::from([cooking, reading, walking]);

let match_result = match_students_to_multiple_categories(
    Vec::from([bert, suze]),
    &categories,
    &mut rng);

println!("Students matched to categories:");
println!();
for category in &categories {
    println!("{}:", &category.name);
    for student in match_result
        .placed
        .get(&category.name)
        .unwrap_or(&Vec::new())
    {
        println!(" - {}", &student.name);
    }
}

if match_result.not_placable.is_empty() {
    println!();
    println!("All students could be placed.");
}

This should the following result:

Students matched to categories:

Cooking:
 - Suze
 - Bert
Reading:
 - Bert
 - Suze
Walking:
 - Bert

All students could be placed.

Modules

da_stb

Implements the Deferred Acceptance - Single Tie Break algorithm

Structs

Category	Holds a category
MatchResult	Holds the result of a match
Student	Holds a student