problemreductions/models/misc/
betweenness.rs

1//! Betweenness problem implementation.
2//!
3//! Given a finite set A and a collection C of ordered triples (a, b, c),
4//! determine whether there exists a linear ordering f: A → {1, ..., |A|}
5//! such that for each (a, b, c) ∈ C, either f(a) < f(b) < f(c) or
6//! f(c) < f(b) < f(a) (i.e., b is between a and c).
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry};
9use crate::traits::Problem;
10use crate::types::Or;
11use serde::de::Error as _;
12use serde::{Deserialize, Deserializer, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "Betweenness",
17        display_name: "Betweenness",
18        aliases: &[],
19        dimensions: &[],
20        module_path: module_path!(),
21        description: "Find a linear ordering where specified elements are between others",
22        fields: &[
23            FieldInfo { name: "num_elements", type_name: "usize", description: "Number of elements in the set A" },
24            FieldInfo { name: "triples", type_name: "Vec<(usize, usize, usize)>", description: "Collection of ordered triples (a, b, c) requiring b between a and c" },
25        ],
26    }
27}
28
29inventory::submit! {
30    ProblemSizeFieldEntry {
31        name: "Betweenness",
32        fields: &["num_elements", "num_triples"],
33    }
34}
35
36#[derive(Debug, Clone, Serialize)]
37pub struct Betweenness {
38    num_elements: usize,
39    triples: Vec<(usize, usize, usize)>,
40}
41
42impl Betweenness {
43    fn validate_inputs(
44        num_elements: usize,
45        triples: &[(usize, usize, usize)],
46    ) -> Result<(), String> {
47        if num_elements == 0 {
48            return Err("Betweenness requires at least one element".to_string());
49        }
50        for (i, &(a, b, c)) in triples.iter().enumerate() {
51            if a >= num_elements || b >= num_elements || c >= num_elements {
52                return Err(format!(
53                    "Triple {} has element(s) out of range 0..{}",
54                    i, num_elements
55                ));
56            }
57            if a == b || b == c || a == c {
58                return Err(format!(
59                    "Triple {} has duplicate elements ({}, {}, {})",
60                    i, a, b, c
61                ));
62            }
63        }
64        Ok(())
65    }
66
67    pub fn try_new(
68        num_elements: usize,
69        triples: Vec<(usize, usize, usize)>,
70    ) -> Result<Self, String> {
71        Self::validate_inputs(num_elements, &triples)?;
72        Ok(Self {
73            num_elements,
74            triples,
75        })
76    }
77
78    /// Create a new Betweenness instance.
79    ///
80    /// # Panics
81    ///
82    /// Panics if any triple element is out of range or if any triple has duplicate elements.
83    pub fn new(num_elements: usize, triples: Vec<(usize, usize, usize)>) -> Self {
84        Self::try_new(num_elements, triples).unwrap_or_else(|message| panic!("{message}"))
85    }
86
87    /// Number of elements in the set A.
88    pub fn num_elements(&self) -> usize {
89        self.num_elements
90    }
91
92    /// Number of betweenness triples.
93    pub fn num_triples(&self) -> usize {
94        self.triples.len()
95    }
96
97    /// The collection of ordered triples.
98    pub fn triples(&self) -> &[(usize, usize, usize)] {
99        &self.triples
100    }
101
102    /// Check whether a configuration represents a valid permutation and
103    /// satisfies all betweenness constraints.
104    fn is_valid_solution(&self, config: &[usize]) -> bool {
105        if config.len() != self.num_elements {
106            return false;
107        }
108
109        // Check that config is a valid permutation of 0..n
110        let n = self.num_elements;
111        let mut seen = vec![false; n];
112        for &pos in config {
113            if pos >= n || seen[pos] {
114                return false;
115            }
116            seen[pos] = true;
117        }
118
119        // Check betweenness constraints: for each (a, b, c),
120        // config[a] < config[b] < config[c] OR config[c] < config[b] < config[a]
121        for &(a, b, c) in &self.triples {
122            let fa = config[a];
123            let fb = config[b];
124            let fc = config[c];
125            if !((fa < fb && fb < fc) || (fc < fb && fb < fa)) {
126                return false;
127            }
128        }
129
130        true
131    }
132}
133
134#[derive(Deserialize)]
135struct BetweennessData {
136    num_elements: usize,
137    triples: Vec<(usize, usize, usize)>,
138}
139
140impl<'de> Deserialize<'de> for Betweenness {
141    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
142    where
143        D: Deserializer<'de>,
144    {
145        let data = BetweennessData::deserialize(deserializer)?;
146        Self::try_new(data.num_elements, data.triples).map_err(D::Error::custom)
147    }
148}
149
150impl Problem for Betweenness {
151    const NAME: &'static str = "Betweenness";
152    type Value = Or;
153
154    fn variant() -> Vec<(&'static str, &'static str)> {
155        crate::variant_params![]
156    }
157
158    fn dims(&self) -> Vec<usize> {
159        vec![self.num_elements; self.num_elements]
160    }
161
162    fn evaluate(&self, config: &[usize]) -> Or {
163        Or(self.is_valid_solution(config))
164    }
165}
166
167crate::declare_variants! {
168    default Betweenness => "2^num_elements",
169}
170
171#[cfg(feature = "example-db")]
172pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
173    vec![crate::example_db::specs::ModelExampleSpec {
174        id: "betweenness",
175        instance: Box::new(Betweenness::new(
176            5,
177            vec![(0, 1, 2), (2, 3, 4), (0, 2, 4), (1, 3, 4)],
178        )),
179        optimal_config: vec![0, 1, 2, 3, 4],
180        optimal_value: serde_json::json!(true),
181    }]
182}
183
184#[cfg(test)]
185#[path = "../../unit_tests/models/misc/betweenness.rs"]
186mod tests;
problemreductions/models/misc/betweenness.rs

problemreductions/models/misc/
betweenness.rs
