problemreductions/models/graph/
optimal_linear_arrangement.rs

1//! Optimal Linear Arrangement problem implementation.
2//!
3//! The Optimal Linear Arrangement problem asks for a one-to-one function
4//! f: V -> {0, 1, ..., |V|-1} that minimizes the total edge length
5//! sum_{{u,v} in E} |f(u) - f(v)|.
6
7use crate::models::decision::Decision;
8use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
9use crate::topology::{Graph, SimpleGraph};
10use crate::traits::Problem;
11use crate::types::Min;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "OptimalLinearArrangement",
17        display_name: "Optimal Linear Arrangement",
18        aliases: &["OLA"],
19        dimensions: &[
20            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
21        ],
22        category: crate::registry::ProblemCategory::Graph,
23        module_path: module_path!(),
24        description: "Find a vertex ordering on a line minimizing total edge length",
25        fields: &[
26            FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
27        ],
28    }
29}
30
31/// The Optimal Linear Arrangement problem.
32///
33/// Given an undirected graph G = (V, E), find a bijection f: V -> {0, 1, ..., |V|-1}
34/// that minimizes the total edge length sum_{{u,v} in E} |f(u) - f(v)|.
35///
36/// This is the optimization (minimization) version of the problem.
37///
38/// # Representation
39///
40/// Each vertex is assigned a variable representing its position in the arrangement.
41/// Variable i takes a value in {0, 1, ..., n-1}, and a valid configuration must be
42/// a permutation (all positions are distinct). The objective is to minimize total
43/// edge length.
44///
45/// # Type Parameters
46///
47/// * `G` - The graph type (e.g., `SimpleGraph`)
48///
49/// # Example
50///
51/// ```
52/// use problemreductions::models::graph::OptimalLinearArrangement;
53/// use problemreductions::topology::SimpleGraph;
54/// use problemreductions::{Problem, BruteForce};
55///
56/// // Path graph: 0-1-2-3
57/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
58/// let problem = OptimalLinearArrangement::new(graph);
59///
60/// let solver = BruteForce::new();
61/// let solution = solver.solve(&problem).unwrap();
62/// assert!(solution.is_some());
63/// ```
64#[derive(Debug, Clone, Serialize, Deserialize)]
65#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
66pub struct OptimalLinearArrangement<G> {
67    /// The underlying graph.
68    graph: G,
69}
70
71impl<G: Graph> OptimalLinearArrangement<G> {
72    /// Create a new Optimal Linear Arrangement problem.
73    ///
74    /// # Arguments
75    /// * `graph` - The undirected graph G = (V, E)
76    pub fn new(graph: G) -> Self {
77        Self { graph }
78    }
79
80    /// Get a reference to the underlying graph.
81    pub fn graph(&self) -> &G {
82        &self.graph
83    }
84
85    /// Get the number of vertices in the underlying graph.
86    pub fn num_vertices(&self) -> usize {
87        self.graph.num_vertices()
88    }
89
90    /// Get the number of edges in the underlying graph.
91    pub fn num_edges(&self) -> usize {
92        self.graph.num_edges()
93    }
94
95    /// Check if a configuration is a valid permutation.
96    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
97        self.is_valid_permutation(config)
98    }
99
100    /// Check if a configuration forms a valid permutation of {0, ..., n-1}.
101    fn is_valid_permutation(&self, config: &[usize]) -> bool {
102        let n = self.graph.num_vertices();
103        if config.len() != n {
104            return false;
105        }
106        let mut seen = vec![false; n];
107        for &pos in config {
108            if pos >= n || seen[pos] {
109                return false;
110            }
111            seen[pos] = true;
112        }
113        true
114    }
115
116    /// Compute the total edge length for a given arrangement.
117    ///
118    /// Returns `None` if the configuration is not a valid permutation.
119    pub fn total_edge_length(
120        &self,
121        config: &[usize],
122    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
123        if !self.is_valid_permutation(config) {
124            return Ok(None);
125        }
126        let mut total = 0_i64;
127        for (u, v) in self.graph.edges() {
128            let fu = config[u];
129            let fv = config[v];
130            let length = i64::try_from(fu.abs_diff(fv)).map_err(|_| {
131                crate::traits::EvaluationError::IntegerOverflow(
132                    "converting linear-arrangement edge length to i64".to_string(),
133                )
134            })?;
135            total = total.checked_add(length).ok_or_else(|| {
136                crate::traits::EvaluationError::IntegerOverflow(
137                    "summing linear-arrangement edge lengths".to_string(),
138                )
139            })?;
140        }
141        Ok(Some(total))
142    }
143}
144
145impl<G> Problem for OptimalLinearArrangement<G>
146where
147    G: Graph + crate::variant::VariantParam,
148{
149    const NAME: &'static str = "OptimalLinearArrangement";
150    type Solution = Vec<usize>;
151    type Value = Min<i64>;
152
153    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
154
155    fn variant() -> Vec<(&'static str, &'static str)> {
156        crate::variant_params![G]
157    }
158
159    fn evaluate(
160        &self,
161        config: &Self::Solution,
162    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
163        let n = self.graph.num_vertices();
164        if config.len() != n {
165            return Err(crate::traits::EvaluationError::InvalidConfiguration(
166                "vertex arrangement length does not match the graph".into(),
167            ));
168        }
169        if config.iter().any(|&position| position >= n) {
170            return Err(crate::traits::EvaluationError::InvalidConfiguration(
171                "vertex arrangement contains an out-of-range position".into(),
172            ));
173        }
174        Ok({
175            match self.total_edge_length(config)? {
176                Some(cost) => Min(Some(cost)),
177                None => Min(None),
178            }
179        })
180    }
181}
182
183impl<G> crate::solvers::BruteForceProblem for OptimalLinearArrangement<G>
184where
185    G: Graph + crate::variant::VariantParam,
186{
187    fn dimensions(&self) -> Vec<usize> {
188        let n = self.graph.num_vertices();
189        vec![n; n]
190    }
191}
192
193crate::impl_random_generate!(
194    OptimalLinearArrangement<SimpleGraph>,
195    crate::random::SimpleGraphRandomSpec,
196    |spec| { Ok(OptimalLinearArrangement::new(spec.graph()?)) }
197);
198
199crate::declare_variants! {
200    default OptimalLinearArrangement<SimpleGraph> => "2^num_vertices" random,
201}
202
203crate::register_brute_force! {
204    OptimalLinearArrangement<SimpleGraph>,
205}
206
207impl<G> crate::models::decision::DecisionProblemMeta for OptimalLinearArrangement<G>
208where
209    G: Graph + crate::variant::VariantParam,
210{
211    const DECISION_NAME: &'static str = "DecisionOptimalLinearArrangement";
212}
213
214impl Decision<OptimalLinearArrangement<SimpleGraph>> {
215    /// Number of vertices in the underlying graph.
216    pub fn num_vertices(&self) -> usize {
217        self.inner().num_vertices()
218    }
219
220    /// Number of edges in the underlying graph.
221    pub fn num_edges(&self) -> usize {
222        self.inner().num_edges()
223    }
224
225    /// Decision bound (maximum allowed total edge length) as a nonnegative integer.
226    pub fn k(&self) -> usize {
227        usize::try_from(*self.bound()).expect("nonnegative decision bound must fit usize")
228    }
229}
230
231crate::register_decision_variant!(
232    OptimalLinearArrangement<SimpleGraph>,
233    "DecisionOptimalLinearArrangement",
234    "2^num_vertices",
235    &["DOLA"],
236    "Decision version: does a linear arrangement of total edge length <= bound exist?",
237    category: crate::registry::ProblemCategory::Graph,
238    dims: [
239        VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
240    ],
241    fields: [
242        FieldInfo { name: "graph", type_name: "G", description: "The undirected graph G=(V,E)" },
243        FieldInfo { name: "bound", type_name: "i64", description: "Decision bound (maximum allowed total edge length)" },
244    ],
245    decode: |_, indices: Vec<usize>| indices
246);
247
248#[cfg(feature = "example-db")]
249pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
250    use crate::topology::SimpleGraph;
251    // 6 vertices, 7 edges (path + two long chords)
252    // Optimal arrangement [0,1,2,3,4,5] gives cost 1+1+1+1+1+3+3 = 11
253    vec![crate::example_db::specs::ModelExampleSpec {
254        id: "optimal_linear_arrangement",
255        instance: Box::new(OptimalLinearArrangement::new(SimpleGraph::new(
256            6,
257            vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 3), (2, 5)],
258        ))),
259        optimal_config: serde_json::json!(vec![0, 1, 2, 3, 4, 5]),
260        optimal_value: serde_json::json!(11),
261    }]
262}
263
264#[cfg(feature = "example-db")]
265pub(crate) fn decision_canonical_model_example_specs(
266) -> Vec<crate::example_db::specs::ModelExampleSpec> {
267    use crate::topology::SimpleGraph;
268    // Path P_4 (0-1-2-3): optimal arrangement has cost 3; bound 3 is YES.
269    vec![crate::example_db::specs::ModelExampleSpec {
270        id: "decision_optimal_linear_arrangement_simplegraph",
271        instance: Box::new(Decision::new(
272            OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)])),
273            3,
274        )),
275        optimal_config: serde_json::json!(vec![0, 1, 2, 3]),
276        optimal_value: serde_json::json!(true),
277    }]
278}
279
280#[cfg(feature = "example-db")]
281pub(crate) fn decision_canonical_rule_example_specs(
282) -> Vec<crate::example_db::specs::RuleExampleSpec> {
283    vec![crate::example_db::specs::RuleExampleSpec {
284        id: "decision_optimal_linear_arrangement_to_optimal_linear_arrangement",
285        build: || {
286            use crate::example_db::specs::assemble_rule_example;
287            use crate::export::SolutionPair;
288            use crate::rules::{AggregateReductionResult, ReduceToAggregate};
289            use crate::topology::SimpleGraph;
290
291            // Path P_4 (0-1-2-3): optimal arrangement has cost 3; bound 3 is YES.
292            let source = Decision::new(
293                OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)])),
294                3,
295            );
296            let result = source
297                .reduce_to_aggregate()
298                .expect("reduction should succeed");
299            let target = result.target_problem();
300            let config = vec![0, 1, 2, 3];
301            assemble_rule_example(
302                &source,
303                target,
304                vec![SolutionPair {
305                    source_config: serde_json::json!(config.clone()),
306                    target_config: serde_json::json!(config),
307                }],
308            )
309        },
310    }]
311}
312
313#[cfg(test)]
314#[path = "../../unit_tests/models/graph/optimal_linear_arrangement.rs"]
315mod tests;
problemreductions/models/graph/optimal_linear_arrangement.rs

problemreductions/models/graph/
optimal_linear_arrangement.rs
