problemreductions/rules/
minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs

1//! Unit-weight feedback vertex set to unlimited-register code generation.
2//!
3//! The Aho–Johnson–Ullman reduction encodes cardinality, not arbitrary vertex
4//! weights. Each source vertex has a start operation followed by its outgoing
5//! arc operations. The separate start makes each right-use strictly later than
6//! the originating start, including self-loops. An additional right-only leaf
7//! makes every start binary without introducing another possible copy.
8
9use crate::models::graph::MinimumFeedbackVertexSet;
10use crate::models::misc::MinimumCodeGenerationUnlimitedRegisters;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::types::One;
14
15/// Result of the unit-weight FVS to code-generation reduction.
16#[derive(Debug, Clone)]
17pub struct ReductionFVSToCodeGen {
18    target: MinimumCodeGenerationUnlimitedRegisters,
19    /// Configuration index of each source vertex's start operation.
20    chain_start: Vec<usize>,
21    /// Configuration indices of operations that right-use each original leaf.
22    right_child_users: Vec<Vec<usize>>,
23}
24
25impl ReductionResult for ReductionFVSToCodeGen {
26    type Source = MinimumFeedbackVertexSet<One>;
27    type Target = MinimumCodeGenerationUnlimitedRegisters;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_witness(
38            self.target_problem(),
39            target_solution,
40            |value| value.0.is_some(),
41            "target order must be a permutation respecting expression dependencies",
42        )?;
43        Ok(self
44            .chain_start
45            .iter()
46            .zip(&self.right_child_users)
47            .map(|(&start, users)| {
48                users
49                    .iter()
50                    .any(|&user| target_solution[user] > target_solution[start])
51            })
52            .collect())
53    }
54}
55
56/// Count source leaves, the dummy leaf, and all start/arc operations before allocation.
57fn code_generation_vertex_count(n: usize, m: usize) -> Result<usize, crate::rules::ReductionError> {
58    n.checked_mul(2)
59        .and_then(|count| count.checked_add(m))
60        .and_then(|count| count.checked_add(1))
61        .ok_or_else(|| {
62            crate::rules::ReductionError::integer_overflow::<
63                MinimumFeedbackVertexSet<One>,
64                MinimumCodeGenerationUnlimitedRegisters,
65            >("counting code-generation start and arc nodes")
66        })
67}
68
69#[reduction(
70    transform = exact {
71        num_vertices = "2 * num_vertices + num_arcs + 1",
72    }
73)]
74impl ReduceTo<MinimumCodeGenerationUnlimitedRegisters> for MinimumFeedbackVertexSet<One> {
75    type Result = ReductionFVSToCodeGen;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let n = self.graph().num_vertices();
79        let m = self.graph().num_arcs();
80        let num_vertices = code_generation_vertex_count(n, m)?;
81        // All subsequent offsets are bounded by the checked total above.
82        let first_internal = n + 1;
83        let num_internal = n + m;
84        let mut out_neighbors = vec![vec![]; n];
85        for (u, v) in self.graph().arcs() {
86            out_neighbors[u].push(v);
87        }
88        let mut left_arcs = Vec::with_capacity(num_internal);
89        let mut right_arcs = Vec::with_capacity(num_internal);
90        let mut chain_start = Vec::with_capacity(n);
91        let mut right_child_users = vec![vec![]; n];
92        let mut next_internal = first_internal;
93        for (x, neighbors) in out_neighbors.iter().enumerate() {
94            chain_start.push(next_internal - first_internal);
95            left_arcs.push((next_internal, x));
96            right_arcs.push((next_internal, n)); // dummy leaf is never overwritten
97            next_internal += 1;
98            for &neighbor in neighbors {
99                left_arcs.push((next_internal, next_internal - 1));
100                right_arcs.push((next_internal, neighbor));
101                right_child_users[neighbor].push(next_internal - first_internal);
102                next_internal += 1;
103            }
104        }
105        debug_assert_eq!(next_internal, num_vertices);
106        let target =
107            MinimumCodeGenerationUnlimitedRegisters::new(num_vertices, left_arcs, right_arcs);
108        Ok(ReductionFVSToCodeGen {
109            target,
110            chain_start,
111            right_child_users,
112        })
113    }
114}
115
116#[cfg(any(test, feature = "example-db"))]
117fn issue_example_source() -> MinimumFeedbackVertexSet<One> {
118    use crate::topology::DirectedGraph;
119    MinimumFeedbackVertexSet::new(
120        DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
121        vec![One; 3],
122    )
123}
124
125#[cfg(feature = "example-db")]
126pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
127    use crate::export::SolutionPair;
128    use crate::solvers::BruteForce;
129
130    vec![crate::example_db::specs::RuleExampleSpec {
131        id: "minimumfeedbackvertexset_to_minimumcodegenerationunlimitedregisters",
132        build: || {
133            let source = issue_example_source();
134            let reduction = ReduceTo::<MinimumCodeGenerationUnlimitedRegisters>::reduce_to(&source)
135                .expect("reduction should succeed");
136            let target_config = BruteForce::new()
137                .solve(reduction.target_problem())
138                .expect("canonical target evaluation must succeed")
139                .expect("canonical DAG has an evaluation order");
140            let source_config = reduction.extract_solution(&target_config).unwrap();
141            crate::example_db::specs::assemble_rule_example(
142                &source,
143                reduction.target_problem(),
144                vec![SolutionPair {
145                    source_config: serde_json::to_value(source_config)
146                        .expect("solution serialization must succeed"),
147                    target_config: serde_json::to_value(target_config)
148                        .expect("solution serialization must succeed"),
149                }],
150            )
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs"]
157mod tests;
problemreductions/rules/minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs

problemreductions/rules/
minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs
