problemreductions/models/set/
rooted_tree_storage_assignment.rs

1//! Rooted Tree Storage Assignment problem implementation.
2
3use crate::registry::{FieldInfo, ProblemSchemaEntry};
4use crate::traits::Problem;
5use serde::{Deserialize, Serialize};
6use std::collections::HashSet;
7
8inventory::submit! {
9    ProblemSchemaEntry {
10        name: "RootedTreeStorageAssignment",
11        display_name: "Rooted Tree Storage Assignment",
12        aliases: &[],
13        dimensions: &[],
14        category: crate::registry::ProblemCategory::Set,
15        module_path: module_path!(),
16        description: "Does there exist a rooted tree whose subset path extensions cost at most K?",
17        fields: &[
18            FieldInfo { name: "universe_size", type_name: "usize", description: "Size of the ground set X" },
19            FieldInfo { name: "subsets", type_name: "Vec<Vec<usize>>", description: "Collection of subsets of X" },
20            FieldInfo { name: "bound", type_name: "i64", description: "Upper bound K on the total extension cost" },
21        ],
22    }
23}
24
25#[derive(Debug, Clone, Serialize, Deserialize)]
26#[serde(try_from = "RootedTreeStorageAssignmentDef")]
27pub struct RootedTreeStorageAssignment {
28    universe_size: usize,
29    subsets: Vec<Vec<usize>>,
30    bound: i64,
31}
32
33#[derive(Debug, Deserialize)]
34struct RootedTreeStorageAssignmentDef {
35    universe_size: usize,
36    subsets: Vec<Vec<usize>>,
37    bound: i64,
38}
39
40impl RootedTreeStorageAssignment {
41    pub fn new(universe_size: usize, subsets: Vec<Vec<usize>>, bound: i64) -> Self {
42        Self::try_new(universe_size, subsets, bound).unwrap_or_else(|err| panic!("{err}"))
43    }
44
45    pub fn try_new(
46        universe_size: usize,
47        subsets: Vec<Vec<usize>>,
48        bound: i64,
49    ) -> Result<Self, crate::registry::ConstructionError> {
50        let subsets = subsets
51            .into_iter()
52            .enumerate()
53            .map(|(subset_index, mut subset)| {
54                let mut seen = HashSet::with_capacity(subset.len());
55                for &element in &subset {
56                    if element >= universe_size {
57                        return Err::<Vec<usize>, crate::registry::ConstructionError>(format!(
58                            "subset {subset_index} contains element {element} outside universe of size {universe_size}"
59                        ).into());
60                    }
61                    if !seen.insert(element) {
62                        return Err::<Vec<usize>, crate::registry::ConstructionError>(format!(
63                            "subset {subset_index} contains duplicate element {element}"
64                        ).into());
65                    }
66                }
67                subset.sort_unstable();
68                Ok(subset)
69            })
70            .collect::<Result<Vec<_>, _>>()?;
71
72        Ok(Self {
73            universe_size,
74            subsets,
75            bound,
76        })
77    }
78
79    pub fn universe_size(&self) -> usize {
80        self.universe_size
81    }
82
83    pub fn num_subsets(&self) -> usize {
84        self.subsets.len()
85    }
86
87    pub fn subsets(&self) -> &[Vec<usize>] {
88        &self.subsets
89    }
90
91    pub fn bound(&self) -> i64 {
92        self.bound
93    }
94
95    fn analyze_tree(config: &[usize]) -> Option<Vec<usize>> {
96        let roots = config
97            .iter()
98            .enumerate()
99            .filter(|(vertex, parent)| *vertex == **parent)
100            .count();
101        if roots != 1 {
102            return None;
103        }
104
105        let n = config.len();
106        let mut state = vec![0u8; n];
107        let mut depth = vec![0usize; n];
108
109        fn visit(vertex: usize, config: &[usize], state: &mut [u8], depth: &mut [usize]) -> bool {
110            match state[vertex] {
111                2 => return true,
112                1 => return false,
113                _ => {}
114            }
115
116            state[vertex] = 1;
117            let parent = config[vertex];
118            if parent == vertex {
119                depth[vertex] = 0;
120            } else {
121                if !visit(parent, config, state, depth) {
122                    return false;
123                }
124                depth[vertex] = depth[parent] + 1;
125            }
126            state[vertex] = 2;
127            true
128        }
129
130        for vertex in 0..n {
131            if !visit(vertex, config, &mut state, &mut depth) {
132                return None;
133            }
134        }
135
136        Some(depth)
137    }
138
139    fn is_ancestor(ancestor: usize, mut vertex: usize, config: &[usize], depth: &[usize]) -> bool {
140        if depth[ancestor] > depth[vertex] {
141            return false;
142        }
143
144        while depth[vertex] > depth[ancestor] {
145            vertex = config[vertex];
146        }
147
148        ancestor == vertex
149    }
150
151    fn subset_extension_cost(
152        &self,
153        subset: &[usize],
154        config: &[usize],
155        depth: &[usize],
156    ) -> Option<usize> {
157        if subset.len() <= 1 {
158            return Some(0);
159        }
160
161        let mut ordered = subset.to_vec();
162        ordered.sort_by_key(|&vertex| depth[vertex]);
163
164        for pair in ordered.windows(2) {
165            if !Self::is_ancestor(pair[0], pair[1], config, depth) {
166                return None;
167            }
168        }
169
170        let top = ordered[0];
171        let bottom = *ordered.last().unwrap();
172        Some(depth[bottom] - depth[top] + 1 - ordered.len())
173    }
174}
175
176impl Problem for RootedTreeStorageAssignment {
177    const NAME: &'static str = "RootedTreeStorageAssignment";
178    type Solution = Vec<usize>;
179    type Value = crate::types::Or;
180
181    crate::problem_parameters![
182        ("num_subsets", num_subsets),
183        ("universe_size", universe_size),
184    ];
185
186    fn evaluate(
187        &self,
188        config: &Self::Solution,
189    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
190        Ok({
191            crate::types::Or({
192                if config.len() != self.universe_size {
193                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
194                        "parent assignment length does not match the universe".into(),
195                    ));
196                }
197                if config.iter().any(|&parent| parent >= self.universe_size) {
198                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
199                        "parent assignment contains an out-of-range element".into(),
200                    ));
201                }
202                if self.universe_size == 0 {
203                    return Ok(crate::types::Or(self.subsets.is_empty()));
204                }
205
206                let Some(depth) = Self::analyze_tree(config) else {
207                    return Ok(crate::types::Or(false));
208                };
209
210                let mut total_cost = 0_i64;
211                for subset in &self.subsets {
212                    let Some(cost) = self.subset_extension_cost(subset, config, &depth) else {
213                        return Ok(crate::types::Or(false));
214                    };
215                    let cost = i64::try_from(cost).map_err(|_| {
216                        crate::traits::EvaluationError::IntegerOverflow(
217                            "converting a rooted-tree storage assignment cost to i64".to_string(),
218                        )
219                    })?;
220                    total_cost = total_cost.checked_add(cost).ok_or_else(|| {
221                        crate::traits::EvaluationError::IntegerOverflow(
222                            "summing rooted-tree storage assignment costs".to_string(),
223                        )
224                    })?;
225                    if total_cost > self.bound {
226                        return Ok(crate::types::Or(false));
227                    }
228                }
229
230                true
231            })
232        })
233    }
234
235    fn variant() -> Vec<(&'static str, &'static str)> {
236        crate::variant_params![]
237    }
238}
239
240impl crate::solvers::BruteForceProblem for RootedTreeStorageAssignment {
241    fn dimensions(&self) -> Vec<usize> {
242        vec![self.universe_size; self.universe_size]
243    }
244}
245
246crate::declare_variants! {
247    default RootedTreeStorageAssignment => "universe_size^universe_size",
248}
249
250crate::register_brute_force! {
251    RootedTreeStorageAssignment,
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![crate::example_db::specs::ModelExampleSpec {
257        id: "rooted_tree_storage_assignment",
258        instance: Box::new(RootedTreeStorageAssignment::new(
259            5,
260            vec![vec![0, 2], vec![1, 3], vec![0, 4], vec![2, 4]],
261            1,
262        )),
263        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 2]),
264        optimal_value: serde_json::json!(true),
265    }]
266}
267
268impl TryFrom<RootedTreeStorageAssignmentDef> for RootedTreeStorageAssignment {
269    type Error = crate::registry::ConstructionError;
270
271    fn try_from(value: RootedTreeStorageAssignmentDef) -> Result<Self, Self::Error> {
272        Self::try_new(value.universe_size, value.subsets, value.bound)
273    }
274}
275
276#[cfg(test)]
277#[path = "../../unit_tests/models/set/rooted_tree_storage_assignment.rs"]
278mod tests;
problemreductions/models/set/rooted_tree_storage_assignment.rs

problemreductions/models/set/
rooted_tree_storage_assignment.rs
