1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
use crate::data_structures::poset::Poset;
/// A complete lattice: a poset with a unique top (⊤) and bottom (⊥) element,
/// closed under binary join (∨) and meet (∧).
pub struct Lattice<T> {
/// The underlying poset (covering relation, transitive closure, and node list).
pub poset: Poset<T>,
/// Index of the top element (greatest element, ⊤).
pub top: u32,
/// Index of the bottom element (least element, ⊥).
pub bottom: u32,
}
impl<T: Clone> Lattice<T> {
/// Construct a `Lattice` from a `Poset`.
///
/// Returns `None` if the poset does not have a unique top and unique bottom
/// element (i.e., it is not a complete lattice).
///
/// # Examples
///
/// ```
/// use odis::{Poset, Lattice};
///
/// // Diamond: bottom(0) ≺ left(1), bottom(0) ≺ right(2), left(1) ≺ top(3), right(2) ≺ top(3)
/// let poset = Poset::from_covering_relation(
/// vec!["bot", "l", "r", "top"],
/// vec![(0, 1), (0, 2), (1, 3), (2, 3)],
/// ).unwrap();
/// let lattice = Lattice::from_poset(poset).unwrap();
/// assert_eq!(lattice.bottom, 0);
/// assert_eq!(lattice.top, 3);
/// ```
pub fn from_poset(poset: Poset<T>) -> Option<Self> {
let n = poset.nodes.len();
if n == 0 {
return None;
}
// top = unique node with no strict upper bound (no node strictly above it)
// bottom = unique node with no strict lower bound (no node strictly below it)
let top_candidates: Vec<u32> = (0..n as u32)
.filter(|&u| !poset.transitive_edges.iter().any(|&(a, _b)| a == u))
.collect();
let bottom_candidates: Vec<u32> = (0..n as u32)
.filter(|&u| !poset.transitive_edges.iter().any(|&(_a, b)| b == u))
.collect();
if top_candidates.len() != 1 || bottom_candidates.len() != 1 {
return None;
}
Some(Lattice {
poset,
top: top_candidates[0],
bottom: bottom_candidates[0],
})
}
/// Returns the least upper bound (join, ∨) of nodes `a` and `b`.
///
/// Collects all nodes that are ≥ both `a` and `b`, then returns the minimum
/// among them (the node that is ≤ all other common upper bounds).
///
/// # Examples
///
/// ```
/// use odis::{Poset, Lattice};
///
/// let poset = Poset::from_covering_relation(
/// vec!["bot", "l", "r", "top"],
/// vec![(0, 1), (0, 2), (1, 3), (2, 3)],
/// ).unwrap();
/// let lattice = Lattice::from_poset(poset).unwrap();
/// // join of the two incomparable middle nodes is the top
/// assert_eq!(lattice.join(1, 2), 3);
/// // join of a node with itself is itself
/// assert_eq!(lattice.join(0, 0), 0);
/// ```
pub fn join(&self, a: u32, b: u32) -> u32 {
if a == b {
return a;
}
// upper bounds of a: all v such that a ≤ v
// upper bounds of b: all v such that b ≤ v
// common upper bounds = intersection; join = the minimum one
let is_upper_bound = |v: u32| self.poset.is_leq(a, v) && self.poset.is_leq(b, v);
let n = self.poset.nodes.len() as u32;
let upper_bounds: Vec<u32> = (0..n).filter(|&v| is_upper_bound(v)).collect();
// The join is the unique lower bound of all upper bounds
upper_bounds
.iter()
.cloned()
.find(|&v| upper_bounds.iter().all(|&w| self.poset.is_leq(v, w)))
.unwrap_or(self.top)
}
/// Returns the greatest lower bound (meet, ∧) of nodes `a` and `b`.
///
/// Collects all nodes that are ≤ both `a` and `b`, then returns the maximum
/// among them (the node that is ≥ all other common lower bounds).
///
/// # Examples
///
/// ```
/// use odis::{Poset, Lattice};
///
/// let poset = Poset::from_covering_relation(
/// vec!["bot", "l", "r", "top"],
/// vec![(0, 1), (0, 2), (1, 3), (2, 3)],
/// ).unwrap();
/// let lattice = Lattice::from_poset(poset).unwrap();
/// // meet of the two incomparable middle nodes is the bottom
/// assert_eq!(lattice.meet(1, 2), 0);
/// // meet of a node with itself is itself
/// assert_eq!(lattice.meet(3, 3), 3);
/// ```
pub fn meet(&self, a: u32, b: u32) -> u32 {
if a == b {
return a;
}
let is_lower_bound = |v: u32| self.poset.is_leq(v, a) && self.poset.is_leq(v, b);
let n = self.poset.nodes.len() as u32;
let lower_bounds: Vec<u32> = (0..n).filter(|&v| is_lower_bound(v)).collect();
lower_bounds
.iter()
.cloned()
.find(|&v| lower_bounds.iter().all(|&w| self.poset.is_leq(w, v)))
.unwrap_or(self.bottom)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::data_structures::poset::Poset;
fn diamond_lattice() -> Lattice<usize> {
// bottom(0) ≺ left(1), bottom(0) ≺ right(2), left(1) ≺ top(3), right(2) ≺ top(3)
let poset = Poset::from_covering_relation(
vec![0usize, 1, 2, 3],
vec![(0, 1), (0, 2), (1, 3), (2, 3)],
)
.unwrap();
Lattice::from_poset(poset).unwrap()
}
#[test]
fn test_from_poset_diamond() {
let l = diamond_lattice();
assert_eq!(l.bottom, 0);
assert_eq!(l.top, 3);
}
#[test]
fn test_join_diamond() {
let l = diamond_lattice();
assert_eq!(l.join(1, 2), 3); // left ∨ right = top
assert_eq!(l.join(0, 1), 1); // bottom ∨ left = left
assert_eq!(l.join(0, 0), 0); // idempotent
assert_eq!(l.join(0, 3), 3); // bottom ∨ top = top
}
#[test]
fn test_meet_diamond() {
let l = diamond_lattice();
assert_eq!(l.meet(1, 2), 0); // left ∧ right = bottom
assert_eq!(l.meet(1, 3), 1); // left ∧ top = left
assert_eq!(l.meet(0, 3), 0); // bottom ∧ top = bottom
}
#[test]
fn test_trivial_single_node() {
let poset = Poset::from_covering_relation(vec![42usize], vec![]).unwrap();
let l = Lattice::from_poset(poset).unwrap();
assert_eq!(l.top, 0);
assert_eq!(l.bottom, 0);
assert_eq!(l.join(0, 0), 0);
assert_eq!(l.meet(0, 0), 0);
}
#[test]
fn test_non_lattice_returns_none() {
// Two-element antichain: no edges, two nodes → two maxima, two minima
let poset = Poset::from_covering_relation(vec![0usize, 1], vec![]).unwrap();
assert!(Lattice::from_poset(poset).is_none());
}
}