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

problemreductions/rules/
hamiltonianpath_degreeconstrainedspanningtree.rs
