problemreductions/rules/
hamiltonianpath_isomorphicspanningtree.rs

1//! Reduction from HamiltonianPath to `IsomorphicSpanningTree<SimpleGraph>`.
2//!
3//! A Hamiltonian path in G exists iff G has a spanning tree isomorphic to the
4//! path graph P_n. The reduction keeps G unchanged as the host graph and
5//! constructs T = P_n (the path on n vertices: edges {0,1},{1,2},...,{n-2,n-1}).
6
7use crate::models::graph::{HamiltonianPath, IsomorphicSpanningTree};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::SimpleGraph;
11
12/// Result of reducing HamiltonianPath to IsomorphicSpanningTree<SimpleGraph>.
13#[derive(Debug, Clone)]
14pub struct ReductionHPToIST {
15    target: IsomorphicSpanningTree<SimpleGraph>,
16}
17
18impl ReductionResult for ReductionHPToIST {
19    type Source = HamiltonianPath<SimpleGraph>;
20    type Target = IsomorphicSpanningTree<SimpleGraph>;
21
22    fn target_problem(&self) -> &Self::Target {
23        &self.target
24    }
25
26    /// Solution extraction: identity mapping.
27    ///
28    /// The IST config maps tree vertex i to graph vertex config[i]. Since the
29    /// tree is P_n (path 0-1-2-...-n-1), this mapping directly gives the
30    /// vertex ordering of the Hamiltonian path.
31    fn extract_solution(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_witness(
36            self.target_problem(),
37            target_solution,
38            |value| value.0,
39            "target witness is not satisfying",
40        )?;
41
42        Ok(target_solution.to_vec())
43    }
44}
45
46#[crate::aggregate_reduction(identity)]
47impl crate::rules::AggregateReductionResult for ReductionHPToIST {}
48
49#[reduction(
50    transform = exact {
51        num_vertices = "num_vertices",
52        num_edges = "num_edges",
53    }
54)]
55impl ReduceTo<IsomorphicSpanningTree<SimpleGraph>> for HamiltonianPath<SimpleGraph> {
56    type Result = ReductionHPToIST;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let n = self.num_vertices();
60
61        // Host graph: keep G unchanged
62        let graph = self.graph().clone();
63
64        let tree = SimpleGraph::path(n);
65
66        Ok(ReductionHPToIST {
67            target: IsomorphicSpanningTree::new(graph, tree),
68        })
69    }
70}
71
72#[cfg(feature = "example-db")]
73pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
74    use crate::export::SolutionPair;
75
76    vec![crate::example_db::specs::RuleExampleSpec {
77        id: "hamiltonianpath_to_isomorphicspanningtree",
78        build: || {
79            // Path graph 0-1-2-3-4 has a trivial Hamiltonian path
80            let source = HamiltonianPath::new(SimpleGraph::path(5));
81            crate::example_db::specs::rule_example_with_witness::<
82                _,
83                IsomorphicSpanningTree<SimpleGraph>,
84            >(
85                source,
86                SolutionPair {
87                    source_config: serde_json::json!(vec![0, 1, 2, 3, 4]),
88                    target_config: serde_json::json!(vec![0, 1, 2, 3, 4]),
89                },
90            )
91        },
92    }]
93}
94
95#[cfg(test)]
96#[path = "../unit_tests/rules/hamiltonianpath_isomorphicspanningtree.rs"]
97mod tests;
problemreductions/rules/hamiltonianpath_isomorphicspanningtree.rs

problemreductions/rules/
hamiltonianpath_isomorphicspanningtree.rs
