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        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find a vertex ordering minimizing the maximum edge stretch",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
26        ],
27    }
28}
29
30/// The Minimum Graph Bandwidth problem.
31///
32/// Given an undirected graph G = (V, E), find a bijection f: V -> {0, 1, ..., |V|-1}
33/// that minimizes the bandwidth max_{(u,v) in E} |f(u) - f(v)|.
34///
35/// # Representation
36///
37/// Each vertex is assigned a variable representing its position in the arrangement.
38/// Variable i takes a value in {0, 1, ..., n-1}, and a valid configuration must be
39/// a permutation (all positions are distinct). The objective is to minimize the
40/// maximum edge stretch.
41///
42/// # Type Parameters
43///
44/// * `G` - The graph type (e.g., `SimpleGraph`)
45///
46/// # Example
47///
48/// ```
49/// use problemreductions::models::graph::MinimumGraphBandwidth;
50/// use problemreductions::topology::SimpleGraph;
51/// use problemreductions::{Problem, BruteForce};
52///
53/// // Star graph S4: center 0 connected to 1, 2, 3
54/// let graph = SimpleGraph::new(4, vec![(0, 1), (0, 2), (0, 3)]);
55/// let problem = MinimumGraphBandwidth::new(graph);
56///
57/// let solver = BruteForce::new();
58/// let solution = solver.solve(&problem).unwrap();
59/// assert!(solution.is_some());
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
63pub struct MinimumGraphBandwidth<G> {
64    /// The underlying graph.
65    graph: G,
66}
67
68impl<G: Graph> MinimumGraphBandwidth<G> {
69    /// Create a new Minimum Graph Bandwidth problem.
70    ///
71    /// # Arguments
72    /// * `graph` - The undirected graph G = (V, E)
73    pub fn new(graph: G) -> Self {
74        Self { graph }
75    }
76
77    /// Get a reference to the underlying graph.
78    pub fn graph(&self) -> &G {
79        &self.graph
80    }
81
82    /// Get the number of vertices in the underlying graph.
83    pub fn num_vertices(&self) -> usize {
84        self.graph.num_vertices()
85    }
86
87    /// Get the number of edges in the underlying graph.
88    pub fn num_edges(&self) -> usize {
89        self.graph.num_edges()
90    }
91
92    /// Check if a configuration forms a valid permutation of {0, ..., n-1}.
93    fn is_valid_permutation(&self, config: &[usize]) -> bool {
94        let n = self.graph.num_vertices();
95        if config.len() != n {
96            return false;
97        }
98        let mut seen = vec![false; n];
99        for &pos in config {
100            if pos >= n || seen[pos] {
101                return false;
102            }
103            seen[pos] = true;
104        }
105        true
106    }
107
108    /// Compute the bandwidth (maximum edge stretch) for a given arrangement.
109    ///
110    /// Returns `None` if the configuration is not a valid permutation.
111    pub fn bandwidth(
112        &self,
113        config: &[usize],
114    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
115        if !self.is_valid_permutation(config) {
116            return Ok(None);
117        }
118        let mut max_stretch = 0usize;
119        for (u, v) in self.graph.edges() {
120            let stretch = config[u].abs_diff(config[v]);
121            max_stretch = max_stretch.max(stretch);
122        }
123        Ok(Some(i64::try_from(max_stretch).map_err(|_| {
124            crate::traits::EvaluationError::IntegerOverflow(
125                "converting graph bandwidth to i64".to_string(),
126            )
127        })?))
128    }
129}
130
131impl<G> Problem for MinimumGraphBandwidth<G>
132where
133    G: Graph + crate::variant::VariantParam,
134{
135    const NAME: &'static str = "MinimumGraphBandwidth";
136    type Solution = Vec<usize>;
137    type Value = Min<i64>;
138
139    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
140
141    fn variant() -> Vec<(&'static str, &'static str)> {
142        crate::variant_params![G]
143    }
144
145    fn evaluate(
146        &self,
147        config: &Self::Solution,
148    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
149        let n = self.graph.num_vertices();
150        if config.len() != n {
151            return Err(crate::traits::EvaluationError::InvalidConfiguration(
152                "vertex ordering length does not match the graph".into(),
153            ));
154        }
155        if config.iter().any(|&position| position >= n) {
156            return Err(crate::traits::EvaluationError::InvalidConfiguration(
157                "vertex ordering contains an out-of-range position".into(),
158            ));
159        }
160        Ok({
161            match self.bandwidth(config)? {
162                Some(bw) => Min(Some(bw)),
163                None => Min(None),
164            }
165        })
166    }
167}
168
169impl<G> crate::solvers::BruteForceProblem for MinimumGraphBandwidth<G>
170where
171    G: Graph + crate::variant::VariantParam,
172{
173    fn dimensions(&self) -> Vec<usize> {
174        let n = self.graph.num_vertices();
175        vec![n; n]
176    }
177}
178
179crate::declare_variants! {
180    default MinimumGraphBandwidth<SimpleGraph> => "factorial(num_vertices)",
181}
182
183crate::register_brute_force! {
184    MinimumGraphBandwidth<SimpleGraph>,
185}
186
187#[cfg(feature = "example-db")]
188pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
189    use crate::topology::SimpleGraph;
190    // Star graph S4: center 0 connected to 1, 2, 3
191    // Config [1,0,2,3]: f(0)=1, f(1)=0, f(2)=2, f(3)=3
192    // Bandwidth = max(|1-0|, |1-2|, |1-3|) = max(1, 1, 2) = 2
193    // Optimal bandwidth for S4 is 2 (center must be adjacent to all leaves,
194    // placing center at position 1 achieves max stretch 2).
195    vec![crate::example_db::specs::ModelExampleSpec {
196        id: "minimum_graph_bandwidth",
197        instance: Box::new(MinimumGraphBandwidth::new(SimpleGraph::new(
198            4,
199            vec![(0, 1), (0, 2), (0, 3)],
200        ))),
201        optimal_config: serde_json::json!(vec![1, 0, 2, 3]),
202        optimal_value: serde_json::json!(2),
203    }]
204}
205
206#[cfg(test)]
207#[path = "../../unit_tests/models/graph/minimum_graph_bandwidth.rs"]
208mod tests;
problemreductions/models/graph/minimum_graph_bandwidth.rs

problemreductions/models/graph/
minimum_graph_bandwidth.rs
