ttpgen/solution.rs
1// Std library
2use std::collections::{HashMap, HashSet};
3use std::fs::{self, File};
4use std::hash::{Hash};
5use std::io::BufReader;
6
7// External crates
8use indicatif::{ProgressBar, ProgressStyle};
9use log::info;
10use rand::SeedableRng;
11use rand::rngs::StdRng;
12use rand::seq::SliceRandom;
13use serde::{Deserialize, Serialize};
14use serde_json::from_reader;
15
16// Local modules
17use crate::data_set::{Rawdata, Team};
18
19/// Saves any serializable data to a json file.
20///
21/// This function serializes the provided data structure into a json format
22/// and writes it to the specified file path. It works with any type
23/// that implements `serde::Serialize`.
24///
25/// # Arguments
26/// * `data` - A reference to the data to serialize and save.
27/// * `path` - A string slice specifying the file path.
28///
29/// # Returns
30/// A `Result` indicating success (`Ok(())`) or failure (`Err`) with an I/O error.
31///
32/// # Example
33/// ```
34/// use serde::Serialize;
35/// #[derive(Serialize)]
36/// struct Example {
37/// id: u32,
38/// name: String,
39/// }
40///
41/// let data = Example { id: 1, name: "Test".to_string() };
42/// save_to_file(&data, "output/example.json").expect("Failed to save file");
43/// ```
44pub fn save_to_file<T: Serialize>(data: &T, path: &str) -> std::io::Result<()> {
45 let file = File::create(path)?;
46 serde_json::to_writer_pretty(file, data)?;
47 Ok(())
48}
49
50/// Represents a single match/game between two teams.
51///
52/// The `Game` struct stores the home/away status and the opponent's ID.
53///
54/// # Fields
55/// * `home_game` - A boolean indicating if the team is playing at home (`true`) or away (`false`).
56/// * `opponent` - The ID of the opponent team.
57///
58/// # Example
59/// ```
60/// let match_game = Game {
61/// home_game: true,
62/// opponent: 5,
63/// };
64/// println!("Home game: {}, Opponent: {}", match_game.home_game, match_game.opponent);
65/// ```
66#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq, Hash)]
67pub struct Game {
68 pub home_game: bool,
69 pub opponent: i32,
70}
71
72/// Represents a set of generated team permutations along with metadata.
73///
74/// `Permutations` stores multiple random permutations of team IDs,
75/// along with the seed used for generation and the instance name. This is useful
76/// for saving and later reusing or analyzing the generated permutations.
77///
78/// # Fields
79/// * `seed` - The seed used for generating the permutations.
80/// * `instance_name` - The name of the problem instance.
81/// * `permutations` - A vector of vectors, where each inner vector represents one permutation of team IDs.
82///
83/// # Example
84/// ```
85/// let perms = Permutations {
86/// seed: 42,
87/// instance_name: "instance_01".to_string(),
88/// permutations: vec![
89/// vec![0,1,2,3],
90/// vec![3,2,1,0],
91/// ],
92/// };
93/// ```
94#[derive(Serialize)]
95pub struct Permutations {
96 pub seed: u64,
97 pub instance_name: String,
98 pub permutations: Vec<Vec<i32>>,
99}
100
101/// A simple wrapper around `ProgressBar` for logging progress.
102///
103/// # Example
104/// ```
105/// let progress = ProgressBarLog::new(100);
106/// for i in 0..100 {
107/// progress.set_message(&format!("Processing item {}", i));
108/// progress.inc();
109/// }
110/// progress.finish();
111/// ```
112pub struct ProgressBarLog {
113 bar: ProgressBar,
114}
115
116/// A simple wrapper around `ProgressBar` for logging progress.
117///
118/// `ProgressBarLog` provides a convenient interface to create and manipulate a progress bar
119/// with custom styling and logging messages. This is useful for tracking long-running
120/// operations, like generating or evaluating multiple scheduling solutions.
121///
122/// # Example
123/// ```
124/// let progress = ProgressBarLog::new(100);
125/// for i in 0..100 {
126/// progress.set_message(&format!("Processing item {}", i));
127/// progress.inc();
128/// }
129/// progress.finish();
130/// ```
131impl ProgressBarLog {
132 /// Creates a new `ProgressBarLog` with the given total count.
133 ///
134 /// # Arguments
135 /// * `total` - The total number of steps to complete.
136 ///
137 /// # Returns
138 /// A `ProgressBarLog` instance with custom styling.
139 pub fn new(total: u64) -> Self {
140 let bar = ProgressBar::new(total);
141 bar.set_style(
142 ProgressStyle::default_bar()
143 .template(
144 " [{elapsed_precise}] {bar:40.green/white} {pos}/{len} ({percent}%) | {msg}",
145 )
146 .progress_chars("%>="),
147 );
148 Self { bar }
149 }
150
151 /// Increments the progress bar by one step.
152 pub fn inc(&self) {
153 self.bar.inc(1);
154 }
155
156 #[allow(dead_code)]
157 /// Finishes the progress bar, marking it as complete.
158 pub fn finish(&self) {
159 self.bar.finish();
160 }
161
162 #[allow(dead_code)]
163 /// Sets a custom message to display alongside the progress bar.
164 ///
165 /// # Arguments
166 /// * `msg` - The message string to display.
167 pub fn set_message(&self, msg: &str) {
168 self.bar.set_message(msg);
169 }
170}
171
172/// Represents a solution for the scheduling problem.
173///
174/// Each `Solution` contains an `id` identifying the solution,
175/// and a `solution` matrix where `solution[slot][team]`
176/// stores a `Game` indicating the opponent and if the game is home or away.
177///
178/// # Fields
179/// * `id` - A unique identifier for the solution.
180/// * `solution` - A 2D vector of `Game` instances representing the schedule matrix.
181///
182/// # Example
183/// ```
184/// let solution = Solution {
185/// id: 1,
186/// solution: vec![vec![Game { home_game: true, opponent: 2 }]],
187/// };
188/// println!("Solution ID: {}", solution.id);
189/// ```
190#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq, Hash)]
191pub struct Solution {
192 pub id: i32,
193 pub solution: Vec<Vec<Game>>,
194}
195
196impl Solution {
197
198 /// Creates a new, empty `Solution` instance initialized with default game values.
199 ///
200 /// This function constructs a solution matrix where each slot and team position
201 /// is filled with a `Game`:
202 /// - `home_game` is set to `false`
203 /// - `opponent` is set to `-1` (indicating: no opponent assigned yet)
204 ///
205 /// # Arguments
206 /// * `data` - A reference to the `Rawdata` structure containing teams and slots
207 /// information. The size of the solution matrix is derived from:
208 /// - `data.teams.len()`
209 /// - `data.slots.len()`
210 ///
211 /// # Returns
212 /// A `Solution` struct with:
213 /// - `id` initialized to `-1`
214 /// - `solution` initialized as a `slots x teams` matrix filled with default games.
215 ///
216 /// # Example
217 /// ```
218 /// let data = Rawdata::generate_example();
219 /// let solution = Solution::new(&data);
220 /// assert_eq!(solution.solution.len(), data.slots.len());
221 /// assert_eq!(solution.solution[0].len(), data.teams.len());
222 /// ```
223 pub fn new(data: &Rawdata) -> Solution {
224 Solution {
225 id: -1,
226 solution: vec![
227 vec![
228 Game {
229 home_game: false,
230 opponent: -1
231 };
232 data.teams.len()
233 ];
234 data.slots.len()
235 ],
236 }
237 }
238
239 /// Generates a traveling distance matrix based on the distance in `Rawdata`.
240 ///
241 /// This function constructs a 2D matrix where each cell `(i, j)` represents the
242 /// distance traveled from team `i` to team `j`. The matrix is initialized with
243 /// zeros and populated using the `distances` list contained inside `Rawdata`.
244 ///
245 /// # Arguments
246 /// * `data` - A reference to the `Rawdata` structure containing team distance
247 /// relationships. `data.distances` is expected to list distances between pairs
248 /// of teams.
249 ///
250 /// # Returns
251 /// A 2D vector (`Vec<Vec<i32>>`) where:
252 /// - The row index corresponds to the origin team
253 /// - The column index corresponds to the destination team
254 /// - Each cell contains the travel distance between them
255 ///
256 /// # Example
257 /// ```
258 /// let data = Rawdata::generate_example();
259 /// let distance_matrix = generate_traveling_distance_matrix(&data);
260 ///
261 /// println!("Distance: {}", distance_matrix[0][2]);
262 /// ```
263 pub fn generate_traveling_distance_matrix(data: &Rawdata) -> Vec<Vec<i32>> {
264 let mut traveling_distance_matrix = vec![vec![0i32; data.teams.len()]; data.teams.len()];
265
266 for distance in &data.distances {
267 traveling_distance_matrix[distance.team1 as usize][distance.team2 as usize] =
268 distance.dist;
269 }
270
271 traveling_distance_matrix
272 }
273
274 #[allow(dead_code)]
275 /// Checks if a list of `Solution` objects contains duplicates.
276 ///
277 /// This function iterates over all solutions and attempts to insert each one into a
278 /// `HashSet`. If insertion fails for any solution, it means a duplicate exists,
279 /// and the function returns `true`.
280 ///
281 /// # Arguments
282 /// * `solutions` - A reference to a vector of `Solution` instances to be checked.
283 ///
284 /// # Returns
285 /// * `true` if one or more duplicates are found.
286 /// * `false` if all solutions are unique.
287 ///
288 /// # Requirements
289 /// The `Solution` type must implement:
290 /// - `Hash`
291 /// - `Eq`
292 ///
293 /// # Example
294 /// ```
295 /// let solutions = load_solutions("output/solutions/");
296 /// if has_duplicate_solutions(&solutions) {
297 /// println!("Duplicate.");
298 /// } else {
299 /// println!("No duplicates.");
300 /// }
301 /// ```
302 pub fn has_duplicate_solutions(solutions: &Vec<Solution>) -> bool {
303 let mut seen = HashSet::new();
304
305 for sol in solutions {
306 if !seen.insert(sol) {
307 return true;
308 }
309 }
310 false
311 }
312
313 #[allow(dead_code)]
314 /// Loads all solution files from a directory and returns them as a vector of `Solution`.
315 ///
316 /// This function scans the directory for files whose names follow the pattern
317 /// `solutions_*.json`. Each file is opened, deserialized into a `Solution`,
318 /// and collected into a vector. After loading, the solutions are sorted in ascending
319 /// order based on their `id` field.
320 ///
321 /// # Arguments
322 /// * `path` - A string slice representing the directory to search for solution files.
323 ///
324 /// # Returns
325 /// A vector of `Solution` objects loaded from the directory.
326 ///
327 /// # Panics
328 /// This function will panic if:
329 /// - The directory cannot be read.
330 /// - A file cannot be opened.
331 /// - A JSON file cannot be deserialized into a `Solution`.
332 ///
333 /// # Example
334 /// ```
335 /// let solutions = load_solutions("output/solutions/");
336 /// println!("Loaded {} solutions", solutions.len());
337 ///
338 /// if let Some(first) = solutions.first() {
339 /// println!("First solution ID: {}", first.id);
340 /// }
341 /// ```
342 pub fn load_solutions(path: &str) -> Vec<Solution> {
343 let mut all_solutions = Vec::new();
344
345 let entries = fs::read_dir(path).expect("Error opening directory");
346
347 for entry in entries {
348 let entry = entry.expect("Error at path");
349 let path = entry.path();
350
351 if path.is_file() {
352 if let Some(filename) = path.file_name().and_then(|n| n.to_str()) {
353 if filename.starts_with("solutions_") && filename.ends_with(".json") {
354 let file = File::open(&path).expect("Error opening file");
355 let reader = BufReader::new(file);
356
357 let solution: Solution =
358 from_reader(reader).expect("Error deserializing JSON");
359
360 all_solutions.push(solution);
361 }
362 }
363 }
364 }
365
366 all_solutions.sort_by_key(|s| s.id);
367 all_solutions
368 }
369
370 #[allow(dead_code)]
371 /// Calculates the total traveling distances for a list of solutions.
372 ///
373 /// This function iterates over each solution, evaluates it using the provided
374 /// traveling distance matrix, and collects the total distances into a vector.
375 ///
376 /// # Arguments
377 /// * `solutions` - A vector of `Solution` instances to evaluate.
378 /// * `data` - A reference to the `Rawdata` containing teams and constraints.
379 /// * `traveling_distance_matrix` - A reference to a 2D vector where `matrix[i][j]` represents
380 /// the distance from team `i` to team `j`.
381 ///
382 /// # Returns
383 /// A vector of `i128` where each element represents the total traveling distance
384 /// of the corresponding solution.
385 ///
386 /// # Example
387 /// ```
388 /// let data = Rawdata::generate_example();
389 /// let distance_matrix = vec![vec![0,5,7], vec![5,0,3], vec![7,3,0]];
390 /// let solutions = vec![Solution::generate_example(), Solution::generate_example()];
391 /// let distances = generate_distances(solutions, &data, &distance_matrix);
392 /// println!("All distances: {:?}", distances);
393 /// ```
394 pub fn generate_distances(
395 solutions: Vec<Solution>,
396 data: &Rawdata,
397 traveling_distance_matrix: &Vec<Vec<i32>>,
398 ) -> Vec<i128> {
399 let mut all_distances: Vec<i128> = Vec::new();
400
401 for solution in solutions {
402 let (distance, _, _, _) =
403 Solution::evaluate_solution(data, traveling_distance_matrix, &solution);
404
405 all_distances.push(distance as i128);
406 }
407
408 all_distances
409 }
410
411 /// Logs a solution's schedule and its evaluation metrics.
412 ///
413 /// This function prints a representation of the solution,
414 /// including the total traveling distance, capacity, round-robin and separation
415 /// constraint violations, It also returns the total distance.
416 ///
417 /// # Arguments
418 /// * `solution` - A reference to the `Solution` to log.
419 /// * `data` - A reference to the `Rawdata` containing teams and constraints.
420 /// * `traveling_distance_matrix` - A reference to a 2D vector where `matrix[i][j]` represents
421 /// the distance from team `i` to team `j`.
422 ///
423 /// # Returns
424 /// The total traveling distance (`i32`) of the solution.
425 ///
426 /// # Example
427 /// ```
428 /// let data = Rawdata::generate_example();
429 /// let solution = Solution::generate_example();
430 /// let distance = Solution::log_solution(&solution, &data, &vec![vec![0,5,7], vec![5,0,3], vec![7,3,0]]);
431 /// println!("Total distance: {}", distance);
432 /// ```
433 fn log_solution(
434 solution: &Solution,
435 data: &Rawdata,
436 traveling_distance_matrix: &Vec<Vec<i32>>,
437 ) -> i32 {
438 let (distance, cap_constraints, sep_constraints, round_robin_respect) =
439 Solution::evaluate_solution(data, traveling_distance_matrix, solution);
440
441 let solution_str = Solution::solution_to_string(solution, data);
442 info!(
443 "Solution:\n{}\nDistance: {}\nCapacity Constraints: {}\nSeparation Constraints: {}\nRound Robin Respect: {}",
444 solution_str, distance, cap_constraints, sep_constraints, round_robin_respect
445 );
446
447 distance
448 }
449
450 /// Generates a complete solution for a given team permutation using Florian's method.
451 ///
452 /// This function clones the input `Rawdata`, applies the given team permutation, and
453 /// generates a round-robin schedule using `generate_florian_solution`. The resulting
454 /// solution is assigned the provided ID.
455 ///
456 /// # Arguments
457 /// * `data` - A reference to the `Rawdata` containing the original teams, traveling_distance_matrix and constraints.
458 /// * `perm` - A reference to a vector of `Team` representing the ordered permutation of teams.
459 /// * `fixed_team` - The index of the team to remain fixed during the method rotations.
460 /// * `upward` - If `true`, the home/away pattern follows an upward direction, otherwise downward.
461 /// * `id` - The unique ID to assign to the generated solution.
462 ///
463 /// # Returns
464 /// A `Solution` struct representing the generated schedule with the specified ID.
465 ///
466 /// # Example
467 /// ```
468 /// let data = Rawdata::generate_example();
469 /// let perm = data.teams.clone();
470 /// let solution = generate_solution(&data, &perm, 0, true, 1);
471 /// println!("{}", solution_to_string(&solution, &data));
472 /// ```
473 fn generate_solution(
474 data: &Rawdata,
475 perm: &Vec<Team>,
476 fixed_team: usize,
477 upward: bool,
478 id: i32,
479 ) -> Solution {
480 let mut temporary_data = data.clone();
481 temporary_data.teams = perm.clone();
482 let mut solution = Solution::generate_florian_solution(&temporary_data, fixed_team, upward);
483 solution.id = id;
484
485 solution
486 }
487
488 /// Generates a set of unique random permutations of the team IDs.
489 ///
490 /// This function takes the list of teams from `Rawdata` and generates the requested number of
491 /// unique permutations. Each permutation is randomized and stored in a `Vec<i32>`.
492 ///
493 /// # Arguments
494 /// * `data` - A reference to the `Rawdata` struct containing the list of teams.
495 /// * `number_permutation` - A reference to an `i32` specifying how many unique permutations
496 /// should be generated.
497 ///
498 /// # Returns
499 /// A vector of vectors (`Vec<Vec<i32>>`), where each inner vector is a unique permutation
500 /// of the team IDs.
501 ///
502 /// # Example
503 /// ```
504 /// let data = Rawdata::generate_example();
505 /// let permutations = generate_random_permutations(&data, &5);
506 /// ```
507 pub fn generate_random_permutations(
508 data: &Rawdata,
509 number_permutations: i32,
510 seed: u64,
511 path: &str, save: bool,
512 ) -> Vec<Vec<i32>> {
513 let team_ids: Vec<i32> = data.teams.iter().map(|t| t.id).collect();
514
515 let mut rng = StdRng::seed_from_u64(seed);
516 let mut permutations: HashSet<Vec<i32>> = HashSet::new();
517
518 while permutations.len() < number_permutations as usize {
519 let mut perm = team_ids.clone();
520 perm.shuffle(&mut rng);
521 permutations.insert(perm);
522 }
523
524 let vec_perm: Vec<Vec<i32>> = permutations.into_iter().collect();
525
526 if save {
527 let permutations_to_save = Permutations {
528 seed,
529 instance_name: data.instance_name.clone(),
530 permutations: vec_perm.clone(),
531 };
532 save_to_file(&permutations_to_save, &format!("{}/permutation.json", path)).unwrap();
533 }
534
535 vec_perm
536 }
537
538 /// Generates all possible solutions for a given team permutation using Florian's method,
539 /// evaluates their distances, and optionally saves them to disk.
540 ///
541 /// This function iterates over all possible combinations of fixed teams and home/away patterns
542 /// (upward/downward) for a given permutation of teams. Each generated solution is evaluated
543 /// using the traveling distance matrix, logged, and optionally saved as JSON.
544 ///
545 /// # Arguments
546 /// * `data` - A reference to the `Rawdata` containing teams, slots, and constraints.
547 /// * `traveling_distance_matrix` - A reference to a 2D vector where `matrix[i][j]` represents
548 /// the distance from team `i` to team `j`.
549 /// * `permutation` - A vector of vect of team IDs representing the order in which teams are considered.
550 /// * `path` - A string slice representing the directory path where solutions will be saved if `SAVE_ENABLED` is true.
551 ///
552 /// # Returns
553 /// A tuple `(solutions, all_distances)`:
554 /// - `solutions` (Vec<Solution>): all generated solution matrices.
555 /// - `all_distances` (Vec<i128>): total traveling distance for each solution.
556 ///
557 /// # Panics
558 /// This function may panic if saving a solution to file fails.
559 ///
560 /// # Example
561 /// ```
562 /// let data = Rawdata::generate_example();
563 /// let distance_matrix = vec![vec![0,5,7], vec![5,0,3], vec![7,3,0]];
564 /// let permutation = vec![0,1,2];
565 /// let (solutions, distances) = generate_all_solutions(&data, &distance_matrix, permutation, "output");
566 /// println!("Solutions length {}", solutions.len());
567 /// println!("Distances: {:?}", distances);
568 /// ```
569 pub fn generate_all_solutions(
570 data: &Rawdata,
571 traveling_distance_matrix: &Vec<Vec<i32>>,
572 permutation: Vec<Vec<i32>>,
573 path: &str,
574 save: bool,
575 ) -> (Vec<Solution>, Vec<i128>) {
576 let mut solutions: Vec<Solution> = Vec::new();
577 let mut all_distances: Vec<i128> = Vec::new();
578
579 let mut id_solution = 0;
580
581 let total_perms = 2 * data.teams.len() * permutation.len();
582
583 // Create progress bar
584 let progress = ProgressBarLog::new(total_perms as u64);
585
586 for team in permutation {
587 let teams_ordered: Vec<Team> = team
588 .iter()
589 .filter_map(|id| data.teams.iter().find(|t| t.id == *id))
590 .cloned()
591 .collect();
592
593 // Log the permutation
594 info!("Permutation: {:?}", team);
595
596 for direction in [true, false] {
597 for fixed_team in 0..data.teams.len() {
598 id_solution = id_solution + 1;
599
600 // Generate solution
601 let temporary_solution = Solution::generate_solution(
602 &data,
603 &teams_ordered,
604 fixed_team,
605 direction,
606 id_solution,
607 );
608
609 // Log solution details
610 let distance_solution = Solution::log_solution(
611 &temporary_solution,
612 &data,
613 &traveling_distance_matrix,
614 );
615
616 // Store the solution and the distance
617 solutions.push(temporary_solution.clone());
618 all_distances.push(distance_solution as i128);
619
620 // Save to file
621 if save {
622 save_to_file(
623 &temporary_solution,
624 &format!("{}/solution_{}.json", path, id_solution),
625 )
626 .unwrap();
627 }
628
629 // Update bar inc
630 progress.inc();
631 }
632 }
633 }
634
635 (solutions, all_distances)
636 }
637
638 /// Generates a schedule using Florian's method construction.
639 ///
640 /// This function constructs a round-robin schedule fixing a team. The `upward`
641 /// flag determines the pattern of home/away assignments for the first match
642 /// of each pairing.
643 ///
644 /// # Arguments
645 /// * `data` - A reference to `Rawdata` containing team information.
646 /// * `fixed_team` - The index of the team to remain fixed during rotations.
647 /// * `upward` - If `true`, the home team assignment follows an upward pattern; otherwise downward.
648 ///
649 /// # Returns
650 /// A `Solution` struct with the scheduled matches for all slots and teams.
651 ///
652 /// # Example
653 /// ```
654 /// let data = Rawdata::generate_example();
655 /// let solution = generate_florian_solution(&data, 0, true);
656 /// println!("{}", solution_to_string(&solution, &data));
657 /// ```
658 pub fn generate_florian_solution(data: &Rawdata, fixed_team: usize, upward: bool) -> Solution {
659 info!(
660 "Starting Florian's construction for {} teams | Fixed team: {} | Pattern: {}",
661 data.teams.len(),
662 fixed_team,
663 if upward {
664 "Upward direction"
665 } else {
666 "Downward direction"
667 }
668 );
669
670 let mut solution_matrix = Solution::new(&data);
671
672 let mut teams: Vec<usize> = data
673 .teams
674 .iter()
675 .enumerate()
676 .map(|(_, team)| team.id as usize)
677 .collect();
678
679 let fixed_team = teams.remove(fixed_team);
680 teams.push(fixed_team);
681
682 for round in 0..2 * (data.teams.len() - 1) {
683 info!("Round: {}", round);
684 info!("Teams before rotation: {:?}", teams);
685 for i in 0..(data.teams.len() / 2) {
686 let team_a = teams[i];
687 let team_b = teams[data.teams.len() - 1 - i];
688 let home_first = (round % 2 == 0) == upward;
689
690 if home_first {
691 solution_matrix.solution[round][team_a] = Game {
692 home_game: true,
693 opponent: team_b as i32,
694 };
695 solution_matrix.solution[round][team_b] = Game {
696 home_game: false,
697 opponent: team_a as i32,
698 };
699 } else {
700 solution_matrix.solution[round][team_a] = Game {
701 home_game: false,
702 opponent: team_b as i32,
703 };
704 solution_matrix.solution[round][team_b] = Game {
705 home_game: true,
706 opponent: team_a as i32,
707 };
708 }
709
710 info!(
711 "Pairing: Team {} vs Team {} | {} is home",
712 team_a,
713 team_b,
714 if home_first { team_a } else { team_b }
715 );
716 }
717
718 let fixed_team = teams.remove(teams.len() - 1);
719 teams.rotate_right(1);
720 teams.push(fixed_team);
721 info!("Teams after rotation: {:?}", teams);
722 }
723
724 info!(
725 "Final solution for {} teams | Fixed team: {} | Pattern: {}",
726 data.teams.len(),
727 fixed_team,
728 if upward {
729 "Upward direction"
730 } else {
731 "Downward direction"
732 }
733 );
734
735 solution_matrix
736 }
737
738 /// Converts a `Solution` matrix into a formatted string representation.
739 ///
740 /// This function generates a human-readable string showing the schedule of all teams
741 /// for each slot. Each cell shows the opponent ID followed by `H` for a home game or
742 /// `A` for an away game. The output also includes team names and IDs as headers.
743 ///
744 /// # Arguments
745 /// * `solution_matrix` - A reference to the `Solution` containing the schedule.
746 /// * `data` - A reference to the `Rawdata` struct containing team information.
747 ///
748 /// # Returns
749 /// A `String` representing the formatted solution.
750 ///
751 /// # Example
752 /// ```
753 /// let data = Rawdata::generate_example();
754 /// let solution = Solution::generate_example();
755 /// let output_str = solution_to_string(&solution, &data);
756 /// println!("{}", output_str);
757 /// ```
758 /// Example output:
759 /// ```text
760 /// Id: 1
761 /// ATL:0 NYM:1 PHI:2
762 /// Slot:0 1H 2A 0H
763 /// Slot:1 2H 0A 1H
764 /// ```
765 pub fn solution_to_string(solution_matrix: &Solution, data: &Rawdata) -> String {
766 let mut output = String::new();
767 output.push_str(&format!("Id: {}\n", solution_matrix.id));
768
769 output.push_str(&format!("{:>8}", ""));
770 for team_id in 0..data.teams.len() {
771 output.push_str(&format!(
772 "{:>8}",
773 format!("{}:{}", data.teams[team_id].name, data.teams[team_id].id)
774 ));
775 }
776 output.push('\n');
777
778 for (slot_id, row) in solution_matrix.solution.iter().enumerate() {
779 output.push_str(&format!("{:>8}", format!("Slot:{}", slot_id)));
780 for game in row {
781 output.push_str(&format!(
782 "{:>8}",
783 format!(
784 "{}{}",
785 game.opponent,
786 if game.home_game { "H" } else { "A" }
787 )
788 ));
789 }
790 output.push('\n');
791 }
792
793 output
794 }
795
796 /// Checks all constraints for a solution, including capacity, separation, and round-robin.
797 ///
798 /// 1. **Capacity constraints**: Verifies for each team, within the specified interval (`c_intp`)
799 /// of consecutive slots, the number of home or away games falls within
800 /// the minimum (`c_min`) and maximum (`c_max`) allowed.
801 ///
802 /// 2. **Separation constraints**: Ensures that matches between two teams respect the minimum and maximum
803 /// separation distances defined by each constraint.
804 ///
805 /// 3. **Round-robin constraints**: Checks that no pair of teams plays against each other more than 4 times (2 pairs of game).
806 ///
807 /// # Arguments
808 /// * `data` - A reference to the `Rawdata` containing teams and constraints.
809 /// * `solution_matrix` - A reference to the `Solution` with the scheduled games.
810 ///
811 /// # Returns
812 /// A tuple `(capacity_violations, separation_violations, round_robin_respected)`
813 /// - `capacity_violations` (i32): total number of capacity constraint violations.
814 /// - `separation_violations` (i32): total number of separation constraint violations.
815 /// - `round_robin_respected` (bool): true if all pairs of teams respect the round-robin.
816 ///
817 /// # Example
818 /// ```
819 /// let data = Rawdata::generate_example();
820 /// let solution = Solution::generate_example();
821 /// let (cap_viol, sep_viol, rr_ok) = check_constraints(&data, &solution);
822 /// println!("Capacity violations: {}, Separation violations: {}, Round-robin ok: {}", cap_viol, sep_viol, rr_ok);
823 /// ```
824 fn check_constraints(data: &Rawdata, solution_matrix: &Solution) -> (i32, i32, bool) {
825 let num_slots = solution_matrix.solution.len();
826 let num_teams = solution_matrix.solution[0].len();
827 let mut capacity_constraints = 0;
828 let mut separation_constraints = 0;
829 let mut round_robin_respect = true;
830
831 // Capacity Constraints:
832
833 for constraint in &data.capacity_constraints {
834 for team in 0..num_teams {
835 for start_slot in 0..=num_slots - constraint.c_intp as usize {
836 let count = solution_matrix.solution
837 [start_slot..start_slot + constraint.c_intp as usize]
838 .iter()
839 .filter(|slot| {
840 let game = &slot[team];
841 match constraint.c_mode1 {
842 'A' => game.home_game,
843 'H' => !game.home_game,
844 _ => false,
845 }
846 })
847 .count();
848
849 if count < constraint.c_min as usize || count > constraint.c_max as usize {
850 capacity_constraints += 1;
851 }
852 }
853 }
854 }
855
856 // Separation Constraints:
857
858 for constraint in &data.separation_constraints {
859 for team in 0..num_teams {
860 let mut last_slot_vs: Vec<Option<usize>> = vec![None; num_teams];
861
862 for slot in 0..num_slots {
863 let game = &solution_matrix.solution[slot][team];
864 let opponent = game.opponent as usize;
865
866 if let Some(last) = last_slot_vs[opponent] {
867 let distance = slot - last;
868
869 if distance <= constraint.c_min as usize
870 || distance > constraint.c_max as usize
871 {
872 separation_constraints += 1;
873 }
874 }
875
876 last_slot_vs[opponent] = Some(slot);
877 }
878 }
879 }
880
881 // Round-robin constraints
882
883 let mut match_count: HashMap<(usize, usize), i32> = HashMap::new();
884
885 for slot in 0..num_slots {
886 for home_team in 0..num_teams {
887 let away_team = solution_matrix.solution[slot][home_team].opponent;
888
889 let key = if home_team < away_team as usize {
890 (home_team, away_team as usize)
891 } else {
892 (away_team as usize, home_team)
893 };
894
895 *match_count.entry(key).or_insert(0) += 1;
896 }
897 }
898
899 for ((_, _), count) in &match_count {
900 if *count > 4 {
901 round_robin_respect = false;
902 }
903 }
904
905 (
906 capacity_constraints,
907 separation_constraints,
908 round_robin_respect,
909 )
910 }
911
912 /// Calculates the total traveling distance for all teams in a given solution.
913 ///
914 /// This function iterates over all teams and all slots in the solution. For each team,
915 /// it tracks the current location and adds the distance to the next game location.
916 /// Home games do not require traveling, while away games add the distance to the opponent's location.
917 ///
918 /// # Arguments
919 /// * `traveling_distance_matrix` - A reference to a 2D vector where `matrix[i][j]` represents
920 /// the distance from team `i` to team `j`.
921 /// * `solution_matrix` - A reference to the `Solution` containing the schedule of games
922 /// for all slots and teams.
923 ///
924 /// # Returns
925 /// The total traveling distance for all teams (i32).
926 ///
927 /// # Example
928 /// ```
929 /// let distance_matrix = vec![vec![0, 5, 7], vec![5, 0, 3], vec![7, 3, 0]];
930 /// let total = evaluate_objective(&distance_matrix, &solution);
931 /// println!("Total traveling distance: {}", total);
932 /// ```
933 fn evaluate_objective(
934 traveling_distance_matrix: &Vec<Vec<i32>>,
935 solution_matrix: &Solution,
936 ) -> i32 {
937 let num_slots = solution_matrix.solution.len();
938 let num_teams = solution_matrix.solution[0].len();
939 let mut total_distance = 0;
940
941 for team in 0..num_teams {
942 let mut current_location = team;
943 for slot in 0..num_slots {
944 let game = &solution_matrix.solution[slot][team];
945 let next_location = if game.home_game {
946 team
947 } else {
948 game.opponent as usize
949 };
950 total_distance += traveling_distance_matrix[current_location][next_location];
951 current_location = next_location;
952 }
953 }
954
955 total_distance
956 }
957
958 /// Evaluates a given solution by calculating the total traveling distance and checking constraints.
959 ///
960 /// This function combines the distance evaluation and constraint checks for a solution.
961 /// It returns the total traveling distance, the total violations of capacity constraints,
962 /// the total violations of separation constraints, and a boolean indicating if the
963 /// round-robin structure is respected.
964 ///
965 /// # Arguments
966 /// * `data` - A reference to the `Rawdata` struct containing teams, slots, and constraints.
967 /// * `traveling_distance_matrix` - A reference to a 2D vector where `matrix[i][j]` represents
968 /// the distance from team `i` to team `j`.
969 /// * `solution_matrix` - A reference to the `Solution` containing the schedule of games
970 /// for all slots and teams.
971 ///
972 /// # Returns
973 /// A tuple `(total_distance, capacity_violations, separation_violations, round_robin_respected)`
974 /// - `total_distance` (i32): total traveling distance for all teams.
975 /// - `capacity_violations` (i32): total penalty for capacity constraints violations.
976 /// - `separation_violations` (i32): total penalty for separation constraints violations.
977 /// - `round_robin_respected` (bool): true if the round-robin structure is respected.
978 ///
979 /// # Example
980 /// ```
981 /// let data = Rawdata::generate_example();
982 /// let distance_matrix = vec![vec![0,5,7], vec![5,0,3], vec![7,3,0]];
983 /// let solution = Solution::generate_example();
984 /// let (total_distance, cap_viol, sep_viol, rr_ok) = evaluate_solution(&data, &distance_matrix, &solution);
985 /// ```
986 pub fn evaluate_solution(
987 data: &Rawdata,
988 traveling_distance_matrix: &Vec<Vec<i32>>,
989 solution_matrix: &Solution,
990 ) -> (i32, i32, i32, bool) {
991 let (cap_constraints, sep_constraints, round_robin_respect) =
992 Self::check_constraints(data, solution_matrix);
993 let result = Self::evaluate_objective(traveling_distance_matrix, solution_matrix);
994 (
995 result,
996 cap_constraints,
997 sep_constraints,
998 round_robin_respect,
999 )
1000 }
1001}