problemreductions/models/graph/
rooted_tree_arrangement.rs

1//! Rooted Tree Arrangement problem implementation.
2//!
3//! The Rooted Tree Arrangement problem asks whether a graph can be embedded
4//! into the nodes of a rooted tree so that every graph edge lies on a single
5//! root-to-leaf path and the total tree stretch is bounded.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::variant::VariantParam;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "RootedTreeArrangement",
16        display_name: "Rooted Tree Arrangement",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find a rooted-tree embedding of a graph with bounded total edge stretch",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
26            FieldInfo { name: "bound", type_name: "i64", description: "Upper bound K on total tree stretch" },
27        ],
28    }
29}
30
31#[derive(Debug, Clone, Serialize, Deserialize)]
32#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
33pub struct RootedTreeArrangement<G> {
34    graph: G,
35    bound: i64,
36}
37
38#[derive(Debug, Deserialize, crate::CreateSpec)]
39struct RootedTreeArrangementRandomSpec {
40    /// Number of graph vertices.
41    num_vertices: usize,
42    /// Independent edge probability (default: 0.5).
43    edge_prob: Option<f64>,
44    /// Seed for reproducible generation.
45    seed: Option<i64>,
46    /// Maximum total edge stretch (defaults to a graph-size upper bound).
47    bound: Option<i64>,
48}
49
50#[derive(Debug, Clone)]
51struct TreeInfo {
52    depth: Vec<usize>,
53}
54
55impl<G: Graph> RootedTreeArrangement<G> {
56    pub fn new(graph: G, bound: i64) -> Self {
57        Self { graph, bound }
58    }
59
60    pub fn graph(&self) -> &G {
61        &self.graph
62    }
63
64    pub fn bound(&self) -> i64 {
65        self.bound
66    }
67
68    pub fn num_vertices(&self) -> usize {
69        self.graph.num_vertices()
70    }
71
72    pub fn num_edges(&self) -> usize {
73        self.graph.num_edges()
74    }
75
76    pub fn is_valid_solution(
77        &self,
78        config: &[usize],
79    ) -> Result<bool, crate::traits::EvaluationError> {
80        Ok(matches!(self.total_edge_stretch(config)?, Some(stretch) if stretch <= self.bound))
81    }
82
83    pub fn total_edge_stretch(
84        &self,
85        config: &[usize],
86    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
87        let n = self.graph.num_vertices();
88        if n == 0 {
89            return Ok(config.is_empty().then_some(0));
90        }
91
92        let Some((parent, mapping)) = self.split_config(config) else {
93            return Ok(None);
94        };
95        let Some(tree) = analyze_parent_array(parent) else {
96            return Ok(None);
97        };
98        if !is_valid_permutation(mapping) {
99            return Ok(None);
100        }
101
102        let mut total = 0_i64;
103        for (u, v) in self.graph.edges() {
104            let tree_u = mapping[u];
105            let tree_v = mapping[v];
106            if !are_ancestor_comparable(parent, tree_u, tree_v) {
107                return Ok(None);
108            }
109            let stretch =
110                i64::try_from(tree.depth[tree_u].abs_diff(tree.depth[tree_v])).map_err(|_| {
111                    crate::traits::EvaluationError::IntegerOverflow(
112                        "converting a rooted-tree edge stretch to i64".to_string(),
113                    )
114                })?;
115            total = total.checked_add(stretch).ok_or_else(|| {
116                crate::traits::EvaluationError::IntegerOverflow(
117                    "summing rooted-tree arrangement edge stretches".to_string(),
118                )
119            })?;
120        }
121
122        Ok(Some(total))
123    }
124
125    fn split_config<'a>(&self, config: &'a [usize]) -> Option<(&'a [usize], &'a [usize])> {
126        let n = self.graph.num_vertices();
127        (config.len() == 2 * n).then(|| config.split_at(n))
128    }
129}
130
131impl<G> Problem for RootedTreeArrangement<G>
132where
133    G: Graph + VariantParam,
134{
135    const NAME: &'static str = "RootedTreeArrangement";
136    type Solution = Vec<usize>;
137    type Value = crate::types::Or;
138
139    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
140
141    fn variant() -> Vec<(&'static str, &'static str)> {
142        crate::variant_params![G]
143    }
144
145    fn evaluate(
146        &self,
147        config: &Self::Solution,
148    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
149        let n = self.graph.num_vertices();
150        if config.len() != 2 * n {
151            return Err(crate::traits::EvaluationError::InvalidConfiguration(
152                "tree-arrangement representation length does not match the graph".into(),
153            ));
154        }
155        Ok(crate::types::Or(self.is_valid_solution(config)?))
156    }
157}
158
159impl<G> crate::solvers::BruteForceProblem for RootedTreeArrangement<G>
160where
161    G: Graph + VariantParam,
162{
163    fn dimensions(&self) -> Vec<usize> {
164        let n = self.graph.num_vertices();
165        vec![n; 2 * n]
166    }
167}
168
169fn analyze_parent_array(parent: &[usize]) -> Option<TreeInfo> {
170    let n = parent.len();
171    if n == 0 {
172        return Some(TreeInfo { depth: vec![] });
173    }
174
175    if parent.iter().any(|&p| p >= n) {
176        return None;
177    }
178
179    let roots = parent
180        .iter()
181        .enumerate()
182        .filter_map(|(node, &p)| (node == p).then_some(node))
183        .collect::<Vec<_>>();
184    if roots.len() != 1 {
185        return None;
186    }
187    let root = roots[0];
188
189    let mut state = vec![0u8; n];
190    let mut depth = vec![0usize; n];
191
192    fn visit(
193        node: usize,
194        root: usize,
195        parent: &[usize],
196        state: &mut [u8],
197        depth: &mut [usize],
198    ) -> Option<usize> {
199        match state[node] {
200            1 => return None,
201            2 => return Some(depth[node]),
202            _ => {}
203        }
204
205        state[node] = 1;
206        let d = if node == root {
207            0
208        } else {
209            let next = parent[node];
210            if next == node {
211                return None;
212            }
213            visit(next, root, parent, state, depth)? + 1
214        };
215        depth[node] = d;
216        state[node] = 2;
217        Some(d)
218    }
219
220    for node in 0..n {
221        visit(node, root, parent, &mut state, &mut depth)?;
222    }
223
224    Some(TreeInfo { depth })
225}
226
227fn is_valid_permutation(mapping: &[usize]) -> bool {
228    let n = mapping.len();
229    let mut seen = vec![false; n];
230    for &image in mapping {
231        if image >= n || seen[image] {
232            return false;
233        }
234        seen[image] = true;
235    }
236    true
237}
238
239fn is_ancestor(parent: &[usize], ancestor: usize, descendant: usize) -> bool {
240    let mut current = descendant;
241    loop {
242        if current == ancestor {
243            return true;
244        }
245        let next = parent[current];
246        if next == current {
247            return false;
248        }
249        current = next;
250    }
251}
252
253fn are_ancestor_comparable(parent: &[usize], u: usize, v: usize) -> bool {
254    is_ancestor(parent, u, v) || is_ancestor(parent, v, u)
255}
256
257crate::impl_random_generate!(
258    RootedTreeArrangement<SimpleGraph>,
259    RootedTreeArrangementRandomSpec,
260    |spec| {
261        let graph = crate::random::SimpleGraphRandomSpec {
262            num_vertices: spec.num_vertices,
263            edge_prob: spec.edge_prob,
264            seed: spec.seed,
265        }
266        .graph()?;
267        let bound = match spec.bound {
268            Some(bound) => bound,
269            None => {
270                let max_depth = if spec.num_vertices == 0 {
271                    0
272                } else {
273                    spec.num_vertices - 1
274                };
275                let max_stretch = max_depth.checked_mul(graph.num_edges()).ok_or_else(|| {
276                    crate::registry::ConstructionError::IntegerOverflow(
277                        "default rooted-tree arrangement bound overflows usize".into(),
278                    )
279                })?;
280                i64::try_from(max_stretch).map_err(|_| {
281                    crate::registry::ConstructionError::IntegerOverflow(
282                        "default rooted-tree arrangement bound does not fit i64".into(),
283                    )
284                })?
285            }
286        };
287        Ok(RootedTreeArrangement::new(graph, bound))
288    }
289);
290
291crate::declare_variants! {
292    default RootedTreeArrangement<SimpleGraph> => "2^num_vertices" random,
293}
294
295crate::register_brute_force! {
296    RootedTreeArrangement<SimpleGraph>,
297}
298
299#[cfg(feature = "example-db")]
300pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
301    vec![crate::example_db::specs::ModelExampleSpec {
302        id: "rooted_tree_arrangement_simplegraph",
303        instance: Box::new(RootedTreeArrangement::new(
304            SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (2, 3)]),
305            5,
306        )),
307        optimal_config: serde_json::json!(vec![0, 0, 1, 2, 0, 1, 2, 3]),
308        optimal_value: serde_json::json!(true),
309    }]
310}
311
312#[cfg(test)]
313#[path = "../../unit_tests/models/graph/rooted_tree_arrangement.rs"]
314mod tests;
problemreductions/models/graph/rooted_tree_arrangement.rs

problemreductions/models/graph/
rooted_tree_arrangement.rs
