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    /// Cached edge list from the graph, indexed by edge position.
19    edges: Vec<(usize, usize)>,
20    source_vertex: usize,
21    num_vertices: usize,
22}
23
24impl ReductionResult for ReductionHPBTVToLP {
25    type Source = HamiltonianPathBetweenTwoVertices<SimpleGraph>;
26    type Target = LongestPath<SimpleGraph, One>;
27
28    fn target_problem(&self) -> &Self::Target {
29        &self.target
30    }
31
32    /// Extract a vertex-permutation solution from an edge-selection solution.
33    ///
34    /// The target solution is a binary vector over edges. We walk the selected
35    /// edges from the source vertex to reconstruct the vertex ordering.
36    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
37        let n = self.num_vertices;
38
39        // Build adjacency from selected edges
40        let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
41        for (idx, &selected) in target_solution.iter().enumerate() {
42            if selected == 1 {
43                let (u, v) = self.edges[idx];
44                adj[u].push(v);
45                adj[v].push(u);
46            }
47        }
48
49        // Walk the path from source
50        let mut path = Vec::with_capacity(n);
51        let mut current = self.source_vertex;
52        let mut prev = usize::MAX; // sentinel for "no previous"
53        path.push(current);
54
55        while path.len() < n {
56            let next = adj[current]
57                .iter()
58                .find(|&&neighbor| neighbor != prev)
59                .copied();
60            match next {
61                Some(next_vertex) => {
62                    prev = current;
63                    current = next_vertex;
64                    path.push(current);
65                }
66                None => break,
67            }
68        }
69
70        path
71    }
72}
73
74#[reduction(overhead = {
75    num_vertices = "num_vertices",
76    num_edges = "num_edges",
77})]
78impl ReduceTo<LongestPath<SimpleGraph, One>> for HamiltonianPathBetweenTwoVertices<SimpleGraph> {
79    type Result = ReductionHPBTVToLP;
80
81    fn reduce_to(&self) -> Self::Result {
82        let graph = self.graph().clone();
83        let num_edges = graph.num_edges();
84        let edges = graph.edges();
85        let edge_lengths = vec![One; num_edges];
86
87        let target = LongestPath::new(
88            graph,
89            edge_lengths,
90            self.source_vertex(),
91            self.target_vertex(),
92        );
93
94        ReductionHPBTVToLP {
95            target,
96            edges,
97            source_vertex: self.source_vertex(),
98            num_vertices: self.num_vertices(),
99        }
100    }
101}
102
103#[cfg(feature = "example-db")]
104pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
105    use crate::export::SolutionPair;
106
107    vec![crate::example_db::specs::RuleExampleSpec {
108        id: "hamiltonianpathbetweentwovertices_to_longestpath",
109        build: || {
110            // Path graph 0-1-2-3-4 with s=0, t=4
111            let source = HamiltonianPathBetweenTwoVertices::new(
112                SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
113                0,
114                4,
115            );
116            crate::example_db::specs::rule_example_with_witness::<_, LongestPath<SimpleGraph, One>>(
117                source,
118                SolutionPair {
119                    source_config: vec![0, 1, 2, 3, 4],
120                    target_config: vec![1, 1, 1, 1],
121                },
122            )
123        },
124    }]
125}
126
127#[cfg(test)]
128#[path = "../unit_tests/rules/hamiltonianpathbetweentwovertices_longestpath.rs"]
129mod tests;
problemreductions/rules/hamiltonianpathbetweentwovertices_longestpath.rs

problemreductions/rules/
hamiltonianpathbetweentwovertices_longestpath.rs
