Coverage for algorithm/matching.py: 100%

1""" 

2The matching algorithm is a stable marriage algorithm that matches students 

3to placements based on their preferences. The algorithm is implemented in the 

4`Matching` class. The `find_best_match` method finds the best match for students and placements. 

5""" 

6 

7from typing import List, Dict, Tuple 

8 

9 

10class Matching: 

11 """Class to match students to placements based on their preferences.""" 

12 

13 def __init__( 

14 self, 

15 student_rank: Dict[str, List[str]], 

16 placement_rank: Dict[str, Dict[str, int]], 

17 ): 

18 # Students' preferences 

19 self.student_rank = student_rank 

20 # Employers' rankings, includes "positions" key 

21 self.placement_rank = placement_rank 

22 # To store the final matches 

23 self.potential_match: Dict[str, List[str]] = {} 

24 # To store the final matches (Unmatched, Matched) 

25 self.final_result: Tuple[List[str], Dict[str, List[str]]] = ([], {}) 

26 

27 def find_best_match(self) -> Tuple[List[str], Dict[str, List[str]]]: 

28 """Find the best match for students and placements.""" 

29 students = list(self.student_rank.keys()) # List of unmatched students 

30 unmapped = [] # List of students who cannot be matched (no more preferences) 

31 # Keep track of employers' current engagements 

32 placement_current_match: Dict[str, List[str]] = { 

33 placement: [] for placement in self.placement_rank.keys() 

34 } 

35 

36 # print("Initial state:") 

37 # print(f"Students: {students}") 

38 # print(f"Employers' current matches: {placement_current_match}") 

39 

40 while students: 

41 student = students.pop(0) # Pick the next unmatched student 

42 # print(f"\nProcessing student: {student}") 

43 

44 if not self.student_rank[student]: # If student has no more preferences 

45 # print(f"Student {student} has no more preferences and is unmapped.") 

46 unmapped.append(student) 

47 continue 

48 

49 choice = self.student_rank[student].pop(0) 

50 # print(f"{student} prefers placement: {choice}") 

51 

52 # Check current matches of the chosen employer 

53 current_matches = placement_current_match[choice] 

54 positions = int(self.placement_rank[choice]["positions"]) 

55 

56 # If there are positions available, add the student 

57 if ( 

58 len(current_matches) < positions 

59 and student in self.placement_rank[choice] 

60 ): 

61 # print(f"{choice} has available positions. Adding {student}.") 

62 placement_current_match[choice].append(student) 

63 self.potential_match[choice] = placement_current_match[choice] 

64 

65 else: 

66 # print(f"{choice} is full or {student} is not ranked by the employer.") 

67 if current_matches: 

68 # print(f"Current matches at {choice}: {current_matches}") 

69 

70 # Find the weakest match using the employer's ranking 

71 weakest_match = current_matches[-1] # Get the least preferred match 

72 weakest_match_rank = self.placement_rank[choice][weakest_match] 

73 index = len(current_matches) - 1 

74 

75 for match in current_matches: 

76 if self.placement_rank[choice][match] > weakest_match_rank: 

77 weakest_match = match 

78 weakest_match_rank = self.placement_rank[choice][match] 

79 index = current_matches.index(weakest_match) 

80 

81 # Check if the student is in the employer's ranking 

82 if student in self.placement_rank[choice]: 

83 new_candidate_rank = self.placement_rank[choice][student] 

84 # print( 

85 # f"Comparing {student} (rank {new_candidate_rank}) with 

86 # weakest match {weakest_match} (rank {weakest_match_rank})." 

87 # ) 

88 

89 # If new student is ranked higher (lower number), replace the weakest match 

90 if new_candidate_rank < weakest_match_rank: 

91 # print( 

92 # f"{student} is ranked higher than {weakest_match}. Replacing." 

93 # ) 

94 placement_current_match[choice][ 

95 index 

96 ] = student # Replace weakest match 

97 self.potential_match[choice] = placement_current_match[ 

98 choice 

99 ] 

100 students.insert( 

101 0, weakest_match 

102 ) # Re-add the replaced student to the unmatched list 

103 else: 

104 # print( 

105 # f"{student} is ranked lower than {weakest_match}. Rejected." 

106 # ) 

107 students.insert( 

108 0, student 

109 ) # Add student back to the unmatched list 

110 else: 

111 # print(f"{student} is not ranked by {choice}. Rejected.") 

112 students.insert( 

113 0, student 

114 ) # Re-add student to the unmatched list 

115 else: 

116 # print( 

117 # f"{choice} has no current matches. {student} has not been ranked by {choice}." 

118 # ) 

119 students.insert(0, student) 

120 

121 self.final_result = (unmapped, self.potential_match) 

122 # print("\nFinal result:") 

123 # print(f"Unmapped students: {self.final_result[0]}") 

124 # print(f"Matched students: {self.final_result[1]}") 

125 return self.final_result 

126 

127 def get_matches(self) -> Tuple[List[str], Dict[str, List[str]]]: 

128 """Get final result.""" 

129 # print("\nReturning final matches:") 

130 # print(f"Unmapped: {self.final_result[0]}") 

131 # print(f"Matched: {self.final_result[1]}") 

132 return self.final_result