problemreductions/rules/
rootedtreearrangement_rootedtreestorageassignment.rs

1//! Reduction from RootedTreeArrangement to RootedTreeStorageAssignment.
2//!
3//! Given a RootedTreeArrangement instance with graph G = (V, E) and bound K,
4//! construct a RootedTreeStorageAssignment instance:
5//! - Universe X = V (the vertex set)
6//! - For each edge {u, v} in E, create a 2-element subset {u, v}
7//! - Bound K' = K - |E|
8//!
9//! The extension cost for a single edge subset {u,v} equals d_T(u,v) - 1
10//! in the rooted tree, so total extension cost = total arrangement cost - |E|.
11
12use crate::models::graph::RootedTreeArrangement;
13use crate::models::set::RootedTreeStorageAssignment;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing RootedTreeArrangement to RootedTreeStorageAssignment.
19#[derive(Debug, Clone)]
20pub struct ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
21    target: RootedTreeStorageAssignment,
22    /// Number of vertices in the source graph (needed for solution extraction).
23    num_vertices: usize,
24}
25
26impl ReductionResult for ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
27    type Source = RootedTreeArrangement<SimpleGraph>;
28    type Target = RootedTreeStorageAssignment;
29
30    fn target_problem(&self) -> &Self::Target {
31        &self.target
32    }
33
34    /// Extract a source solution from a target solution.
35    ///
36    /// The target config is a parent array defining a rooted tree on X = V.
37    /// The source config is [parent_array | identity_mapping] since X = V
38    /// means the mapping f is the identity.
39    fn extract_solution(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_witness(
44            self.target_problem(),
45            target_solution,
46            |value| value.0,
47            "target witness does not satisfy the target problem",
48        )?;
49
50        Ok({
51            let n = self.num_vertices;
52            // target_solution is the parent array of the rooted tree on X = V
53            // Source config = [parent_array, identity_mapping]
54            let mut source_config = target_solution.to_vec();
55            // Append identity mapping: f(v) = v for all v
56            source_config.extend(0..n);
57            source_config
58        })
59    }
60}
61
62#[crate::aggregate_reduction(identity)]
63impl crate::rules::AggregateReductionResult
64    for ReductionRootedTreeArrangementToRootedTreeStorageAssignment
65{
66}
67
68#[reduction(
69    transform = upper_bound {
70        universe_size = "num_vertices",
71        num_subsets = "num_edges",
72    }
73)]
74impl ReduceTo<RootedTreeStorageAssignment> for RootedTreeArrangement<SimpleGraph> {
75    type Result = ReductionRootedTreeArrangementToRootedTreeStorageAssignment;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let n = self.num_vertices();
79        // Loops have zero stretch and impose no storage constraint.
80        let edges: Vec<_> = self
81            .graph()
82            .edges()
83            .into_iter()
84            .filter(|&(u, v)| u != v)
85            .collect();
86        let num_edges = edges.len();
87
88        // Each edge becomes a 2-element subset
89        let subsets: Vec<Vec<usize>> = edges.iter().map(|&(u, v)| vec![u, v]).collect();
90
91        // Every non-loop edge contributes at least one unit of stretch.
92        let num_edges = i64::try_from(num_edges).map_err(|_| {
93            crate::rules::ReductionError::integer_overflow::<
94                RootedTreeArrangement<SimpleGraph>,
95                RootedTreeStorageAssignment,
96            >("converting the number of edges to i64")
97        })?;
98        let bound = if self.bound() < num_edges {
99            -1
100        } else {
101            self.bound() - num_edges
102        };
103
104        let target = RootedTreeStorageAssignment::new(n, subsets, bound);
105
106        Ok(
107            ReductionRootedTreeArrangementToRootedTreeStorageAssignment {
108                target,
109                num_vertices: n,
110            },
111        )
112    }
113}
114
115#[cfg(feature = "example-db")]
116pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
117    use crate::export::SolutionPair;
118
119    vec![crate::example_db::specs::RuleExampleSpec {
120        id: "rootedtreearrangement_to_rootedtreestorageassignment",
121        build: || {
122            // Path graph P4: 0-1-2-3, bound K=5
123            // Optimal tree: chain 0->1->2->3 (root=0), identity mapping
124            // Total distance = 1+1+1 = 3 <= 5
125            // Target: universe_size=4, subsets={{0,1},{1,2},{2,3}}, bound=5-3=2
126            // Target tree: parent=[0,0,1,2], identity mapping
127            // Extension cost = 0+0+0 = 0 <= 2
128            let source =
129                RootedTreeArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]), 5);
130            let source_config = vec![0, 0, 1, 2, 0, 1, 2, 3];
131            let target_config = vec![0, 0, 1, 2];
132            crate::example_db::specs::rule_example_with_witness::<_, RootedTreeStorageAssignment>(
133                source,
134                SolutionPair {
135                    source_config: serde_json::to_value(source_config)
136                        .expect("solution serialization must succeed"),
137                    target_config: serde_json::to_value(target_config)
138                        .expect("solution serialization must succeed"),
139                },
140            )
141        },
142    }]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/rootedtreearrangement_rootedtreestorageassignment.rs"]
147mod tests;
problemreductions/rules/rootedtreearrangement_rootedtreestorageassignment.rs

problemreductions/rules/
rootedtreearrangement_rootedtreestorageassignment.rs
