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

problemreductions/models/graph/
optimal_linear_arrangement.rs
