problemreductions/models/graph/
bottleneck_traveling_salesman.rs

1//! Bottleneck Traveling Salesman problem implementation.
2//!
3//! The Bottleneck Traveling Salesman problem asks for a Hamiltonian cycle
4//! minimizing the maximum selected edge weight.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "BottleneckTravelingSalesman",
15        display_name: "Bottleneck Traveling Salesman",
16        aliases: &[],
17        dimensions: &[],
18        module_path: module_path!(),
19        description: "Find a Hamiltonian cycle minimizing the maximum selected edge weight",
20        fields: &[
21            FieldInfo { name: "graph", type_name: "SimpleGraph", description: "The underlying graph G=(V,E)" },
22            FieldInfo { name: "edge_weights", type_name: "Vec<i32>", description: "Edge weights w: E -> Z" },
23        ],
24    }
25}
26
27/// The Bottleneck Traveling Salesman problem on a simple weighted graph.
28#[derive(Debug, Clone, Serialize, Deserialize)]
29pub struct BottleneckTravelingSalesman {
30    graph: SimpleGraph,
31    edge_weights: Vec<i32>,
32}
33
34impl BottleneckTravelingSalesman {
35    /// Create a BottleneckTravelingSalesman problem from a graph with edge weights.
36    pub fn new(graph: SimpleGraph, edge_weights: Vec<i32>) -> Self {
37        assert_eq!(
38            edge_weights.len(),
39            graph.num_edges(),
40            "edge_weights length must match num_edges"
41        );
42        Self {
43            graph,
44            edge_weights,
45        }
46    }
47
48    /// Get a reference to the underlying graph.
49    pub fn graph(&self) -> &SimpleGraph {
50        &self.graph
51    }
52
53    /// Get the weights for the problem.
54    pub fn weights(&self) -> Vec<i32> {
55        self.edge_weights.clone()
56    }
57
58    /// Set new weights for the problem.
59    pub fn set_weights(&mut self, weights: Vec<i32>) {
60        assert_eq!(weights.len(), self.graph.num_edges());
61        self.edge_weights = weights;
62    }
63
64    /// Get all edges with their weights.
65    pub fn edges(&self) -> Vec<(usize, usize, i32)> {
66        self.graph
67            .edges()
68            .into_iter()
69            .zip(self.edge_weights.iter().copied())
70            .map(|((u, v), w)| (u, v, w))
71            .collect()
72    }
73
74    /// Get the number of vertices in the underlying graph.
75    pub fn num_vertices(&self) -> usize {
76        self.graph.num_vertices()
77    }
78
79    /// Get the number of edges in the underlying graph.
80    pub fn num_edges(&self) -> usize {
81        self.graph.num_edges()
82    }
83
84    /// This model is always weighted.
85    pub fn is_weighted(&self) -> bool {
86        true
87    }
88
89    /// Check if a configuration is a valid Hamiltonian cycle.
90    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
91        if config.len() != self.graph.num_edges() {
92            return false;
93        }
94        let selected: Vec<bool> = config.iter().map(|&s| s == 1).collect();
95        super::traveling_salesman::is_hamiltonian_cycle(&self.graph, &selected)
96    }
97}
98
99impl Problem for BottleneckTravelingSalesman {
100    const NAME: &'static str = "BottleneckTravelingSalesman";
101    type Value = Min<i32>;
102
103    fn variant() -> Vec<(&'static str, &'static str)> {
104        crate::variant_params![]
105    }
106
107    fn dims(&self) -> Vec<usize> {
108        vec![2; self.graph.num_edges()]
109    }
110
111    fn evaluate(&self, config: &[usize]) -> Min<i32> {
112        if config.len() != self.graph.num_edges() {
113            return Min(None);
114        }
115
116        let selected: Vec<bool> = config.iter().map(|&s| s == 1).collect();
117        if !super::traveling_salesman::is_hamiltonian_cycle(&self.graph, &selected) {
118            return Min(None);
119        }
120
121        let bottleneck = config
122            .iter()
123            .zip(self.edge_weights.iter())
124            .filter_map(|(&selected, &weight)| (selected == 1).then_some(weight))
125            .max()
126            .expect("valid Hamiltonian cycle selects at least one edge");
127
128        Min(Some(bottleneck))
129    }
130}
131
132#[cfg(feature = "example-db")]
133pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
134    vec![crate::example_db::specs::ModelExampleSpec {
135        id: "bottleneck_traveling_salesman",
136        instance: Box::new(BottleneckTravelingSalesman::new(
137            SimpleGraph::new(
138                5,
139                vec![
140                    (0, 1),
141                    (0, 2),
142                    (0, 3),
143                    (0, 4),
144                    (1, 2),
145                    (1, 3),
146                    (1, 4),
147                    (2, 3),
148                    (2, 4),
149                    (3, 4),
150                ],
151            ),
152            vec![5, 4, 4, 5, 4, 1, 2, 1, 5, 4],
153        )),
154        optimal_config: vec![0, 1, 1, 0, 1, 0, 1, 0, 0, 1],
155        optimal_value: serde_json::json!(4),
156    }]
157}
158
159crate::declare_variants! {
160    default BottleneckTravelingSalesman => "num_vertices^2 * 2^num_vertices",
161}
162
163#[cfg(test)]
164#[path = "../../unit_tests/models/graph/bottleneck_traveling_salesman.rs"]
165mod tests;
problemreductions/models/graph/bottleneck_traveling_salesman.rs

problemreductions/models/graph/
bottleneck_traveling_salesman.rs
