Coverage for tests/model_tests/test_complex_algorithm.py: 100%
56 statements
« prev ^ index » next coverage.py v7.8.0, created at 2025-05-05 14:02 +0000
1"""Tests for the matching algorithm."""
3import os
4import sys
5import time
6import random
8# flake8: noqa: F811
10sys.path.append(
11 os.path.dirname(os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
12)
14from algorithm.matching import Matching
17def test_complex_student_employer_preferences():
18 """Tests a complex scenario with multiple students and employers."""
19 students_preference = {
20 "Student_1": ["company_1", "company_2", "company_3"],
21 "Student_2": ["company_2"],
22 "Student_3": ["company_5", "company_4", "company_3"],
23 "Student_4": ["company_1", "company_5", "company_6"],
24 "Student_5": ["company_6", "company_7", "company_8"],
25 "Student_6": ["company_4", "company_5", "company_9"],
26 "Student_7": ["company_2", "company_3", "company_7"],
27 "Student_8": ["company_1", "company_6", "company_10"],
28 "Student_9": ["company_3", "company_8", "company_9"],
29 "Student_10": ["company_2", "company_5", "company_6"],
30 }
32 employer_preference = {
33 "company_1": {
34 "positions": 2,
35 "Student_7": 1,
36 "Student_1": 2,
37 "Student_4": 3,
38 "Student_10": 4,
39 "Student_2": 5,
40 "Student_3": 6,
41 "Student_5": 7,
42 "Student_9": 8,
43 "Student_8": 9,
44 "Student_6": 10,
45 },
46 "company_2": {
47 "positions": 1,
48 "Student_7": 1,
49 "Student_1": 2,
50 "Student_4": 3,
51 "Student_10": 4,
52 "Student_3": 5,
53 "Student_2": 6,
54 "Student_9": 7,
55 "Student_5": 8,
56 "Student_8": 9,
57 "Student_6": 10,
58 },
59 "company_3": {
60 "positions": 2,
61 "Student_7": 1,
62 "Student_1": 2,
63 "Student_4": 3,
64 "Student_10": 4,
65 "Student_2": 5,
66 "Student_8": 6,
67 "Student_3": 7,
68 "Student_5": 8,
69 "Student_9": 9,
70 "Student_6": 10,
71 },
72 "company_4": {
73 "positions": 1,
74 "Student_7": 1,
75 "Student_1": 2,
76 "Student_4": 3,
77 "Student_10": 4,
78 "Student_3": 5,
79 "Student_2": 6,
80 "Student_9": 7,
81 "Student_5": 8,
82 "Student_8": 9,
83 "Student_6": 10,
84 },
85 "company_5": {
86 "positions": 2,
87 "Student_7": 1,
88 "Student_1": 2,
89 "Student_4": 3,
90 "Student_10": 4,
91 "Student_2": 5,
92 "Student_3": 6,
93 "Student_9": 7,
94 "Student_5": 8,
95 "Student_8": 9,
96 "Student_6": 10,
97 },
98 "company_6": {
99 "positions": 1,
100 "Student_7": 1,
101 "Student_1": 2,
102 "Student_4": 3,
103 "Student_10": 4,
104 "Student_2": 5,
105 "Student_5": 6,
106 "Student_8": 7,
107 "Student_9": 8,
108 "Student_3": 9,
109 "Student_6": 10,
110 },
111 "company_7": {
112 "positions": 1,
113 "Student_7": 1,
114 "Student_1": 2,
115 "Student_4": 3,
116 "Student_10": 4,
117 "Student_3": 5,
118 "Student_2": 6,
119 "Student_9": 7,
120 "Student_5": 8,
121 "Student_6": 9,
122 "Student_8": 10,
123 },
124 "company_8": {
125 "positions": 1,
126 "Student_7": 1,
127 "Student_1": 2,
128 "Student_4": 3,
129 "Student_10": 4,
130 "Student_3": 5,
131 "Student_2": 6,
132 "Student_9": 7,
133 "Student_5": 8,
134 "Student_8": 9,
135 "Student_6": 10,
136 },
137 "company_9": {
138 "positions": 1,
139 "Student_7": 1,
140 "Student_1": 2,
141 "Student_4": 3,
142 "Student_10": 4,
143 "Student_2": 5,
144 "Student_3": 6,
145 "Student_9": 7,
146 "Student_5": 8,
147 "Student_8": 9,
148 "Student_6": 10,
149 },
150 "company_10": {
151 "positions": 1,
152 "Student_7": 1,
153 "Student_1": 2,
154 "Student_4": 3,
155 "Student_10": 4,
156 "Student_2": 5,
157 "Student_3": 6,
158 "Student_9": 7,
159 "Student_5": 8,
160 "Student_8": 9,
161 "Student_6": 10,
162 },
163 }
165 match = Matching(students_preference, employer_preference)
166 result = match.find_best_match()
168 expected = (
169 ["Student_2"],
170 {
171 "company_1": ["Student_1", "Student_4"],
172 "company_2": ["Student_7"],
173 "company_5": ["Student_3", "Student_10"],
174 "company_6": ["Student_5"],
175 "company_4": ["Student_6"],
176 "company_3": ["Student_9"],
177 "company_10": ["Student_8"],
178 },
179 )
180 assert result == expected
183def test_complex_student_employer_preferences_v2():
184 """Tests a complex scenario with multiple students and employers."""
185 students_preference = {
186 "Student_1": ["company_1", "company_2", "company_3"],
187 "Student_2": ["company_2", "company_4"],
188 "Student_3": ["company_1", "company_5", "company_6"],
189 "Student_4": ["company_3", "company_2", "company_1"],
190 "Student_5": ["company_7", "company_8", "company_4"],
191 "Student_6": ["company_8", "company_9", "company_5"],
192 "Student_7": ["company_1", "company_6"],
193 "Student_8": ["company_5", "company_3", "company_2"],
194 "Student_9": ["company_4", "company_7", "company_10"],
195 "Student_10": ["company_2", "company_9", "company_8"],
196 }
198 employer_preference = {
199 "company_1": {
200 "positions": 2,
201 "Student_1": 1,
202 "Student_3": 2,
203 "Student_4": 3,
204 "Student_7": 4,
205 "Student_5": 5,
206 "Student_10": 6,
207 "Student_9": 7,
208 "Student_2": 8,
209 "Student_6": 9,
210 "Student_8": 10,
211 },
212 "company_2": {
213 "positions": 2,
214 "Student_2": 1,
215 "Student_1": 2,
216 "Student_4": 3,
217 "Student_10": 4,
218 "Student_6": 5,
219 "Student_9": 6,
220 "Student_8": 7,
221 "Student_7": 8,
222 "Student_5": 9,
223 "Student_3": 10,
224 },
225 "company_3": {
226 "positions": 1,
227 "Student_4": 1,
228 "Student_1": 2,
229 "Student_8": 3,
230 "Student_2": 4,
231 "Student_10": 5,
232 "Student_5": 6,
233 "Student_6": 7,
234 "Student_3": 8,
235 "Student_9": 9,
236 "Student_7": 10,
237 },
238 "company_4": {
239 "positions": 2,
240 "Student_2": 1,
241 "Student_5": 2,
242 "Student_9": 3,
243 "Student_1": 4,
244 "Student_4": 5,
245 "Student_3": 6,
246 "Student_8": 7,
247 "Student_10": 8,
248 "Student_6": 9,
249 "Student_7": 10,
250 },
251 "company_5": {
252 "positions": 2,
253 "Student_3": 1,
254 "Student_6": 2,
255 "Student_8": 3,
256 "Student_1": 4,
257 "Student_2": 5,
258 "Student_4": 6,
259 "Student_10": 7,
260 "Student_5": 8,
261 "Student_7": 9,
262 "Student_9": 10,
263 },
264 "company_6": {
265 "positions": 1,
266 "Student_1": 1,
267 "Student_2": 2,
268 "Student_7": 3,
269 "Student_4": 4,
270 "Student_3": 5,
271 "Student_9": 6,
272 "Student_10": 7,
273 "Student_8": 8,
274 "Student_5": 9,
275 "Student_6": 10,
276 },
277 "company_7": {
278 "positions": 1,
279 "Student_5": 1,
280 "Student_9": 2,
281 "Student_3": 3,
282 "Student_2": 4,
283 "Student_4": 5,
284 "Student_8": 6,
285 "Student_10": 7,
286 "Student_6": 8,
287 "Student_1": 9,
288 "Student_7": 10,
289 },
290 "company_8": {
291 "positions": 1,
292 "Student_6": 1,
293 "Student_1": 2,
294 "Student_2": 3,
295 "Student_5": 4,
296 "Student_3": 5,
297 "Student_10": 6,
298 "Student_7": 7,
299 "Student_8": 8,
300 "Student_4": 9,
301 "Student_9": 10,
302 },
303 "company_9": {
304 "positions": 1,
305 "Student_6": 1,
306 "Student_10": 2,
307 "Student_5": 3,
308 "Student_2": 4,
309 "Student_7": 5,
310 "Student_1": 6,
311 "Student_3": 7,
312 "Student_8": 8,
313 "Student_4": 9,
314 "Student_9": 10,
315 },
316 "company_10": {
317 "positions": 1,
318 "Student_4": 1,
319 "Student_2": 2,
320 "Student_9": 3,
321 "Student_5": 4,
322 "Student_7": 5,
323 "Student_3": 6,
324 "Student_1": 7,
325 "Student_10": 8,
326 "Student_6": 9,
327 "Student_8": 10,
328 },
329 }
331 match = Matching(students_preference, employer_preference)
332 result = match.find_best_match()
334 expected = (
335 [],
336 {
337 "company_1": ["Student_1", "Student_3"],
338 "company_2": ["Student_2", "Student_10"],
339 "company_3": ["Student_4"],
340 "company_7": ["Student_5"],
341 "company_8": ["Student_6"],
342 "company_6": ["Student_7"],
343 "company_5": ["Student_8"],
344 "company_4": ["Student_9"],
345 },
346 )
348 assert result == expected
351def test_complex_student_employer_preferences_v3():
352 """Tests a complex scenario with multiple students and employers."""
353 students_preference = {
354 "Student_1": ["company_1", "company_2"],
355 "Student_2": ["company_1", "company_3", "company_4"],
356 "Student_3": ["company_5", "company_6"],
357 "Student_4": ["company_2", "company_7", "company_5"],
358 "Student_5": ["company_3", "company_4", "company_8"],
359 "Student_6": ["company_1", "company_8", "company_3"],
360 "Student_7": ["company_5", "company_6", "company_9"],
361 "Student_8": ["company_2", "company_3"],
362 "Student_9": ["company_7", "company_4"],
363 "Student_10": ["company_1", "company_9", "company_10"],
364 }
366 employer_preference = {
367 "company_1": {
368 "positions": 2,
369 "Student_1": 1,
370 "Student_2": 2,
371 "Student_6": 3,
372 "Student_10": 4,
373 "Student_4": 5,
374 "Student_8": 6,
375 },
376 "company_2": {
377 "positions": 1,
378 "Student_4": 1,
379 "Student_1": 2,
380 "Student_8": 3,
381 "Student_5": 4,
382 "Student_3": 5,
383 "Student_10": 6,
384 "Student_2": 7,
385 "Student_7": 8,
386 "Student_9": 9,
387 },
388 "company_3": {
389 "positions": 2,
390 "Student_10": 1,
391 "Student_2": 2,
392 "Student_6": 3,
393 "Student_8": 4,
394 "Student_5": 5,
395 "Student_1": 6,
396 "Student_3": 7,
397 "Student_4": 8,
398 "Student_7": 9,
399 },
400 "company_4": {
401 "positions": 2,
402 "Student_5": 1,
403 "Student_9": 2,
404 "Student_2": 3,
405 "Student_1": 4,
406 "Student_10": 5,
407 "Student_6": 6,
408 "Student_3": 7,
409 "Student_7": 8,
410 "Student_8": 9,
411 },
412 "company_5": {
413 "positions": 1,
414 "Student_3": 1,
415 "Student_4": 2,
416 "Student_7": 3,
417 "Student_1": 4,
418 "Student_2": 5,
419 "Student_8": 6,
420 },
421 "company_6": {
422 "positions": 2,
423 "Student_3": 1,
424 "Student_7": 2,
425 "Student_5": 3,
426 "Student_10": 4,
427 "Student_2": 5,
428 "Student_1": 6,
429 "Student_4": 7,
430 "Student_9": 8,
431 },
432 "company_7": {
433 "positions": 1,
434 "Student_4": 1,
435 "Student_9": 2,
436 "Student_1": 3,
437 "Student_6": 4,
438 "Student_10": 5,
439 "Student_2": 6,
440 "Student_5": 7,
441 "Student_8": 8,
442 },
443 "company_8": {
444 "positions": 1,
445 "Student_3": 1,
446 "Student_5": 2,
447 "Student_1": 3,
448 "Student_2": 4,
449 "Student_9": 5,
450 "Student_10": 6,
451 },
452 "company_9": {
453 "positions": 1,
454 "Student_7": 1,
455 "Student_10": 2,
456 "Student_1": 3,
457 "Student_2": 4,
458 "Student_3": 5,
459 "Student_8": 6,
460 },
461 }
463 match = Matching(students_preference, employer_preference)
464 result = match.find_best_match()
466 expected = (
467 [],
468 {
469 "company_1": ["Student_1", "Student_2"],
470 "company_5": ["Student_3"],
471 "company_2": ["Student_4"],
472 "company_3": ["Student_8", "Student_6"],
473 "company_6": ["Student_7"],
474 "company_4": ["Student_5"],
475 "company_7": ["Student_9"],
476 "company_9": ["Student_10"],
477 },
478 )
479 assert result == expected
482def test_complex_student_employer_preferences_v4():
483 """Test a complex matching scenario."""
484 students_preference = {
485 "Student_1": ["company_2", "company_3"],
486 "Student_2": ["company_1", "company_4", "company_5"],
487 "Student_3": ["company_1", "company_2", "company_6"],
488 "Student_4": ["company_3", "company_5"],
489 "Student_5": ["company_2", "company_3", "company_7"],
490 "Student_6": ["company_5", "company_8"],
491 "Student_7": ["company_1", "company_4"],
492 "Student_8": ["company_7", "company_9", "company_5"],
493 "Student_9": ["company_1", "company_2"],
494 "Student_10": ["company_8", "company_10", "company_9"],
495 }
497 employer_preference = {
498 "company_1": {
499 "positions": 2,
500 "Student_2": 1,
501 "Student_3": 2,
502 "Student_9": 3,
503 "Student_5": 4,
504 "Student_1": 5,
505 },
506 "company_2": {
507 "positions": 2,
508 "Student_1": 1,
509 "Student_5": 2,
510 "Student_3": 3,
511 "Student_10": 4,
512 "Student_8": 5,
513 "Student_4": 6,
514 },
515 "company_3": {
516 "positions": 1,
517 "Student_4": 1,
518 "Student_1": 2,
519 "Student_2": 3,
520 "Student_9": 4,
521 "Student_8": 5,
522 },
523 "company_4": {
524 "positions": 2,
525 "Student_2": 1,
526 "Student_7": 2,
527 "Student_5": 3,
528 "Student_1": 4,
529 "Student_3": 5,
530 },
531 "company_5": {
532 "positions": 1,
533 "Student_6": 1,
534 "Student_4": 2,
535 "Student_2": 3,
536 "Student_10": 4,
537 },
538 "company_6": {
539 "positions": 1,
540 "Student_3": 1,
541 "Student_1": 2,
542 "Student_4": 3,
543 "Student_9": 4,
544 },
545 "company_7": {
546 "positions": 1,
547 "Student_5": 1,
548 "Student_8": 2,
549 "Student_1": 3,
550 "Student_3": 4,
551 },
552 "company_8": {
553 "positions": 2,
554 "Student_10": 1,
555 "Student_6": 2,
556 "Student_2": 3,
557 "Student_3": 4,
558 },
559 "company_9": {
560 "positions": 1,
561 "Student_2": 1,
562 "Student_4": 2,
563 "Student_1": 3,
564 },
565 "company_10": {
566 "positions": 1,
567 "Student_10": 1,
568 "Student_5": 2,
569 "Student_6": 3,
570 "Student_8": 4,
571 },
572 }
574 match = Matching(students_preference, employer_preference)
575 result = match.find_best_match()
577 expected = (
578 ["Student_9"],
579 {
580 "company_2": ["Student_1", "Student_5"],
581 "company_1": ["Student_2", "Student_3"],
582 "company_3": ["Student_4"],
583 "company_5": ["Student_6"],
584 "company_4": ["Student_7"],
585 "company_7": ["Student_8"],
586 "company_8": ["Student_10"],
587 },
588 )
590 assert result == expected
593def test_large_scale_matching_under_30_seconds():
594 """Tests the matching algorithm with 5000 students and enough employers under 30 seconds."""
595 num_students = 5000
596 num_companies = 1000
597 student_ids = [f"Student_{i+1}" for i in range(num_students)]
598 company_ids = [f"company_{i+1}" for i in range(num_companies)]
600 # Generate random student preferences
601 students_preference = {}
602 for student in student_ids:
603 preferred_companies = random.sample(company_ids, k=random.randint(5, 10))
604 students_preference[student] = preferred_companies
606 # Generate random employer preferences
607 employer_preference = {}
608 for company in company_ids:
609 positions = random.randint(2, 10) # Each company offers 2-10 positions
610 ranked_students = random.sample(student_ids, k=len(student_ids))
611 preference = {student: rank + 1 for rank, student in enumerate(ranked_students)}
612 preference["positions"] = positions
613 employer_preference[company] = preference
615 # Run the matching algorithm and time it
616 match = Matching(students_preference, employer_preference)
618 start_time = time.time()
619 result = match.find_best_match()
620 end_time = time.time()
622 duration = end_time - start_time
623 assert duration < 30, f"Matching took too long: {duration:.2f} seconds"