problemreductions/models/graph/
minimum_graph_bandwidth.rs

1//! Minimum Graph Bandwidth problem implementation.
2//!
3//! The Minimum Graph Bandwidth problem asks for a bijection
4//! f: V -> {0, 1, ..., |V|-1} that minimizes the maximum edge stretch
5//! max_{(u,v) in E} |f(u) - f(v)|.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
8use crate::topology::{Graph, SimpleGraph};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumGraphBandwidth",
16        display_name: "Minimum Graph Bandwidth",
17        aliases: &["MGB"],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        module_path: module_path!(),
22        description: "Find a vertex ordering minimizing the maximum edge stretch",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
25        ],
26    }
27}
28
29/// The Minimum Graph Bandwidth problem.
30///
31/// Given an undirected graph G = (V, E), find a bijection f: V -> {0, 1, ..., |V|-1}
32/// that minimizes the bandwidth max_{(u,v) in E} |f(u) - f(v)|.
33///
34/// # Representation
35///
36/// Each vertex is assigned a variable representing its position in the arrangement.
37/// Variable i takes a value in {0, 1, ..., n-1}, and a valid configuration must be
38/// a permutation (all positions are distinct). The objective is to minimize the
39/// maximum edge stretch.
40///
41/// # Type Parameters
42///
43/// * `G` - The graph type (e.g., `SimpleGraph`)
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::MinimumGraphBandwidth;
49/// use problemreductions::topology::SimpleGraph;
50/// use problemreductions::{Problem, Solver, BruteForce};
51///
52/// // Star graph S4: center 0 connected to 1, 2, 3
53/// let graph = SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]);
54/// let problem = MinimumGraphBandwidth::new(graph);
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)]
61#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
62pub struct MinimumGraphBandwidth<G> {
63    /// The underlying graph.
64    graph: G,
65}
66
67impl<G: Graph> MinimumGraphBandwidth<G> {
68    /// Create a new Minimum Graph Bandwidth problem.
69    ///
70    /// # Arguments
71    /// * `graph` - The undirected graph G = (V, E)
72    pub fn new(graph: G) -> Self {
73        Self { graph }
74    }
75
76    /// Get a reference to the underlying graph.
77    pub fn graph(&self) -> &G {
78        &self.graph
79    }
80
81    /// Get the number of vertices in the underlying graph.
82    pub fn num_vertices(&self) -> usize {
83        self.graph.num_vertices()
84    }
85
86    /// Get the number of edges in the underlying graph.
87    pub fn num_edges(&self) -> usize {
88        self.graph.num_edges()
89    }
90
91    /// Check if a configuration forms a valid permutation of {0, ..., n-1}.
92    fn is_valid_permutation(&self, config: &[usize]) -> bool {
93        let n = self.graph.num_vertices();
94        if config.len() != n {
95            return false;
96        }
97        let mut seen = vec![false; n];
98        for &pos in config {
99            if pos >= n || seen[pos] {
100                return false;
101            }
102            seen[pos] = true;
103        }
104        true
105    }
106
107    /// Compute the bandwidth (maximum edge stretch) for a given arrangement.
108    ///
109    /// Returns `None` if the configuration is not a valid permutation.
110    pub fn bandwidth(&self, config: &[usize]) -> Option<usize> {
111        if !self.is_valid_permutation(config) {
112            return None;
113        }
114        let mut max_stretch = 0usize;
115        for (u, v) in self.graph.edges() {
116            let stretch = config[u].abs_diff(config[v]);
117            max_stretch = max_stretch.max(stretch);
118        }
119        Some(max_stretch)
120    }
121}
122
123impl<G> Problem for MinimumGraphBandwidth<G>
124where
125    G: Graph + crate::variant::VariantParam,
126{
127    const NAME: &'static str = "MinimumGraphBandwidth";
128    type Value = Min<usize>;
129
130    fn variant() -> Vec<(&'static str, &'static str)> {
131        crate::variant_params![G]
132    }
133
134    fn dims(&self) -> Vec<usize> {
135        let n = self.graph.num_vertices();
136        vec![n; n]
137    }
138
139    fn evaluate(&self, config: &[usize]) -> Min<usize> {
140        match self.bandwidth(config) {
141            Some(bw) => Min(Some(bw)),
142            None => Min(None),
143        }
144    }
145}
146
147crate::declare_variants! {
148    default MinimumGraphBandwidth<SimpleGraph> => "factorial(num_vertices)",
149}
150
151#[cfg(feature = "example-db")]
152pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
153    use crate::topology::SimpleGraph;
154    // Star graph S4: center 0 connected to 1, 2, 3
155    // Config [1,0,2,3]: f(0)=1, f(1)=0, f(2)=2, f(3)=3
156    // Bandwidth = max(|1-0|, |1-2|, |1-3|) = max(1, 1, 2) = 2
157    // Optimal bandwidth for S4 is 2 (center must be adjacent to all leaves,
158    // placing center at position 1 achieves max stretch 2).
159    vec![crate::example_db::specs::ModelExampleSpec {
160        id: "minimum_graph_bandwidth",
161        instance: Box::new(MinimumGraphBandwidth::new(SimpleGraph::new(
162            4,
163            vec![(0, 1), (0, 2), (0, 3)],
164        ))),
165        optimal_config: vec![1, 0, 2, 3],
166        optimal_value: serde_json::json!(2),
167    }]
168}
169
170#[cfg(test)]
171#[path = "../../unit_tests/models/graph/minimum_graph_bandwidth.rs"]
172mod tests;
problemreductions/models/graph/minimum_graph_bandwidth.rs

problemreductions/models/graph/
minimum_graph_bandwidth.rs
