problemreductions/rules/
hamiltonianpathbetweentwovertices_longestpath.rs

1//! Reduction from HamiltonianPathBetweenTwoVertices to LongestPath.
2//!
3//! A Hamiltonian s-t path in G has length n-1 edges (the maximum possible for
4//! any simple path). Setting all edge lengths to unit weight and the same
5//! source/target vertices, the longest path of length n-1 exactly corresponds
6//! to a Hamiltonian s-t path.
7
8use crate::models::decision::Decision;
9use crate::models::graph::{HamiltonianPathBetweenTwoVertices, LongestPath};
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13use crate::types::One;
14
15/// Result of reducing HamiltonianPathBetweenTwoVertices to LongestPath.
16#[derive(Debug, Clone)]
17pub struct ReductionHPBTVToLP {
18    target: Decision<LongestPath<SimpleGraph, One>>,
19}
20
21impl ReductionResult for ReductionHPBTVToLP {
22    type Source = HamiltonianPathBetweenTwoVertices<SimpleGraph>;
23    type Target = Decision<LongestPath<SimpleGraph, One>>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    /// Extract a vertex-permutation solution from an edge-selection solution.
30    ///
31    /// The target solution is a binary vector over edges. We walk the selected
32    /// edges from the source vertex to reconstruct the vertex ordering.
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        crate::rules::traits::validate_target_witness(
38            self.target_problem(),
39            target_solution,
40            |value| value.0,
41            "target path does not certify a Hamiltonian source-target path",
42        )?;
43
44        let mut adjacency = vec![Vec::new(); self.target.inner().num_vertices()];
45        for (&selected, (u, v)) in target_solution
46            .iter()
47            .zip(self.target.inner().graph().edges())
48        {
49            if selected {
50                adjacency[u].push(v);
51                adjacency[v].push(u);
52            }
53        }
54
55        // Target feasibility guarantees a single simple path with these endpoints.
56        // Its certified n-1 edges visit every vertex; walking away from the
57        // previous vertex terminates at the target without repetitions.
58        let mut current = self.target.inner().source_vertex();
59        let mut previous = None;
60        let mut path = Vec::with_capacity(self.target.inner().num_vertices());
61        path.push(current);
62        while let Some(&next) = adjacency[current]
63            .iter()
64            .find(|&&neighbor| Some(neighbor) != previous)
65        {
66            previous = Some(current);
67            current = next;
68            path.push(current);
69        }
70        Ok(path)
71    }
72}
73
74#[crate::aggregate_reduction(identity)]
75impl crate::rules::AggregateReductionResult for ReductionHPBTVToLP {}
76
77#[reduction(
78    transform = exact {
79        num_vertices = "num_vertices",
80        num_edges = "num_edges",
81    })]
82impl ReduceTo<Decision<LongestPath<SimpleGraph, One>>>
83    for HamiltonianPathBetweenTwoVertices<SimpleGraph>
84{
85    type Result = ReductionHPBTVToLP;
86
87    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
88        let graph = self.graph().clone();
89        let num_edges = graph.num_edges();
90        let edge_lengths = vec![One; num_edges];
91
92        let target = LongestPath::new(
93            graph,
94            edge_lengths,
95            self.source_vertex(),
96            self.target_vertex(),
97        );
98
99        Ok(ReductionHPBTVToLP {
100            target: Decision::new(
101                target,
102                <Self as ReduceTo<Decision<LongestPath<SimpleGraph, One>>>>::exact_i64(
103                    self.num_vertices() - 1,
104                    "encoding the path bound",
105                )?,
106            ),
107        })
108    }
109}
110
111#[cfg(feature = "example-db")]
112pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
113    use crate::export::SolutionPair;
114
115    vec![crate::example_db::specs::RuleExampleSpec {
116        id: "hamiltonianpathbetweentwovertices_to_longestpath",
117        build: || {
118            // Path graph 0-1-2-3-4 with s=0, t=4
119            let source = HamiltonianPathBetweenTwoVertices::new(
120                SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
121                0,
122                4,
123            );
124            crate::example_db::specs::rule_example_with_witness::<
125                _,
126                Decision<LongestPath<SimpleGraph, One>>,
127            >(
128                source,
129                SolutionPair {
130                    source_config: serde_json::json!(vec![0, 1, 2, 3, 4]),
131                    target_config: serde_json::json!(vec![true, true, true, true]),
132                },
133            )
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/hamiltonianpathbetweentwovertices_longestpath.rs"]
140mod tests;
problemreductions/rules/hamiltonianpathbetweentwovertices_longestpath.rs

problemreductions/rules/
hamiltonianpathbetweentwovertices_longestpath.rs
