problemreductions/models/graph/
min_max_multicenter.rs

1//! Min-Max Multicenter (vertex p-center) problem implementation.
2//!
3//! The vertex p-center problem asks for K centers on vertices of a graph that
4//! minimize the maximum weighted distance from any vertex to its nearest center.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Min, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinMaxMulticenter",
16        display_name: "Min-Max Multicenter",
17        aliases: &["pCenter"],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20            VariantDimension::new("weight", "i32", &["i32", "One"]),
21        ],
22        module_path: module_path!(),
23        description: "Find K centers minimizing the maximum weighted distance from any vertex to its nearest center (vertex p-center)",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "vertex_weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
27            FieldInfo { name: "edge_lengths", type_name: "Vec<W>", description: "Edge lengths l: E -> R" },
28            FieldInfo { name: "k", type_name: "usize", description: "Number of centers to place" },
29        ],
30    }
31}
32
33/// The Min-Max Multicenter (vertex p-center) problem.
34///
35/// Given a graph G = (V, E) with vertex weights w(v) and edge lengths l(e),
36/// and a number K of centers to place, find a subset P of K vertices (centers)
37/// that minimizes max_{v in V} w(v) * d(v, P),
38/// where d(v, P) is the shortest-path distance from v to the nearest center.
39///
40/// # Type Parameters
41///
42/// * `G` - The graph type (e.g., `SimpleGraph`)
43/// * `W` - The weight/length type (e.g., `i32`)
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::MinMaxMulticenter;
49/// use problemreductions::topology::SimpleGraph;
50/// use problemreductions::{Problem, Solver, BruteForce};
51///
52/// // Hexagonal-like graph: 6 vertices, 7 edges, unit weights/lengths, K=2
53/// let graph = SimpleGraph::new(6, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 5), (1, 4)]);
54/// let problem = MinMaxMulticenter::new(graph, vec![1i32; 6], vec![1i32; 7], 2);
55///
56/// let solver = BruteForce::new();
57/// let solution = solver.find_witness(&problem);
58/// assert!(solution.is_some());
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct MinMaxMulticenter<G, W: WeightElement> {
62    /// The underlying graph.
63    graph: G,
64    /// Non-negative weight for each vertex.
65    vertex_weights: Vec<W>,
66    /// Non-negative length for each edge (in edge index order).
67    edge_lengths: Vec<W>,
68    /// Number of centers to place.
69    k: usize,
70}
71
72impl<G: Graph, W: WeightElement> MinMaxMulticenter<G, W> {
73    /// Create a MinMaxMulticenter problem.
74    ///
75    /// # Panics
76    /// - If `vertex_weights.len() != graph.num_vertices()`
77    /// - If `edge_lengths.len() != graph.num_edges()`
78    /// - If any vertex weight or edge length is negative
79    /// - If `k == 0` or `k > graph.num_vertices()`
80    pub fn new(graph: G, vertex_weights: Vec<W>, edge_lengths: Vec<W>, k: usize) -> Self {
81        assert_eq!(
82            vertex_weights.len(),
83            graph.num_vertices(),
84            "vertex_weights length must match num_vertices"
85        );
86        assert_eq!(
87            edge_lengths.len(),
88            graph.num_edges(),
89            "edge_lengths length must match num_edges"
90        );
91        let zero = W::Sum::zero();
92        assert!(
93            vertex_weights
94                .iter()
95                .all(|weight| weight.to_sum() >= zero.clone()),
96            "vertex_weights must be non-negative"
97        );
98        assert!(
99            edge_lengths
100                .iter()
101                .all(|length| length.to_sum() >= zero.clone()),
102            "edge_lengths must be non-negative"
103        );
104        assert!(k > 0, "k must be positive");
105        assert!(k <= graph.num_vertices(), "k must not exceed num_vertices");
106        Self {
107            graph,
108            vertex_weights,
109            edge_lengths,
110            k,
111        }
112    }
113
114    /// Get a reference to the underlying graph.
115    pub fn graph(&self) -> &G {
116        &self.graph
117    }
118
119    /// Get a reference to the vertex weights.
120    pub fn vertex_weights(&self) -> &[W] {
121        &self.vertex_weights
122    }
123
124    /// Get a reference to the edge lengths.
125    pub fn edge_lengths(&self) -> &[W] {
126        &self.edge_lengths
127    }
128
129    /// Get the number of centers K.
130    pub fn k(&self) -> usize {
131        self.k
132    }
133
134    /// Get the number of vertices in the underlying graph.
135    pub fn num_vertices(&self) -> usize {
136        self.graph().num_vertices()
137    }
138
139    /// Get the number of edges in the underlying graph.
140    pub fn num_edges(&self) -> usize {
141        self.graph().num_edges()
142    }
143
144    /// Get the number of centers K.
145    pub fn num_centers(&self) -> usize {
146        self.k
147    }
148
149    /// Compute shortest distances from each vertex to the nearest center.
150    ///
151    /// Uses multi-source Dijkstra with linear scan: initializes all centers
152    /// at distance 0 and greedily relaxes edges by increasing distance.
153    /// Correct because all edge lengths are non-negative.
154    ///
155    /// Returns `None` if any vertex is unreachable from all centers.
156    fn shortest_distances(&self, config: &[usize]) -> Option<Vec<W::Sum>> {
157        let n = self.graph.num_vertices();
158        if config.len() != n || config.iter().any(|&selected| selected > 1) {
159            return None;
160        }
161        let edges = self.graph.edges();
162
163        let mut adj: Vec<Vec<(usize, W::Sum)>> = vec![Vec::new(); n];
164        for (idx, &(u, v)) in edges.iter().enumerate() {
165            let len = self.edge_lengths[idx].to_sum();
166            adj[u].push((v, len.clone()));
167            adj[v].push((u, len));
168        }
169
170        // Multi-source Dijkstra with linear scan (works with PartialOrd)
171        let mut dist: Vec<Option<W::Sum>> = vec![None; n];
172        let mut visited = vec![false; n];
173
174        // Initialize centers
175        for (v, &selected) in config.iter().enumerate() {
176            if selected == 1 {
177                dist[v] = Some(W::Sum::zero());
178            }
179        }
180
181        for _ in 0..n {
182            // Find unvisited vertex with smallest distance
183            let mut u = None;
184            for v in 0..n {
185                if visited[v] {
186                    continue;
187                }
188                if let Some(ref dv) = dist[v] {
189                    match u {
190                        None => u = Some(v),
191                        Some(prev) => {
192                            if *dv < dist[prev].clone().unwrap() {
193                                u = Some(v);
194                            }
195                        }
196                    }
197                }
198            }
199            let u = match u {
200                Some(v) => v,
201                None => break, // remaining vertices are unreachable
202            };
203            visited[u] = true;
204
205            let du = dist[u].clone().unwrap();
206            for &(next, ref len) in &adj[u] {
207                if visited[next] {
208                    continue;
209                }
210                let new_dist = du.clone() + len.clone();
211                let update = match &dist[next] {
212                    None => true,
213                    Some(d) => new_dist < *d,
214                };
215                if update {
216                    dist[next] = Some(new_dist);
217                }
218            }
219        }
220
221        dist.into_iter().collect()
222    }
223}
224
225impl<G, W> Problem for MinMaxMulticenter<G, W>
226where
227    G: Graph + crate::variant::VariantParam,
228    W: WeightElement + crate::variant::VariantParam,
229{
230    const NAME: &'static str = "MinMaxMulticenter";
231    type Value = Min<W::Sum>;
232
233    fn variant() -> Vec<(&'static str, &'static str)> {
234        crate::variant_params![G, W]
235    }
236
237    fn dims(&self) -> Vec<usize> {
238        vec![2; self.graph.num_vertices()]
239    }
240
241    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
242        if config.len() != self.graph.num_vertices() || config.iter().any(|&selected| selected > 1)
243        {
244            return Min(None);
245        }
246
247        // Check exactly K centers are selected
248        let num_selected = config.iter().filter(|&&selected| selected == 1).count();
249        if num_selected != self.k {
250            return Min(None);
251        }
252
253        // Compute shortest distances to nearest center
254        let distances = match self.shortest_distances(config) {
255            Some(d) => d,
256            None => {
257                return Min(None);
258            }
259        };
260
261        // Compute max weighted distance: max_{v} w(v) * d(v)
262        let mut max_wd = W::Sum::zero();
263        for (v, dist) in distances.iter().enumerate() {
264            let wd = self.vertex_weights[v].to_sum() * dist.clone();
265            if wd > max_wd {
266                max_wd = wd;
267            }
268        }
269
270        Min(Some(max_wd))
271    }
272}
273
274crate::declare_variants! {
275    default MinMaxMulticenter<SimpleGraph, i32> => "1.4969^num_vertices",
276    MinMaxMulticenter<SimpleGraph, crate::types::One> => "1.4969^num_vertices",
277}
278
279#[cfg(feature = "example-db")]
280pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
281    vec![crate::example_db::specs::ModelExampleSpec {
282        id: "min_max_multicenter_simplegraph_i32",
283        instance: Box::new(MinMaxMulticenter::new(
284            SimpleGraph::new(
285                6,
286                vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 5), (1, 4)],
287            ),
288            vec![1i32; 6],
289            vec![1i32; 7],
290            2,
291        )),
292        optimal_config: vec![0, 1, 0, 0, 1, 0],
293        optimal_value: serde_json::json!(1),
294    }]
295}
296
297#[cfg(test)]
298#[path = "../../unit_tests/models/graph/min_max_multicenter.rs"]
299mod tests;
problemreductions/models/graph/min_max_multicenter.rs

problemreductions/models/graph/
min_max_multicenter.rs
