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

problemreductions/rules/
hamiltonianpath_degreeconstrainedspanningtree.rs
