I've written an implementation of Gale-Shapley in Rust as an exercise (I haven't written rust in a while, and I wanted to give myself a refresher). I modeled it so that Proposers send a proposal object to Acceptors (wrapped in a Rc+RefCell), so the Acceptor can change the proposal state.
Is this a reasonable approach? I had another idea using channels (proposers send a Proposal that contains the send end of a channel), but I wasn't sure if that made sense given it's completely single threaded.
I also thought about some way of passing a reference to the proposer directly and getting rid of the proposal object, but I wasn't sure if there was a clean way to do that from a method within Proposer (and even if I did, I wasn't sure if there was a way to pass a reference that would allow the Accepter to update the proposer's state).
Thank you for any help and feedback.
Edit: Another idea I had was changing the submit_next_proposal function return proposal objects to the caller (rather than directly adding it to the acceptor's list), and then the caller is responsible for moving data between the proposers and the acceptors rather than letting the two 'talk' to each other.
// entities.rs
use std::rc::{Rc};
use std::cell::RefCell;
use std::collections::HashMap;
#[derive(PartialEq, Debug)]
pub enum ProposalState {
Accepted,
Rejected
}
#[derive(Debug, PartialEq)]
pub struct Proposer {
pub name: String,
pub preferences: Vec<String>,
pub proposal: Option<Rc<RefCell<Proposal>>>,
next_offer: usize
}
#[derive(Debug, PartialEq)]
pub struct Acceptor {
pub name: String,
pub preferences: HashMap<String, usize>,
pub proposals: Vec<Rc<RefCell<Proposal>>>,
pub active_proposal: Option<Rc<RefCell<Proposal>>>,
active_proposal_priority: Option<usize>
}
#[derive(Debug, PartialEq)]
pub struct Proposal {
pub sender: String,
pub proposal_state: ProposalState
}
impl Proposer {
pub fn new(name: &str, preferences: &[&str]) -> Proposer {
Proposer {
name: String::from(name),
preferences: preferences.iter().map(|s| s.to_string()).collect(),
proposal: None,
next_offer: 0
}
}
pub fn submit_next_proposal(&mut self, acceptors: &mut HashMap<String, Acceptor>) {
let next_pref_name = &self.preferences[self.next_offer];
self.next_offer += 1;
let chosen_acceptor = acceptors.get_mut(next_pref_name.as_str()).unwrap();
let proposal = Rc::new(
RefCell::new(Proposal { sender: self.name.clone(), proposal_state: ProposalState::Rejected }));
chosen_acceptor.submit_proposal(proposal.clone());
self.proposal = Some(proposal);
println!("Proposer {} has proposed to {}", self.name, chosen_acceptor.name);
}
pub fn is_paired(&self) -> bool {
let Some(proposal) = &self.proposal else { return false; };
proposal.borrow().proposal_state == ProposalState::Accepted
}
pub fn paired_party(&self) -> Option<String> {
if !self.is_paired() { return None };
Some(self.preferences[self.next_offer - 1].clone())
}
}
impl Acceptor {
pub fn new(name: &str, preferences: &[&str]) -> Acceptor {
// build a preference hashmap for easier lookups
let mut preference_map: HashMap<String, usize> = HashMap::new();
for (preference, name) in preferences.iter().enumerate() {
preference_map.insert(String::from(*name), preference);
}
Acceptor {
name: name.to_string(),
preferences: preference_map,
proposals: vec![],
active_proposal: None,
active_proposal_priority: None
}
}
pub fn submit_proposal(&mut self, proposal: Rc<RefCell<Proposal>>) {
self.proposals.push(proposal);
}
pub fn process_current_proposals(&mut self) {
// iterate through the proposals, determine the highest preference one.
for proposal in &self.proposals {
if let Some(active_proposal) = self.active_proposal.as_ref() {
// check if the offer is better than the current one.
let existing_priority = self.active_proposal_priority.expect("Active proposal priority should never be empty if active proposal is set.");
// grab a mutable handle to the new offer so we can change its state
let mut new_proposal = proposal.borrow_mut();
let new_proposal_priority = self.preferences[&new_proposal.sender];
if new_proposal_priority >= existing_priority {
// we are fine with the current offer. do not update any values, and simply reject
// the active proposal.
new_proposal.proposal_state = ProposalState::Rejected;
}
else {
// this offer is better than the current one. Reject the current offer, and accept
// the new one.
{
// get a mutable handle to the OLD active proposal
let mut active_proposal = active_proposal.borrow_mut();
active_proposal.proposal_state = ProposalState::Rejected;
}
self.active_proposal = Some(proposal.clone());
new_proposal.proposal_state = ProposalState::Accepted;
self.active_proposal_priority = Some(new_proposal_priority);
}
}
else {
// accept the new proposal because we have no better offer
self.active_proposal = Some(proposal.clone()); // record it and increase the reference count
// get a mutable ref so we can change the proposals state.
let mut proposal = proposal.borrow_mut();
proposal.proposal_state = ProposalState::Accepted;
self.active_proposal_priority = Some(self.preferences[&proposal.sender]);
}
}
self.proposals.clear();
if let Some(proposal) = &self.active_proposal {
println!("Acceptor {} has accepted a proposal from {}", self.name, proposal.borrow().sender);
}
}
}
// lib.rs
use std::collections::HashMap;
pub use crate::entities::{Acceptor, Proposer};
mod entities;
#[derive(PartialEq)]
enum GaleShapleyState {
Incomplete,
Complete
}
pub fn run_gale_shapley(acceptors: &mut HashMap<String, Acceptor>, proposers: &mut HashMap<String, Proposer>) {
loop {
let state = gale_shapely_round(acceptors, proposers);
if state == GaleShapleyState::Complete {break}
}
}
fn gale_shapely_round(acceptors: &mut HashMap<String, Acceptor>, proposers: &mut HashMap<String, Proposer>) -> GaleShapleyState {
for proposer in proposers.values_mut() {
if !proposer.is_paired() { proposer.submit_next_proposal(acceptors) };
}
for acceptor in acceptors.values_mut() {
acceptor.process_current_proposals();
}
for proposer in proposers.values() {
if !proposer.is_paired() { return GaleShapleyState::Incomplete };
}
GaleShapleyState::Complete
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn verify_basic_function() {
let mut acceptors = HashMap::from([
(String::from("acceptor_1"), Acceptor::new("acceptor_1", &["proposer_1", "proposer_2", "proposer_3", "proposer_4"])),
(String::from("acceptor_2"), Acceptor::new("acceptor_2", &["proposer_3", "proposer_4", "proposer_1", "proposer_2"])),
(String::from("acceptor_3"), Acceptor::new("acceptor_3", &["proposer_4", "proposer_2", "proposer_3", "proposer_1"])),
(String::from("acceptor_4"), Acceptor::new("acceptor_4", &["proposer_3", "proposer_2", "proposer_1", "proposer_4"]))
]);
let mut proposers = HashMap::from([
(String::from("proposer_1"), Proposer::new("proposer_1", &["acceptor_2", "acceptor_1", "acceptor_3", "acceptor_4"])),
(String::from("proposer_2"), Proposer::new("proposer_2", &["acceptor_4", "acceptor_1", "acceptor_2", "acceptor_3"])),
(String::from("proposer_3"), Proposer::new("proposer_3", &["acceptor_1", "acceptor_3", "acceptor_2", "acceptor_4"])),
(String::from("proposer_4"), Proposer::new("proposer_4", &["acceptor_2", "acceptor_2", "acceptor_1", "acceptor_4"]))
]);
run_gale_shapley(&mut acceptors, &mut proposers);
assert_eq!(proposers["proposer_1"].paired_party().unwrap(), "acceptor_1");
assert_eq!(proposers["proposer_3"].paired_party().unwrap(), "acceptor_3");
assert_eq!(proposers["proposer_2"].paired_party().unwrap(), "acceptor_4");
assert_eq!(proposers["proposer_4"].paired_party().unwrap(), "acceptor_2");
}
}