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        let value =
38            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
39        if value.0.is_none() {
40            return Err(crate::rules::ExtractionError::invalid(
41                "target order must be a permutation respecting expression dependencies",
42            ));
43        }
44        Ok(self
45            .chain_start
46            .iter()
47            .zip(&self.right_child_users)
48            .map(|(&start, users)| {
49                users
50                    .iter()
51                    .any(|&user| target_solution[user] > target_solution[start])
52            })
53            .collect())
54    }
55}
56
57/// Count source leaves, the dummy leaf, and all start/arc operations before allocation.
58fn code_generation_vertex_count(n: usize, m: usize) -> Result<usize, crate::rules::ReductionError> {
59    n.checked_mul(2)
60        .and_then(|count| count.checked_add(m))
61        .and_then(|count| count.checked_add(1))
62        .ok_or_else(|| {
63            crate::rules::ReductionError::integer_overflow::<
64                MinimumFeedbackVertexSet<One>,
65                MinimumCodeGenerationUnlimitedRegisters,
66            >("counting code-generation start and arc nodes")
67        })
68}
69
70#[reduction(
71    transform = exact {
72        num_vertices = "2 * num_vertices + num_arcs + 1",
73    }
74)]
75impl ReduceTo<MinimumCodeGenerationUnlimitedRegisters> for MinimumFeedbackVertexSet<One> {
76    type Result = ReductionFVSToCodeGen;
77
78    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
79        let n = self.graph().num_vertices();
80        let m = self.graph().num_arcs();
81        let num_vertices = code_generation_vertex_count(n, m)?;
82        // All subsequent offsets are bounded by the checked total above.
83        let first_internal = n + 1;
84        let num_internal = n + m;
85        let mut out_neighbors = vec![vec![]; n];
86        for (u, v) in self.graph().arcs() {
87            out_neighbors[u].push(v);
88        }
89        let mut left_arcs = Vec::with_capacity(num_internal);
90        let mut right_arcs = Vec::with_capacity(num_internal);
91        let mut chain_start = Vec::with_capacity(n);
92        let mut right_child_users = vec![vec![]; n];
93        let mut next_internal = first_internal;
94        for (x, neighbors) in out_neighbors.iter().enumerate() {
95            chain_start.push(next_internal - first_internal);
96            left_arcs.push((next_internal, x));
97            right_arcs.push((next_internal, n)); // dummy leaf is never overwritten
98            next_internal += 1;
99            for &neighbor in neighbors {
100                left_arcs.push((next_internal, next_internal - 1));
101                right_arcs.push((next_internal, neighbor));
102                right_child_users[neighbor].push(next_internal - first_internal);
103                next_internal += 1;
104            }
105        }
106        debug_assert_eq!(next_internal, num_vertices);
107        let target =
108            MinimumCodeGenerationUnlimitedRegisters::new(num_vertices, left_arcs, right_arcs);
109        Ok(ReductionFVSToCodeGen {
110            target,
111            chain_start,
112            right_child_users,
113        })
114    }
115}
116
117#[cfg(any(test, feature = "example-db"))]
118fn issue_example_source() -> MinimumFeedbackVertexSet<One> {
119    use crate::topology::DirectedGraph;
120    MinimumFeedbackVertexSet::new(
121        DirectedGraph::new(3, vec![(0, 1), (1, 2), (2, 0)]),
122        vec![One; 3],
123    )
124}
125
126#[cfg(feature = "example-db")]
127pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
128    use crate::export::SolutionPair;
129    use crate::solvers::BruteForce;
130
131    vec![crate::example_db::specs::RuleExampleSpec {
132        id: "minimumfeedbackvertexset_to_minimumcodegenerationunlimitedregisters",
133        build: || {
134            let source = issue_example_source();
135            let reduction = ReduceTo::<MinimumCodeGenerationUnlimitedRegisters>::reduce_to(&source)
136                .expect("reduction should succeed");
137            let target_config = BruteForce::new()
138                .solve(reduction.target_problem())
139                .expect("canonical target evaluation must succeed")
140                .expect("canonical DAG has an evaluation order");
141            let source_config = reduction.extract_solution(&target_config).unwrap();
142            crate::example_db::specs::assemble_rule_example(
143                &source,
144                reduction.target_problem(),
145                vec![SolutionPair {
146                    source_config: serde_json::to_value(source_config)
147                        .expect("solution serialization must succeed"),
148                    target_config: serde_json::to_value(target_config)
149                        .expect("solution serialization must succeed"),
150                }],
151            )
152        },
153    }]
154}
155
156#[cfg(test)]
157#[path = "../unit_tests/rules/minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs"]
158mod tests;
problemreductions/rules/minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs

problemreductions/rules/
minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters.rs
