From 0fc9ad3f2f70549d290ab77d2836d6d4ce3e20cb Mon Sep 17 00:00:00 2001 From: Jeff Hemminger Date: Fri, 19 Dec 2025 13:48:25 +0900 Subject: [PATCH] added bipartite --- .gitignore | 1 + Cargo.lock | 85 ++++ Cargo.toml | 3 + .../earliest_completion.rs | 35 +- src/algorithms/interview_scheduling/mod.rs | 2 + .../weighted_interval_scheduling.rs | 445 ++++++++++++++++++ src/algorithms/stable_matching/bipartite.rs | 308 ++++++++++++ .../stable_matching/gale_shapley.rs | 165 +------ src/algorithms/stable_matching/mod.rs | 5 +- src/algorithms/stable_matching/types.rs | 165 +++++++ src/main.rs | 12 - 11 files changed, 1048 insertions(+), 178 deletions(-) create mode 100644 src/algorithms/interview_scheduling/weighted_interval_scheduling.rs create mode 100644 src/algorithms/stable_matching/bipartite.rs create mode 100644 src/algorithms/stable_matching/types.rs delete mode 100644 src/main.rs diff --git a/.gitignore b/.gitignore index ea8c4bf..2a0038a 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,2 @@ /target +.idea \ No newline at end of file diff --git a/Cargo.lock b/Cargo.lock index fb81a63..6ecfbb6 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -6,7 +6,10 @@ version = 4 name = "algorithms" version = "0.1.0" dependencies = [ + "csv", "rand", + "serde", + "serde_json", ] [[package]] @@ -15,6 +18,27 @@ version = "1.0.3" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "2fd1289c04a9ea8cb22300a459a72a385d7c73d3259e2ed7dcb2af674838cfa9" +[[package]] +name = "csv" +version = "1.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "acdc4883a9c96732e4733212c01447ebd805833b7275a73ca3ee080fd77afdaf" +dependencies = [ + "csv-core", + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "csv-core" +version = "0.1.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7d02f3b0da4c6504f86e9cd789d8dbafab48c2321be74e9987593de5a894d93d" +dependencies = [ + "memchr", +] + [[package]] name = "getrandom" version = "0.2.16" @@ -26,12 +50,24 @@ dependencies = [ "wasi", ] +[[package]] +name = "itoa" +version = "1.0.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4a5f13b858c8d314ee3e8f639011f7ccefe71f97f96e50151fb991f267928e2c" + [[package]] name = "libc" version = "0.2.175" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "6a82ae493e598baaea5209805c49bbf2ea7de956d50d7da0da1164f9c6d28543" +[[package]] +name = "memchr" +version = "2.7.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "32a282da65faaf38286cf3be983213fcf1d2e2a58700e808f83f4ea9a4804bc0" + [[package]] name = "ppv-lite86" version = "0.2.21" @@ -89,6 +125,55 @@ dependencies = [ "getrandom", ] +[[package]] +name = "ryu" +version = "1.0.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "28d3b2b1366ec20994f1fd18c3c594f05c5dd4bc44d8bb0c1c632c8d6829481f" + +[[package]] +name = "serde" +version = "1.0.225" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fd6c24dee235d0da097043389623fb913daddf92c76e9f5a1db88607a0bcbd1d" +dependencies = [ + "serde_core", + "serde_derive", +] + +[[package]] +name = "serde_core" +version = "1.0.225" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "659356f9a0cb1e529b24c01e43ad2bdf520ec4ceaf83047b83ddcc2251f96383" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.225" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0ea936adf78b1f766949a4977b91d2f5595825bd6ec079aa9543ad2685fc4516" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.145" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "402a6f66d8c709116cf22f558eab210f5a50187f702eb4d7e5ef38d9a7f1c79c" +dependencies = [ + "itoa", + "memchr", + "ryu", + "serde", + "serde_core", +] + [[package]] name = "syn" version = "2.0.106" diff --git a/Cargo.toml b/Cargo.toml index 7ca51a7..701c04e 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -5,6 +5,9 @@ edition = "2024" [dependencies] rand = "0.8" +csv = "1.3" +serde = { version = "1.0", features = ["derive"] } +serde_json = "1.0" [lib] doctest = false diff --git a/src/algorithms/interview_scheduling/earliest_completion.rs b/src/algorithms/interview_scheduling/earliest_completion.rs index 3ecda6a..5397386 100644 --- a/src/algorithms/interview_scheduling/earliest_completion.rs +++ b/src/algorithms/interview_scheduling/earliest_completion.rs @@ -32,8 +32,41 @@ where // This is a placeholder self.end.0 } -} + /// Sort interviews by end time (earliest completion first) + /// This is the optimal greedy algorithm for interval scheduling + pub fn sort_by_earliest_completion(interviews: &mut [Interview]) { + interviews.sort_by(|a, b| a.end.cmp(&b.end)); + } +} + +/// Optimal interval scheduling using earliest completion time +/// Returns maximum set of non-overlapping interviews +pub fn schedule_interviews_optimal(mut interviews: Vec>) -> Vec> +where + T: Ord + Copy, +{ + if interviews.is_empty() { + return vec![]; + } + + // Step 1: Sort by earliest completion time + Interview::sort_by_earliest_completion(&mut interviews); + + // Step 2: Greedily select non-overlapping intervals + let mut selected = vec![interviews[0].clone()]; + + for interview in interviews.into_iter().skip(1) { + let last_selected = selected.last().unwrap(); + + // If this interview starts after the last one ends, select it + if interview.start >= last_selected.end { + selected.push(interview); + } + } + + selected +} #[cfg(test)] mod tests { diff --git a/src/algorithms/interview_scheduling/mod.rs b/src/algorithms/interview_scheduling/mod.rs index 0016163..4dd6544 100644 --- a/src/algorithms/interview_scheduling/mod.rs +++ b/src/algorithms/interview_scheduling/mod.rs @@ -1,6 +1,8 @@ pub mod earliest_completion; +pub mod weighted_interval_scheduling; pub mod test_data; pub use earliest_completion::*; +pub use weighted_interval_scheduling::*; pub use test_data::*; diff --git a/src/algorithms/interview_scheduling/weighted_interval_scheduling.rs b/src/algorithms/interview_scheduling/weighted_interval_scheduling.rs new file mode 100644 index 0000000..de1d84b --- /dev/null +++ b/src/algorithms/interview_scheduling/weighted_interval_scheduling.rs @@ -0,0 +1,445 @@ + +//! Weighted Interval Scheduling Algorithm using Dynamic Programming +//! +//! This implementation follows the approach described in Algorithm Design by Kleinberg & Tardos +//! The algorithm finds the maximum weight subset of non-overlapping intervals. + +use std::cmp; + +/// Represents a job/interval with start time, finish time, and weight/value +#[derive(Debug, Clone)] +pub struct Job { + pub start: i32, + pub finish: i32, + pub weight: i32, + pub id: usize, // For tracking original job indices +} + +impl Job { + /// Creates a new job with the given parameters + pub fn new(start: i32, finish: i32, weight: i32, id: usize) -> Self { + Job { start, finish, weight, id } + } +} + +/// Weighted Interval Scheduling solver using Dynamic Programming +pub struct WeightedScheduler { + jobs: Vec, + dp: Vec, // DP table: dp[i] = maximum weight using first i jobs + n: usize, // Cache the length + predecessors: Vec>, // predecessors[i] = latest compatible job index for job i +} + +impl WeightedScheduler { + + /// Gets the DP value for the predecessor of a jobs + fn predecessor_value(&self, job_idx: usize) -> i32 { + self.predecessors[job_idx] + .map_or(0, |pred| self.dp[pred + 1]) + } + + /// Creates a new scheduler with the given jobs + pub fn new(mut jobs: Vec) -> Self { + // Sort jobs by finish time (crucial for the DP algorithm) + jobs.sort_by(|a, b| a.finish.cmp(&b.finish)); + + let n = jobs.len(); + let dp = vec![0; n + 1]; // dp[0] = 0 (base case: no jobs) + let predecessors = vec![None; n]; // Will be computed later + + WeightedScheduler { + jobs, + dp, + n, + predecessors, + } + } + + /// Computes the predecessor function p(j) for all jobs + /// p(j) = largest index i < j such that job i is compatible with job j + /// (i.e., jobs[i].finish <= jobs[j].start) + fn compute_predecessors(&mut self) { + + for j in 0..self.n { + // Find the latest job that finishes before job j starts + // Using binary search for O(log n) performance per job + self.predecessors[j] = self.find_latest_compatible(j); + } + } + + /// Binary search to find the latest compatible job for job at index j + fn find_latest_compatible(&self, j: usize) -> Option { + let target_start = self.jobs[j].start; + let mut left = 0i32; + let mut right = (j as i32) - 1; + let mut result = None; + + while left <= right { + let mid = left + (right - left) / 2; + + if self.jobs[mid as usize].finish <= target_start { + result = Some(mid as usize); // Changed: Some(mid as usize) instead of mid + left = mid + 1; + } else { + right = mid - 1; + } + } + + result + } + + /// Main dynamic programming algorithm to find maximum weight + /// Returns the maximum total weight achievable + pub fn find_max_weight(&mut self) -> i32 { + if self.n == 0 { + return 0; + } + + // Step 1: Compute predecessors for all jobs + self.compute_predecessors(); + + // Step 2: Fill DP table using the recurrence relation: + // dp[i] = max(dp[i-1], weight[i-1] + dp[p(i-1)+1]) + // where p(i-1) is the predecessor of job i-1 + + for i in 1..=self.n { + let job_idx = i - 1; // Job index (0-based) + let current_weight = self.jobs[job_idx].weight; + + // Option 1: Don't include current job + let exclude = self.dp[i - 1]; + + // Option 2: Include current job + let include = current_weight + self.predecessor_value(job_idx); + + // Take the maximum of the two options + self.dp[i] = cmp::max(exclude, include); + } + + self.dp[self.n] + } + + /// Reconstructs the actual optimal solution (which jobs to select) + /// Returns a vector of job indices in the optimal solution + pub fn find_optimal_jobs(&self) -> Vec { + if self.n == 0 { + return Vec::new(); + } + + let mut solution = Vec::new(); + let mut i = self.n; + + // Backtrack through the DP table to find which jobs were selected + while i > 0 { + let job_idx = i - 1; + let current_weight = self.jobs[job_idx].weight; + + // Check if job i was included in the optimal solution + let include_value = current_weight + self.predecessor_value(job_idx); + + if include_value > self.dp[i - 1] { + // Job i was included + solution.push(self.jobs[job_idx].id); + + // Move to the predecessor + match self.predecessors[job_idx] { + Some(pred) => i = pred + 1, + None => break, + } + + } else { + // Job i was not included + i -= 1; + } + } + + // Reverse to get jobs in chronological order + solution.reverse(); + solution + } + + /// Solves the weighted interval scheduling problem + /// Returns (maximum_weight, selected_job_ids) + pub fn solve(&mut self) -> (i32, Vec) { + let max_weight = self.find_max_weight(); + let selected_jobs = self.find_optimal_jobs(); + (max_weight, selected_jobs) + } + + /// Pretty prints the solution + pub fn print_solution(&self, max_weight: i32, selected_jobs: &[usize]) { + println!("\n=== Weighted Interval Scheduling Solution ==="); + println!("Maximum total weight: {}", max_weight); + println!("Selected jobs:"); + + for &job_id in selected_jobs { + // Find the job with this ID + if let Some(job) = self.jobs.iter().find(|j| j.id == job_id) { + println!(" Job {}: [{}→{}, weight={}]", + job.id, job.start, job.finish, job.weight); + } + } + + println!("\nAll jobs (sorted by finish time):"); + for (_i, job) in self.jobs.iter().enumerate() { + let selected = selected_jobs.contains(&job.id); + let marker = if selected { "✓" } else { " " }; + println!(" {} Job {}: [{}→{}, weight={}]", + marker, job.id, job.start, job.finish, job.weight); + } + } +} + +/// Example and test function +fn main() { + println!("Weighted Interval Scheduling with Dynamic Programming\n"); + + // Example 1: Basic test case + println!("=== Example 1: Basic Case ==="); + let jobs1 = vec![ + Job::new(1, 4, 3, 1), + Job::new(2, 6, 5, 2), + Job::new(4, 7, 2, 3), + Job::new(6, 8, 4, 4), + ]; + + let mut scheduler1 = WeightedScheduler::new(jobs1); + let (max_weight1, solution1) = scheduler1.solve(); + scheduler1.print_solution(max_weight1, &solution1); + + // Example 2: Case where greedy by weight fails + println!("\n\n=== Example 2: Greedy by Weight Fails ==="); + let jobs2 = vec![ + Job::new(0, 10, 10, 1), // Long, high-weight job + Job::new(1, 2, 3, 2), // Short jobs that together + Job::new(3, 4, 3, 3), // are better than the + Job::new(5, 6, 3, 4), // single long job + Job::new(7, 8, 3, 5), + ]; + + let mut scheduler2 = WeightedScheduler::new(jobs2); + let (max_weight2, solution2) = scheduler2.solve(); + scheduler2.print_solution(max_weight2, &solution2); + + // Example 3: Textbook example (if we can infer from description) + println!("\n\n=== Example 3: Larger Test Case ==="); + let jobs3 = vec![ + Job::new(0, 6, 8, 1), + Job::new(1, 4, 2, 2), + Job::new(3, 5, 4, 3), + Job::new(3, 8, 7, 4), + Job::new(4, 7, 1, 5), + Job::new(5, 9, 3, 6), + Job::new(6, 10, 2, 7), + Job::new(8, 11, 4, 8), + ]; + + let mut scheduler3 = WeightedScheduler::new(jobs3); + let (max_weight3, solution3) = scheduler3.solve(); + scheduler3.print_solution(max_weight3, &solution3); +} + +#[cfg(test)] +mod tests { + use super::*; + + // Base test utilities - functional approach with immutable data + fn create_jobs_basic() -> Vec { + vec![ + Job::new(1, 4, 3, 1), + Job::new(2, 6, 5, 2), + Job::new(4, 7, 2, 3), + Job::new(6, 8, 4, 4), + ] + } + + fn create_jobs_greedy_fails() -> Vec { + vec![ + Job::new(0, 10, 10, 1), // Long, high-weight job + Job::new(1, 2, 3, 2), // Short jobs that together + Job::new(3, 4, 3, 3), // are better than the + Job::new(5, 6, 3, 4), // single long job + Job::new(7, 8, 3, 5), + ] + } + + fn create_jobs_large_case() -> Vec { + vec![ + Job::new(0, 6, 8, 1), + Job::new(1, 4, 2, 2), + Job::new(3, 5, 4, 3), + Job::new(3, 8, 7, 4), + Job::new(4, 7, 1, 5), + Job::new(5, 9, 3, 6), + Job::new(6, 10, 2, 7), + Job::new(8, 11, 4, 8), + ] + } + + // Pure function to verify solution validity + fn is_valid_solution(jobs: &[Job], solution: &[usize]) -> bool { + solution.windows(2).all(|pair| { + let job1 = &jobs[pair[0]]; + let job2 = &jobs[pair[1]]; + job1.finish <= job2.start + }) + } + + // Pure function to calculate total weight + fn calculate_total_weight(jobs: &[Job], solution: &[usize]) -> i32 { + solution.iter() + .map(|&idx| jobs[idx].weight) + .map(|w| i32::try_from(w).expect("Weight overflow")) + .sum() + } + + // Example 1: Basic test case + #[test] + fn test_basic_case_example() { + let jobs = create_jobs_basic(); + let mut scheduler = WeightedScheduler::new(jobs.clone()); + let (max_weight, solution) = scheduler.solve(); + + // Verify solution is valid + assert!(is_valid_solution(&jobs, &solution)); + + // Verify calculated weight matches + assert_eq!(max_weight, calculate_total_weight(&jobs, &solution)); + + // For this specific case, optimal weight should be 9 + // (jobs with weights 5 and 4, indices 1 and 3) + assert_eq!(max_weight, 9); + } + + // Example 2: Case where greedy by weight fails + #[test] + fn test_greedy_by_weight_fails() { + let jobs = create_jobs_greedy_fails(); + let mut scheduler = WeightedScheduler::new(jobs.clone()); + let (max_weight, solution) = scheduler.solve(); + + // Verify solution validity + assert!(is_valid_solution(&jobs, &solution)); + assert_eq!(max_weight, calculate_total_weight(&jobs, &solution)); + + // The optimal solution should choose the four short jobs (weight 12) + // rather than the single long job (weight 10) + assert_eq!(max_weight, 12); + assert_eq!(solution.len(), 4); + } + + // Example 3: Larger test case + #[test] + fn test_larger_case_example() { + let jobs = create_jobs_large_case(); + let mut scheduler = WeightedScheduler::new(jobs.clone()); + let (max_weight, solution) = scheduler.solve(); + + // Verify solution validity + assert!(is_valid_solution(&jobs, &solution)); + assert_eq!(max_weight, calculate_total_weight(&jobs, &solution)); + + // For this case, we just ensure we get a reasonable result + assert!(max_weight > 0); + assert!(!solution.is_empty()); + } + + // Property-based test: solution should always be valid + #[test] + fn test_solution_validity_property() { + let test_cases = vec![ + create_jobs_basic(), + create_jobs_greedy_fails(), + create_jobs_large_case(), + ]; + + for jobs in test_cases { + let mut scheduler = WeightedScheduler::new(jobs.clone()); + let (max_weight, solution) = scheduler.solve(); + + // Property: solution must be valid (no overlapping jobs) + assert!(is_valid_solution(&jobs, &solution)); + + // Property: calculated weight must match returned weight + assert_eq!(max_weight, calculate_total_weight(&jobs, &solution)); + } + } + + // Functional testing pattern: test with transformations + #[test] + fn test_job_order_independence() { + let mut jobs = create_jobs_basic(); + let mut scheduler1 = WeightedScheduler::new(jobs.clone()); + let (weight1, _) = scheduler1.solve(); + + // Test that reversing job order doesn't change optimal weight + jobs.reverse(); + let mut scheduler2 = WeightedScheduler::new(jobs); + let (weight2, _) = scheduler2.solve(); + + assert_eq!(weight1, weight2); + } + + // Test edge case: all jobs overlap + #[test] + fn test_all_jobs_overlap() { + let jobs = vec![ + Job::new(1, 5, 10, 0), + Job::new(2, 6, 8, 1), + Job::new(3, 7, 12, 2), + Job::new(4, 8, 6, 3), + ]; + + let mut scheduler = WeightedScheduler::new(jobs.clone()); + let (max_weight, solution) = scheduler.solve(); + + // Should pick the highest weight job (12) + assert_eq!(max_weight, 12); + assert_eq!(solution.len(), 1); + assert_eq!(solution[0], 2); // Job with weight 12 + } + + #[test] + fn test_empty_jobs() { + let mut scheduler = WeightedScheduler::new(vec![]); + let (max_weight, solution) = scheduler.solve(); + assert_eq!(max_weight, 0); + assert!(solution.is_empty()); + } + + #[test] + fn test_single_job() { + let jobs = vec![Job::new(1, 3, 5, 0)]; + let mut scheduler = WeightedScheduler::new(jobs); + let (max_weight, solution) = scheduler.solve(); + assert_eq!(max_weight, 5); + assert_eq!(solution, vec![0]); + } + + #[test] + fn test_no_overlap() { + let jobs = vec![ + Job::new(1, 2, 3, 0), + Job::new(3, 4, 2, 1), + Job::new(5, 6, 4, 2), + ]; + let mut scheduler = WeightedScheduler::new(jobs); + let (max_weight, solution) = scheduler.solve(); + assert_eq!(max_weight, 9); // All jobs can be selected + assert_eq!(solution.len(), 3); + } + + #[test] + fn test_basic_overlap() { + let jobs = vec![ + Job::new(1, 4, 3, 0), + Job::new(2, 6, 5, 1), + Job::new(4, 7, 2, 2), + Job::new(6, 8, 4, 3), + ]; + let mut scheduler = WeightedScheduler::new(jobs); + let (max_weight, _solution) = scheduler.solve(); + // Optimal solution should pick jobs 1 (weight 5) and 3 (weight 4) = 9 + assert_eq!(max_weight, 9); + } +} diff --git a/src/algorithms/stable_matching/bipartite.rs b/src/algorithms/stable_matching/bipartite.rs new file mode 100644 index 0000000..cd65d53 --- /dev/null +++ b/src/algorithms/stable_matching/bipartite.rs @@ -0,0 +1,308 @@ +use std::collections::{HashMap, HashSet}; + +/// Represents preference orderings as a total order on node IDs. +/// This is a simple wrapper that encodes a ranked preference list. +#[derive(Clone, Debug)] +pub struct Preferences { + pub ordered_ids: Vec, +} + +impl Preferences { + pub fn new(ordered_ids: Vec) -> Self { + Preferences { ordered_ids } + } + + /// Check if `a` is preferred over `b` in this preference order. + /// Returns None if either ID is not in the preference list. + pub fn prefers(&self, a: &K, b: &K) -> Option { + let pos_a = self.ordered_ids.iter().position(|id| id == a)?; + let pos_b = self.ordered_ids.iter().position(|id| id == b)?; + Some(pos_a < pos_b) + } +} + +/// Trait for determining bipartite compatibility. +/// Defines a morphism from L × R → Hom(*, Ω) where Ω is the two-element Boolean algebra. +pub trait Compatible { + fn can_connect(&self, left: &L, right: &R) -> bool; +} + +/// Generic bipartite graph structure with independent left and right node types. +/// Type parameters: +/// - `K`: Key type for identifying nodes (must be Hash + Eq + Clone) +/// - `L`: Left partition node type +/// - `R`: Right partition node type +pub struct BipartiteGraph { + pub left_partition: HashMap, + pub right_partition: HashMap, + edges_from_left: HashMap>, + edges_from_right: HashMap>, +} + +impl BipartiteGraph { + pub fn new(left_partition: HashMap, right_partition: HashMap) -> Self { + BipartiteGraph { + left_partition, + right_partition, + edges_from_left: HashMap::new(), + edges_from_right: HashMap::new(), + } + } + + pub fn add_edge(&mut self, left_id: K, right_id: K) -> Result<(), &'static str> { + self.left_partition + .contains_key(&left_id) + .then(|| ()) + .ok_or("Left node ID not found")?; + self.right_partition + .contains_key(&right_id) + .then(|| ()) + .ok_or("Right node ID not found")?; + + self.edges_from_left + .entry(left_id.clone()) + .or_insert_with(Vec::new) + .push(right_id.clone()); + self.edges_from_right + .entry(right_id) + .or_insert_with(Vec::new) + .push(left_id); + + Ok(()) + } + + pub fn neighbors_of_left(&self, left_id: &K) -> Option<&[K]> { + self.edges_from_left.get(left_id).map(|v| v.as_slice()) + } + + pub fn neighbors_of_right(&self, right_id: &K) -> Option<&[K]> { + self.edges_from_right.get(right_id).map(|v| v.as_slice()) + } +} + +/// Generic stable matching algorithm using the Gale-Shapley approach. +/// +/// Type parameters: +/// - `K`: Key type for identifying nodes (must be Hash + Eq + Clone + Debug) +/// - `L`: Left partition node type +/// - `R`: Right partition node type +/// +/// This function implements the Gale-Shapley algorithm as a fold operation, +/// viewing the matching process as successive refinements of a monoid structure +/// (matchings form a commutative monoid under compatibility). +pub fn stable_match( + graph: &BipartiteGraph, + left_prefs: &HashMap>, + right_prefs: &HashMap>, +) -> Result, &'static str> +where + K: Eq + std::hash::Hash + Clone + std::fmt::Debug, +{ + // Initialize state: all left nodes are free, no proposals yet made + let mut free_left: HashSet = graph.left_partition.keys().cloned().collect(); + let mut next_proposal: HashMap = HashMap::new(); + let mut matches: HashMap = HashMap::new(); // right_id -> left_id + + // Main loop: process free left nodes until none remain + while let Some(left_id) = free_left.iter().next().cloned() { + let prefs = left_prefs + .get(&left_id) + .ok_or("Left node has no preferences")?; + + let proposal_index = next_proposal.entry(left_id.clone()).or_insert(0); + + // If this left node has exhausted their preference list, remove them + if *proposal_index >= prefs.ordered_ids.len() { + free_left.remove(&left_id); + continue; + } + + let right_id = prefs.ordered_ids[*proposal_index].clone(); + *proposal_index += 1; + + // Verify right node exists + if !graph.right_partition.contains_key(&right_id) { + return Err("Proposed right node does not exist"); + } + + // Attempt the proposal + match matches.get(&right_id).cloned() { + // Case 1: Right node is unmatched - accept proposal + None => { + matches.insert(right_id, left_id.clone()); + free_left.remove(&left_id); + } + // Case 2: Right node is matched - check if they prefer the new proposer + Some(current_left_id) => { + let right_prefs = right_prefs + .get(&right_id) + .ok_or("Right node has no preferences")?; + + if right_prefs + .prefers(&left_id, ¤t_left_id) + .ok_or("Preference comparison failed")? + { + // Prefer new proposer: update match and free current match + matches.insert(right_id, left_id.clone()); + free_left.remove(&left_id); + free_left.insert(current_left_id); + } + // Else: reject proposal, keep left node free for next iteration + } + } + } + + Ok(matches) +} + + +// ============================================================================ +// Example Usage and Tests +// ============================================================================ + +#[derive(Clone, Debug)] +pub struct Person { + pub id: u32, + pub name: String, + pub gender: Gender, +} + +#[derive(Clone, Copy, Debug, PartialEq)] +pub enum Gender { + Male, + Female, +} + +pub struct GenderValidator; + +impl Compatible for GenderValidator { + fn can_connect(&self, left: &Person, right: &Person) -> bool { + left.gender != right.gender + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_stable_match_simple() { + // Create preferences for a simple matching problem + let left_prefs: HashMap> = HashMap::from([ + (1, Preferences::new(vec![2, 3])), + (4, Preferences::new(vec![3, 2])), + ]); + + let right_prefs: HashMap> = HashMap::from([ + (2, Preferences::new(vec![1, 4])), + (3, Preferences::new(vec![4, 1])), + ]); + + // Create bipartite graph with Person nodes + let left_partition = HashMap::from([ + (1, Person { + id: 1, + name: "Alice".to_string(), + gender: Gender::Female, + }), + (4, Person { + id: 4, + name: "Bob".to_string(), + gender: Gender::Female, + }), + ]); + + let right_partition = HashMap::from([ + (2, Person { + id: 2, + name: "Charlie".to_string(), + gender: Gender::Male, + }), + (3, Person { + id: 3, + name: "David".to_string(), + gender: Gender::Male, + }), + ]); + + let graph: BipartiteGraph = + BipartiteGraph::new(left_partition, right_partition); + + // Run stable matching algorithm + let result = stable_match::( + &graph, + &left_prefs, + &right_prefs, + ); + + assert!(result.is_ok()); + let matches = result.unwrap(); + assert_eq!(matches.len(), 2); // Both should be matched + + println!("Matches: {:?}", matches); + } + + #[test] + fn test_stable_match_with_string_keys() { + // Demonstrate that the algorithm works with different key types + let left_prefs: HashMap> = HashMap::from([ + ("alice".to_string(), Preferences::new(vec!["bob".to_string(), "charlie".to_string()])), + ("diana".to_string(), Preferences::new(vec!["charlie".to_string(), "bob".to_string()])), + ]); + + let right_prefs: HashMap> = HashMap::from([ + ("bob".to_string(), Preferences::new(vec!["alice".to_string(), "diana".to_string()])), + ("charlie".to_string(), Preferences::new(vec!["diana".to_string(), "alice".to_string()])), + ]); + + let left_partition = HashMap::from([ + ("alice".to_string(), Person { + id: 1, + name: "Alice".to_string(), + gender: Gender::Female, + }), + ("diana".to_string(), Person { + id: 2, + name: "Diana".to_string(), + gender: Gender::Female, + }), + ]); + + let right_partition = HashMap::from([ + ("bob".to_string(), Person { + id: 3, + name: "Bob".to_string(), + gender: Gender::Male, + }), + ("charlie".to_string(), Person { + id: 4, + name: "Charlie".to_string(), + gender: Gender::Male, + }), + ]); + + let graph: BipartiteGraph = + BipartiteGraph::new(left_partition, right_partition); + + let result = stable_match::( + &graph, + &left_prefs, + &right_prefs, + ); + + assert!(result.is_ok()); + let matches = result.unwrap(); + assert_eq!(matches.len(), 2); + println!("String-keyed matches: {:?}", matches); + } + + #[test] + fn test_preference_order() { + let prefs = Preferences::new(vec![1, 2, 3, 4]); + + assert_eq!(prefs.prefers(&1, &2), Some(true)); + assert_eq!(prefs.prefers(&2, &1), Some(false)); + assert_eq!(prefs.prefers(&1, &1), Some(false)); // Equal, not preferred + assert_eq!(prefs.prefers(&5, &1), None); // 5 not in list + } +} diff --git a/src/algorithms/stable_matching/gale_shapley.rs b/src/algorithms/stable_matching/gale_shapley.rs index 5d49ce4..11c25e0 100644 --- a/src/algorithms/stable_matching/gale_shapley.rs +++ b/src/algorithms/stable_matching/gale_shapley.rs @@ -26,171 +26,8 @@ use std::collections::{HashMap, HashSet}; use rand::seq::SliceRandom; +use crate::algorithms::stable_matching::types::{Gender, Person, Preferences}; -/// Represents the gender of a person in the matching problem. -/// -/// This enum is used to distinguish between the two sides of the bipartite matching. -/// In the classical formulation, these are typically "men" and "women", but the -/// algorithm applies to any two-sided matching scenario. -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -pub enum Gender { - Male, - Female, -} - -/// A person participating in the stable matching problem. -/// -/// Each person has a unique identifier and belongs to one of two groups -/// distinguished by gender. The algorithm ensures each person from one -/// group is matched with exactly one person from the other group. -/// -/// ## Type Theory Note -/// This represents an element in one of two disjoint sets that form -/// the domain of our matching function. -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct Person { - pub id: u32, - pub gender: Gender, -} - -/// Represents a person's ordered preference list over potential partners. -/// -/// This structure encapsulates the total ordering required by the Gale-Shapley -/// algorithm. Each person must have a complete, strict preference ordering -/// over all potential partners. -/// -/// ## Category Theory Note -/// This represents a morphism in the category of preferences, where objects -/// are people and morphisms represent preference relations. -/// -/// ## Examples -/// -/// ``` -/// # use algorithms::stable_matching::*; -/// // Person 1 prefers partners in order: 3, 1, 2 -/// let prefs = Preferences::new(1, vec!)?;[1][2][3] -/// -/// // Check if person 3 is preferred over person 2 -/// assert!(prefs.prefers(3, 2)?); -/// # Ok::<(), &'static str>(()) -/// ``` -#[derive(Debug, Clone)] -pub struct Preferences { - /// The ordered list of preferred partner IDs (most preferred first) - pub ordered_ids: Vec, - /// The ID of the person who holds these preferences - pub person_id: u32, -} - -impl Preferences { - - /// Creates a new preference list with validation. - /// - /// # Arguments - /// * `person_id` - The ID of the person who holds these preferences - /// * `ordered_ids` - List of preferred partner IDs in order of preference - /// - /// # Returns - /// * `Ok(Preferences)` - Valid preference list - /// * `Err(&'static str)` - Error message if validation fails - /// - /// # Errors - /// * Returns error if the preference list is empty - /// * Returns error if there are duplicate preferences - /// - /// # Examples - /// - /// ``` - /// # use algorithms::stable_matching::*; - /// # use crate::Preferences; - /// // Valid preferences - /// let prefs = Preferences::new(1, vec!)?;[2][3][4] - /// - /// // Invalid - empty list - /// assert!(Preferences::new(1, vec![]).is_err()); - /// - /// // Invalid - duplicates - /// assert!(Preferences::new(1, vec!).is_err());[3][2] - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn new(person_id: u32, ordered_ids: Vec) -> Result { - if ordered_ids.is_empty() { - return Err("Preference list cannot be empty"); - } - - let mut unique_ids = ordered_ids.clone(); - unique_ids.sort(); - unique_ids.dedup(); - if unique_ids.len() != ordered_ids.len() { - return Err("No duplicate preferences allowed"); - } - - Ok(Preferences { - person_id, - ordered_ids, - }) - } - - /// Determines if person `a_id` is preferred over person `b_id`. - /// - /// This implements the strict preference relation required for stable matching. - /// Returns `true` if `a_id` appears earlier in the preference list than `b_id`. - /// - /// # Arguments - /// * `a_id` - ID of the first person to compare - /// * `b_id` - ID of the second person to compare - /// - /// # Returns - /// * `Ok(true)` - If `a_id` is preferred over `b_id` - /// * `Ok(false)` - If `b_id` is preferred over `a_id` - /// * `Err(&'static str)` - If either person is not in the preference list - /// - /// # Mathematical Note - /// This implements the relation `a_id ≻ b_id` in preference theory notation. - /// - /// # Examples - /// - /// ``` - /// # use algorithms::stable_matching::*; - /// # use crate::Preferences; - /// let prefs = Preferences::new(1, vec!)?;[2][3][5] - /// - /// assert!(prefs.prefers(3, 5)?); // 3 is preferred over 5 - /// assert!(!prefs.prefers(5, 3)?); // 5 is not preferred over 3 - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn prefers(&self, a_id: u32, b_id: u32) -> Result { - let pos_a = self.ordered_ids.iter().position(|&id| id == a_id) - .ok_or("Person A not found in preference list")?; - let pos_b = self.ordered_ids.iter().position(|&id| id == b_id) - .ok_or("Person B not found in preference list")?; - - Ok(pos_a < pos_b) - } - - /// Returns the most preferred person's ID. - /// - /// # Returns - /// The ID of the person at the top of this preference list. - /// - /// # Panics - /// Panics if the preference list is empty (which should be impossible - /// if constructed through `new()`). - /// - /// # Examples - /// - /// ``` - /// # use algorithms::stable_matching::*; - /// # use crate::Preferences; - /// use algorithms::stable_matching::*; - /// let prefs = Preferences::new(1, vec!)?;[7][3][5] - /// assert_eq!(prefs.most_preferred(), 7); - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn most_preferred(&self) -> u32 { - self.ordered_ids[0] - } -} /// The main structure representing a stable matching problem instance. /// diff --git a/src/algorithms/stable_matching/mod.rs b/src/algorithms/stable_matching/mod.rs index 37f5b56..98d710e 100644 --- a/src/algorithms/stable_matching/mod.rs +++ b/src/algorithms/stable_matching/mod.rs @@ -4,8 +4,11 @@ // Declare submodules if you split them pub mod gale_shapley; +pub mod types; +pub mod bipartite; //pub mod types; // Re-export the public API from submodules pub use gale_shapley::*; -//pub use types::*; +pub use bipartite::*; +pub use types::*; diff --git a/src/algorithms/stable_matching/types.rs b/src/algorithms/stable_matching/types.rs new file mode 100644 index 0000000..0480f8e --- /dev/null +++ b/src/algorithms/stable_matching/types.rs @@ -0,0 +1,165 @@ + +/// Represents the gender of a person in the matching problem. +/// +/// This enum is used to distinguish between the two sides of the bipartite matching. +/// In the classical formulation, these are typically "men" and "women", but the +/// algorithm applies to any two-sided matching scenario. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum Gender { + Male, + Female, +} + +/// A person participating in the stable matching problem. +/// +/// Each person has a unique identifier and belongs to one of two groups +/// distinguished by gender. The algorithm ensures each person from one +/// group is matched with exactly one person from the other group. +/// +/// ## Type Theory Note +/// This represents an element in one of two disjoint sets that form +/// the domain of our matching function. +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct Person { + pub id: u32, + pub gender: Gender, +} + +/// Represents a person's ordered preference list over potential partners. +/// +/// This structure encapsulates the total ordering required by the Gale-Shapley +/// algorithm. Each person must have a complete, strict preference ordering +/// over all potential partners. +/// +/// ## Category Theory Note +/// This represents a morphism in the category of preferences, where objects +/// are people and morphisms represent preference relations. +/// +/// ## Examples +/// +/// ``` +/// # use algorithms::stable_matching::*; +/// // Person 1 prefers partners in order: 3, 1, 2 +/// let prefs = Preferences::new(1, vec!)?;[1][2][3] +/// +/// // Check if person 3 is preferred over person 2 +/// assert!(prefs.prefers(3, 2)?); +/// # Ok::<(), &'static str>(()) +/// ``` +#[derive(Debug, Clone)] +pub struct Preferences { + /// The ordered list of preferred partner IDs (most preferred first) + pub ordered_ids: Vec, + /// The ID of the person who holds these preferences + pub person_id: u32, +} + +impl Preferences { + + /// Creates a new preference list with validation. + /// + /// # Arguments + /// * `person_id` - The ID of the person who holds these preferences + /// * `ordered_ids` - List of preferred partner IDs in order of preference + /// + /// # Returns + /// * `Ok(Preferences)` - Valid preference list + /// * `Err(&'static str)` - Error message if validation fails + /// + /// # Errors + /// * Returns error if the preference list is empty + /// * Returns error if there are duplicate preferences + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use crate::Preferences; + /// // Valid preferences + /// let prefs = Preferences::new(1, vec!)?;[2][3][4] + /// + /// // Invalid - empty list + /// assert!(Preferences::new(1, vec![]).is_err()); + /// + /// // Invalid - duplicates + /// assert!(Preferences::new(1, vec!).is_err());[3][2] + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn new(person_id: u32, ordered_ids: Vec) -> Result { + if ordered_ids.is_empty() { + return Err("Preference list cannot be empty"); + } + + let mut unique_ids = ordered_ids.clone(); + unique_ids.sort(); + unique_ids.dedup(); + if unique_ids.len() != ordered_ids.len() { + return Err("No duplicate preferences allowed"); + } + + Ok(Preferences { + person_id, + ordered_ids, + }) + } + + /// Determines if person `a_id` is preferred over person `b_id`. + /// + /// This implements the strict preference relation required for stable matching. + /// Returns `true` if `a_id` appears earlier in the preference list than `b_id`. + /// + /// # Arguments + /// * `a_id` - ID of the first person to compare + /// * `b_id` - ID of the second person to compare + /// + /// # Returns + /// * `Ok(true)` - If `a_id` is preferred over `b_id` + /// * `Ok(false)` - If `b_id` is preferred over `a_id` + /// * `Err(&'static str)` - If either person is not in the preference list + /// + /// # Mathematical Note + /// This implements the relation `a_id ≻ b_id` in preference theory notation. + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use crate::Preferences; + /// let prefs = Preferences::new(1, vec!)?;[2][3][5] + /// + /// assert!(prefs.prefers(3, 5)?); // 3 is preferred over 5 + /// assert!(!prefs.prefers(5, 3)?); // 5 is not preferred over 3 + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn prefers(&self, a_id: u32, b_id: u32) -> Result { + let pos_a = self.ordered_ids.iter().position(|&id| id == a_id) + .ok_or("Person A not found in preference list")?; + let pos_b = self.ordered_ids.iter().position(|&id| id == b_id) + .ok_or("Person B not found in preference list")?; + + Ok(pos_a < pos_b) + } + + /// Returns the most preferred person's ID. + /// + /// # Returns + /// The ID of the person at the top of this preference list. + /// + /// # Panics + /// Panics if the preference list is empty (which should be impossible + /// if constructed through `new()`). + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use crate::Preferences; + /// use algorithms::stable_matching::*; + /// let prefs = Preferences::new(1, vec!)?;[7][3][5] + /// assert_eq!(prefs.most_preferred(), 7); + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn most_preferred(&self) -> u32 { + self.ordered_ids[0] + } +} diff --git a/src/main.rs b/src/main.rs deleted file mode 100644 index 1e9610a..0000000 --- a/src/main.rs +++ /dev/null @@ -1,12 +0,0 @@ -//use algorithms::stable_matching::*; -use algorithms::interview_scheduling::*; - -fn main() { - // Example usage of different algorithms - println!("Running algorithm examples..."); - - // Use stable matching - let config = InterviewGenConfig::default(); - let interviews = generate_random_interviews(&config); - println!("Generated {} interviews", interviews.len()); -} -- 2.49.1