rustsat_tools/encodings/
assignment.rs

1//! # Shared Assignment Problem Encoding Tooling
2//!
3//! - Data types
4//! - Input parser
5
6use std::io;
7
8/// An instance of the multi-objective assignment problem
9#[derive(Clone, PartialEq, Eq)]
10pub struct Assignment {
11    pub(crate) n_tasks: usize,
12    pub(crate) n_objs: usize,
13    pub(crate) costs: Vec<usize>,
14}
15
16impl Assignment {
17    fn empty(n_tasks: usize, n_objs: usize) -> Self {
18        Self {
19            n_tasks,
20            n_objs,
21            costs: vec![0; n_objs * n_tasks * n_tasks],
22        }
23    }
24
25    pub fn from_file(reader: impl io::BufRead) -> anyhow::Result<Self> {
26        parsing::parse_moolib(reader)
27    }
28
29    pub fn idx(&self, task: usize, agent: usize, obj: usize) -> usize {
30        debug_assert!(task < self.n_tasks);
31        debug_assert!(agent < self.n_tasks);
32        debug_assert!(obj < self.n_objs);
33        obj * self.n_tasks * self.n_tasks + task * self.n_tasks + agent
34    }
35
36    pub fn cost(&self, task: usize, agent: usize, obj: usize) -> usize {
37        self.costs[self.idx(task, agent, obj)]
38    }
39
40    pub fn cost_mut(&mut self, task: usize, agent: usize, obj: usize) -> &mut usize {
41        let idx = self.idx(task, agent, obj);
42        self.costs.get_mut(idx).unwrap()
43    }
44}
45
46mod parsing {
47    use std::io;
48
49    use anyhow::Context;
50    use nom::character::complete::u32;
51
52    use crate::parsing::{callback_list, single_value};
53
54    macro_rules! next_non_comment_line {
55        ($reader:expr) => {
56            'block: {
57                let mut buf = String::new();
58                while $reader.read_line(&mut buf)? > 0 {
59                    if !buf.trim_start().starts_with('#') && !buf.trim().is_empty() {
60                        break 'block Some(buf);
61                    }
62                    buf.clear();
63                }
64                None
65            }
66        };
67    }
68
69    pub fn parse_moolib(mut reader: impl io::BufRead) -> anyhow::Result<super::Assignment> {
70        let line = next_non_comment_line!(reader)
71            .context("file ended before number of objectives line")?;
72        let (_, n_objs) = single_value(u32, "#")(&line)
73            .map_err(|e| e.to_owned())
74            .with_context(|| format!("failed to parse number of objectives line '{line}'"))?;
75        let line =
76            next_non_comment_line!(reader).context("file ended before number of tasks line")?;
77        let (_, n_tasks) = single_value(u32, "#")(&line)
78            .map_err(|e| e.to_owned())
79            .with_context(|| format!("failed to parse number of tasks line '{line}'"))?;
80        let mut inst = super::Assignment::empty(n_tasks as usize, n_objs as usize);
81        let mut buf = String::new();
82        let mut depth = 0;
83        let mut obj_idx = 0;
84        let mut task_idx = 0;
85        while reader.read_line(&mut buf)? > 0 {
86            let mut remain = buf.trim_start();
87            loop {
88                if remain.starts_with('[') && depth < 2 {
89                    depth += 1;
90                    remain = &remain[1..];
91                }
92                if remain.starts_with(']') {
93                    depth -= 1;
94                    if depth == 1 {
95                        task_idx = 0;
96                    }
97                    remain = &remain[1..];
98                }
99                if remain.starts_with(',') {
100                    match depth {
101                        1 => obj_idx += 1,
102                        2 => task_idx += 1,
103                        _ => unreachable!(),
104                    };
105                    remain = &remain[1..];
106                }
107                if remain.starts_with('#') || remain.trim().is_empty() {
108                    break;
109                }
110                if depth == 2 {
111                    let mut agent_idx = 0;
112                    remain = callback_list(remain.trim_start(), u32, |value| {
113                        anyhow::ensure!(obj_idx < n_objs, "too many objectives");
114                        anyhow::ensure!(task_idx < n_tasks, "too many tasks");
115                        anyhow::ensure!(agent_idx < n_tasks, "too many agents");
116                        *inst.cost_mut(task_idx as usize, agent_idx as usize, obj_idx as usize) =
117                            value as usize;
118                        agent_idx += 1;
119                        Ok(())
120                    })?;
121                }
122            }
123            buf.clear();
124        }
125        anyhow::ensure!(
126            obj_idx + 1 == n_objs,
127            "number of objectives does not match up"
128        );
129        Ok(inst)
130    }
131
132    #[cfg(test)]
133    mod tests {
134        use std::{fs::File, io::BufReader};
135
136        #[test]
137        fn moolib() {
138            let manifest = std::env::var("CARGO_MANIFEST_DIR").unwrap();
139            let reader = BufReader::new(
140                File::open(format!("{manifest}/data/AP_p-3_n-5_ins-1.dat")).unwrap(),
141            );
142            super::parse_moolib(reader).unwrap();
143        }
144    }
145}
rustsat_tools/encodings/assignment.rs

rustsat_tools/encodings/
assignment.rs
