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

problemreductions/models/graph/
optimal_linear_arrangement.rs
