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::graph::{HamiltonianPathBetweenTwoVertices, LongestPath};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12use crate::types::One;
13
14/// Result of reducing HamiltonianPathBetweenTwoVertices to LongestPath.
15#[derive(Debug, Clone)]
16pub struct ReductionHPBTVToLP {
17    target: LongestPath<SimpleGraph, One>,
18}
19
20impl ReductionResult for ReductionHPBTVToLP {
21    type Source = HamiltonianPathBetweenTwoVertices<SimpleGraph>;
22    type Target = LongestPath<SimpleGraph, One>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    /// Extract a vertex-permutation solution from an edge-selection solution.
29    ///
30    /// The target solution is a binary vector over edges. We walk the selected
31    /// edges from the source vertex to reconstruct the vertex ordering.
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        let value =
37            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38        if !crate::rules::AggregateReductionResult::extract_value(self, value).0 {
39            return Err(crate::rules::ExtractionError::invalid(
40                "target path does not certify a Hamiltonian source-target path",
41            ));
42        }
43
44        let mut adjacency = vec![Vec::new(); self.target.num_vertices()];
45        for (&selected, (u, v)) in target_solution.iter().zip(self.target.graph().edges()) {
46            if selected {
47                adjacency[u].push(v);
48                adjacency[v].push(u);
49            }
50        }
51
52        // Target feasibility guarantees a single simple path with these endpoints.
53        // Its certified n-1 edges visit every vertex; walking away from the
54        // previous vertex terminates at the target without repetitions.
55        let mut current = self.target.source_vertex();
56        let mut previous = None;
57        let mut path = Vec::with_capacity(self.target.num_vertices());
58        path.push(current);
59        while let Some(&next) = adjacency[current]
60            .iter()
61            .find(|&&neighbor| Some(neighbor) != previous)
62        {
63            previous = Some(current);
64            current = next;
65            path.push(current);
66        }
67        Ok(path)
68    }
69}
70
71impl crate::rules::AggregateReductionResult for ReductionHPBTVToLP {
72    type Source = HamiltonianPathBetweenTwoVertices<SimpleGraph>;
73    type Target = LongestPath<SimpleGraph, One>;
74
75    fn target_problem(&self) -> &Self::Target {
76        &self.target
77    }
78
79    fn extract_value(&self, value: crate::types::Max<i64>) -> crate::types::Or {
80        // The source requires distinct valid endpoints, hence at least two vertices.
81        crate::types::Or(
82            value.0.is_some_and(|length| {
83                usize::try_from(length) == Ok(self.target.num_vertices() - 1)
84            }),
85        )
86    }
87}
88
89#[reduction(
90    aggregate = custom,
91    transform = exact {
92        num_vertices = "num_vertices",
93        num_edges = "num_edges",
94    })]
95impl ReduceTo<LongestPath<SimpleGraph, One>> for HamiltonianPathBetweenTwoVertices<SimpleGraph> {
96    type Result = ReductionHPBTVToLP;
97
98    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
99        let graph = self.graph().clone();
100        let num_edges = graph.num_edges();
101        let edge_lengths = vec![One; num_edges];
102
103        let target = LongestPath::new(
104            graph,
105            edge_lengths,
106            self.source_vertex(),
107            self.target_vertex(),
108        );
109
110        Ok(ReductionHPBTVToLP { target })
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    use crate::export::SolutionPair;
117
118    vec![crate::example_db::specs::RuleExampleSpec {
119        id: "hamiltonianpathbetweentwovertices_to_longestpath",
120        build: || {
121            // Path graph 0-1-2-3-4 with s=0, t=4
122            let source = HamiltonianPathBetweenTwoVertices::new(
123                SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
124                0,
125                4,
126            );
127            crate::example_db::specs::rule_example_with_witness::<_, LongestPath<SimpleGraph, One>>(
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
