problemreductions/models/graph/
minimum_metric_dimension.rs

1//! Minimum Metric Dimension problem implementation.
2//!
3//! Given a graph G = (V, E), find a minimum resolving set — a smallest subset
4//! V' ⊆ V such that for all distinct u, v ∈ V, there exists w ∈ V' with
5//! d(u, w) ≠ d(v, w), where d denotes shortest-path distance.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MinimumMetricDimension",
17        display_name: "Minimum Metric Dimension",
18        aliases: &[],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21        ],
22        category: crate::registry::ProblemCategory::Graph,
23        module_path: module_path!(),
24        description: "Find minimum resolving set of a graph",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
27        ],
28    }
29}
30
31/// Compute BFS shortest-path distances from a single source vertex.
32///
33/// Returns a vector where `dist[v]` is the shortest-path distance from
34/// `source` to `v`, or `usize::MAX` if `v` is unreachable.
35pub fn bfs_distances<G: Graph>(graph: &G, source: usize) -> Vec<usize> {
36    let n = graph.num_vertices();
37    let mut dist = vec![usize::MAX; n];
38    dist[source] = 0;
39    let mut queue = VecDeque::new();
40    queue.push_back(source);
41    while let Some(u) = queue.pop_front() {
42        for v in graph.neighbors(u) {
43            if dist[v] == usize::MAX {
44                dist[v] = dist[u] + 1;
45                queue.push_back(v);
46            }
47        }
48    }
49    dist
50}
51
52/// The Minimum Metric Dimension problem.
53///
54/// Given a graph G = (V, E), find a minimum-size resolving set V' ⊆ V such
55/// that for every pair of distinct vertices u, v ∈ V, there exists at least
56/// one vertex w ∈ V' with d(u, w) ≠ d(v, w).
57///
58/// # Type Parameters
59///
60/// * `G` - The graph type (e.g., `SimpleGraph`)
61///
62/// # Example
63///
64/// ```
65/// use problemreductions::models::graph::MinimumMetricDimension;
66/// use problemreductions::topology::SimpleGraph;
67/// use problemreductions::{Problem, BruteForce};
68///
69/// // House graph: vertices 0–4
70/// let graph = SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]);
71/// let problem = MinimumMetricDimension::new(graph);
72///
73/// let solver = BruteForce::new();
74/// let solution = solver.solve(&problem).unwrap().unwrap();
75/// let value = problem.evaluate(&solution).unwrap();
76/// assert!(value.is_valid());
77/// ```
78#[derive(Debug, Clone, Serialize)]
79pub struct MinimumMetricDimension<G> {
80    /// The underlying graph.
81    graph: G,
82    /// Precomputed all-pairs shortest-path distances.
83    #[serde(skip)]
84    dist_matrix: Vec<Vec<usize>>,
85}
86
87impl<'de, G: Graph + Deserialize<'de>> Deserialize<'de> for MinimumMetricDimension<G> {
88    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
89    where
90        D: serde::Deserializer<'de>,
91    {
92        #[derive(Deserialize)]
93        struct Helper<G> {
94            graph: G,
95        }
96        let helper = Helper::<G>::deserialize(deserializer)?;
97        Ok(Self::new(helper.graph))
98    }
99}
100
101impl<G: Graph> MinimumMetricDimension<G> {
102    /// Create a MinimumMetricDimension problem from a graph.
103    pub fn new(graph: G) -> Self {
104        let n = graph.num_vertices();
105        let dist_matrix = (0..n).map(|v| bfs_distances(&graph, v)).collect();
106        Self { graph, dist_matrix }
107    }
108
109    /// Get a reference to the underlying graph.
110    pub fn graph(&self) -> &G {
111        &self.graph
112    }
113
114    /// Get the number of vertices in the underlying graph.
115    pub fn num_vertices(&self) -> usize {
116        self.graph.num_vertices()
117    }
118
119    /// Get the number of edges in the underlying graph.
120    pub fn num_edges(&self) -> usize {
121        self.graph.num_edges()
122    }
123
124    /// Check whether a configuration (binary vertex selection) forms a resolving set.
125    ///
126    /// A set S ⊆ V is resolving if for every pair of distinct vertices u, v ∈ V,
127    /// there exists some w ∈ S such that d(u, w) ≠ d(v, w).
128    pub fn is_resolving(&self, config: &[bool]) -> bool {
129        let n = self.graph.num_vertices();
130        let selected: Vec<usize> = (0..n).filter(|&i| config[i]).collect();
131        if selected.is_empty() {
132            return false;
133        }
134
135        // Check that all pairs of distinct vertices have different distance vectors
136        // using precomputed all-pairs distances
137        for u in 0..n {
138            for v in (u + 1)..n {
139                let all_same = selected
140                    .iter()
141                    .all(|&w| self.dist_matrix[w][u] == self.dist_matrix[w][v]);
142                if all_same {
143                    return false;
144                }
145            }
146        }
147
148        true
149    }
150}
151
152impl<G> Problem for MinimumMetricDimension<G>
153where
154    G: Graph + crate::variant::VariantParam,
155{
156    const NAME: &'static str = "MinimumMetricDimension";
157    type Solution = Vec<bool>;
158    type Value = Min<i64>;
159
160    crate::problem_parameters![("num_vertices", num_vertices),];
161
162    fn variant() -> Vec<(&'static str, &'static str)> {
163        crate::variant_params![G]
164    }
165
166    fn evaluate(
167        &self,
168        config: &Self::Solution,
169    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
170        if config.len() != self.graph.num_vertices() {
171            return Err(crate::traits::EvaluationError::InvalidConfiguration(
172                "vertex-selection length does not match the graph".into(),
173            ));
174        }
175        Ok({
176            if !self.is_resolving(config) {
177                return Ok(Min(None));
178            }
179            let count = config.iter().filter(|&&x| x).count();
180            Min(Some(i64::try_from(count).map_err(|_| {
181                crate::traits::EvaluationError::IntegerOverflow(
182                    "converting metric-basis size to i64".into(),
183                )
184            })?))
185        })
186    }
187}
188
189impl<G> crate::solvers::BruteForceProblem for MinimumMetricDimension<G>
190where
191    G: Graph + crate::variant::VariantParam,
192{
193    fn dimensions(&self) -> Vec<usize> {
194        vec![2; self.graph.num_vertices()]
195    }
196}
197
198crate::declare_variants! {
199    default MinimumMetricDimension<SimpleGraph> => "2^num_vertices",
200}
201
202crate::register_brute_force! {
203    MinimumMetricDimension<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
204}
205
206#[cfg(feature = "example-db")]
207pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
208    vec![crate::example_db::specs::ModelExampleSpec {
209        id: "minimum_metric_dimension_simplegraph",
210        instance: Box::new(MinimumMetricDimension::new(SimpleGraph::new(
211            5,
212            vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)],
213        ))),
214        optimal_config: serde_json::json!(vec![true, true, false, false, false]),
215        optimal_value: serde_json::json!(2),
216    }]
217}
218
219#[cfg(test)]
220#[path = "../../unit_tests/models/graph/minimum_metric_dimension.rs"]
221mod tests;
problemreductions/models/graph/minimum_metric_dimension.rs

problemreductions/models/graph/
minimum_metric_dimension.rs
