problemreductions/rules/
hamiltonianpath_degreeconstrainedspanningtree.rs

1//! Reduction from HamiltonianPath to DegreeConstrainedSpanningTree.
2//!
3//! A spanning tree with maximum degree 2 is exactly a Hamiltonian path.
4
5use crate::models::graph::{DegreeConstrainedSpanningTree, HamiltonianPath};
6use crate::reduction;
7use crate::rules::traits::{ReduceTo, ReductionResult};
8use crate::topology::{Graph, SimpleGraph};
9
10/// Result of reducing HamiltonianPath to DegreeConstrainedSpanningTree.
11#[derive(Debug, Clone)]
12pub struct ReductionHamiltonianPathToDegreeConstrainedSpanningTree {
13    target: DegreeConstrainedSpanningTree<SimpleGraph>,
14}
15
16impl ReductionResult for ReductionHamiltonianPathToDegreeConstrainedSpanningTree {
17    type Source = HamiltonianPath<SimpleGraph>;
18    type Target = DegreeConstrainedSpanningTree<SimpleGraph>;
19
20    fn target_problem(&self) -> &Self::Target {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_witness(
29            self.target_problem(),
30            target_solution,
31            |value| value.0,
32            "target witness is not satisfying",
33        )?;
34
35        extract_hamiltonian_order(self.target.graph(), target_solution)
36    }
37}
38
39#[crate::aggregate_reduction(identity)]
40impl crate::rules::AggregateReductionResult
41    for ReductionHamiltonianPathToDegreeConstrainedSpanningTree
42{
43}
44
45#[reduction(
46    transform = exact {
47        num_vertices = "num_vertices",
48        num_edges = "num_edges",
49    }
50)]
51impl ReduceTo<DegreeConstrainedSpanningTree<SimpleGraph>> for HamiltonianPath<SimpleGraph> {
52    type Result = ReductionHamiltonianPathToDegreeConstrainedSpanningTree;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let target = DegreeConstrainedSpanningTree::new(
56            SimpleGraph::new(self.graph().num_vertices(), self.graph().edges()),
57            2,
58        );
59        Ok(ReductionHamiltonianPathToDegreeConstrainedSpanningTree { target })
60    }
61}
62
63fn extract_hamiltonian_order(
64    graph: &SimpleGraph,
65    target_solution: &[bool],
66) -> crate::rules::ExtractionResult<Vec<usize>> {
67    let num_vertices = graph.num_vertices();
68    if num_vertices < 2 {
69        return Ok((0..num_vertices).collect());
70    }
71
72    let edges = graph.edges();
73    let mut adjacency = vec![Vec::new(); num_vertices];
74    for ((u, v), &selected) in edges.iter().copied().zip(target_solution.iter()) {
75        if !selected {
76            continue;
77        }
78        adjacency[u].push(v);
79        adjacency[v].push(u);
80    }
81
82    let mut endpoints: Vec<usize> = adjacency
83        .iter()
84        .enumerate()
85        .filter_map(|(vertex, neighbors)| (neighbors.len() == 1).then_some(vertex))
86        .collect();
87    endpoints.sort_unstable();
88    if endpoints.len() != 2 {
89        return Err(crate::rules::ExtractionError::invalid(
90            "selected edges do not form a Hamiltonian path",
91        ));
92    }
93
94    let mut order = Vec::with_capacity(num_vertices);
95    let mut visited = vec![false; num_vertices];
96    let mut previous = None;
97    let mut current = endpoints[0];
98
99    loop {
100        if visited[current] {
101            return Err(crate::rules::ExtractionError::invalid(
102                "selected edges contain a cycle",
103            ));
104        }
105        visited[current] = true;
106        order.push(current);
107
108        let next = adjacency[current]
109            .iter()
110            .copied()
111            .find(|&neighbor| Some(neighbor) != previous && !visited[neighbor]);
112        match next {
113            Some(next_vertex) => {
114                previous = Some(current);
115                current = next_vertex;
116            }
117            None => break,
118        }
119    }
120
121    if order.len() == num_vertices {
122        Ok(order)
123    } else {
124        Err(crate::rules::ExtractionError::invalid(
125            "selected edges do not span every source vertex",
126        ))
127    }
128}
129
130#[cfg(feature = "example-db")]
131fn edge_config_for_path(graph: &SimpleGraph, path: &[usize]) -> Vec<bool> {
132    let selected_edges: Vec<(usize, usize)> = path
133        .windows(2)
134        .map(|window| (window[0], window[1]))
135        .collect();
136    graph
137        .edges()
138        .into_iter()
139        .map(|(u, v)| {
140            selected_edges
141                .iter()
142                .any(|&(a, b)| (a == u && b == v) || (a == v && b == u))
143        })
144        .collect()
145}
146
147#[cfg(feature = "example-db")]
148pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
149    fn source_example() -> HamiltonianPath<SimpleGraph> {
150        HamiltonianPath::new(SimpleGraph::new(
151            6,
152            vec![
153                (0, 1),
154                (0, 2),
155                (1, 3),
156                (2, 3),
157                (3, 4),
158                (3, 5),
159                (4, 2),
160                (5, 1),
161            ],
162        ))
163    }
164
165    vec![crate::example_db::specs::RuleExampleSpec {
166        id: "hamiltonianpath_to_degreeconstrainedspanningtree",
167        build: || {
168            let source_config = vec![0, 2, 4, 3, 1, 5];
169            let source = source_example();
170            let reduction =
171                ReduceTo::<DegreeConstrainedSpanningTree<SimpleGraph>>::reduce_to(&source)
172                    .expect("reduction should succeed");
173            let target_config =
174                edge_config_for_path(reduction.target_problem().graph(), &source_config);
175            crate::example_db::specs::rule_example_with_witness::<
176                _,
177                DegreeConstrainedSpanningTree<SimpleGraph>,
178            >(
179                source,
180                crate::export::SolutionPair {
181                    source_config: serde_json::to_value(source_config)
182                        .expect("solution serialization must succeed"),
183                    target_config: serde_json::to_value(target_config)
184                        .expect("solution serialization must succeed"),
185                },
186            )
187        },
188    }]
189}
190
191#[cfg(test)]
192#[path = "../unit_tests/rules/hamiltonianpath_degreeconstrainedspanningtree.rs"]
193mod tests;
problemreductions/rules/hamiltonianpath_degreeconstrainedspanningtree.rs

problemreductions/rules/
hamiltonianpath_degreeconstrainedspanningtree.rs
