concept_graph/
relations.rs

1//! Typed adjacency: every edge carries a relationship type, and both
2//! directions are materialized.
3//!
4//! The is-a hierarchy is [`crate::persist::Hierarchy`]; this is for the other
5//! relationships a code system states between its concepts (`RxNorm`'s `REL`
6//! and `RELA`, SNOMED CT's attributes when they are served as a graph). No
7//! spec governs the layout: our own design. Little-endian, a magic and
8//! version prefix, the type names, then the outgoing and the incoming
9//! adjacency as offsets with parallel type and node arrays, each node's edges
10//! sorted by type then node.
11
12use std::io::{self, Read, Write};
13
14use crate::ordinal::{Ordinal, to_usize};
15
16const MAGIC: &[u8; 8] = b"FTRELS\0\0";
17const VERSION: u32 = 1;
18
19/// A failure while building, reading, or writing the relations.
20#[derive(Debug, thiserror::Error)]
21pub enum RelationsError {
22    /// An edge names a node or a type beyond the declared counts.
23    #[error("edge ({from}, {kind}, {target}) is out of range for {nodes} nodes and {types} types")]
24    OutOfRange {
25        /// The source node.
26        from: u32,
27        /// The type index.
28        kind: u32,
29        /// The target node.
30        target: u32,
31        /// The node count.
32        nodes: u32,
33        /// The type count.
34        types: u32,
35    },
36    /// An I/O failure.
37    #[error("relations I/O failed")]
38    Io(#[from] io::Error),
39    /// The bytes do not start with the relations magic.
40    #[error("not a relations artifact")]
41    Magic,
42    /// The layout version is not the one this build reads.
43    #[error("relations layout version {found}, expected {expected}")]
44    Version {
45        /// The version found.
46        found: u32,
47        /// The version this build reads.
48        expected: u32,
49    },
50    /// The arrays are inconsistent.
51    #[error("the relations arrays are inconsistent")]
52    Inconsistent,
53    /// A type name is not UTF-8.
54    #[error("a relationship type name is not UTF-8")]
55    Name(#[from] std::string::FromUtf8Error),
56}
57
58/// One direction of the adjacency.
59#[derive(Debug, Clone, PartialEq, Eq, Default)]
60struct Adjacency {
61    /// `nodes + 1` offsets into `kinds` and `ends`.
62    offsets: Vec<u32>,
63    kinds: Vec<u32>,
64    ends: Vec<u32>,
65}
66
67impl Adjacency {
68    fn build(nodes: u32, mut edges: Vec<(u32, u32, u32)>) -> Self {
69        edges.sort_unstable();
70        edges.dedup();
71        let mut offsets = Vec::with_capacity(to_usize(nodes).saturating_add(1));
72        let mut kinds = Vec::with_capacity(edges.len());
73        let mut ends = Vec::with_capacity(edges.len());
74        let mut cursor = 0usize;
75        for node in 0..nodes {
76            offsets.push(u32::try_from(kinds.len()).unwrap_or(u32::MAX));
77            while let Some(&(from, kind, to)) = edges.get(cursor) {
78                if from != node {
79                    break;
80                }
81                kinds.push(kind);
82                ends.push(to);
83                cursor = cursor.saturating_add(1);
84            }
85        }
86        offsets.push(u32::try_from(kinds.len()).unwrap_or(u32::MAX));
87        Self {
88            offsets,
89            kinds,
90            ends,
91        }
92    }
93
94    fn edges(&self, node: Ordinal) -> impl Iterator<Item = (u32, u32)> + '_ {
95        let index = to_usize(node.index());
96        let (start, end) = match (
97            self.offsets.get(index),
98            self.offsets.get(index.saturating_add(1)),
99        ) {
100            (Some(&s), Some(&e)) => (to_usize(s), to_usize(e)),
101            _ => (0, 0),
102        };
103        let kinds = self.kinds.get(start..end).unwrap_or_default();
104        let ends = self.ends.get(start..end).unwrap_or_default();
105        kinds.iter().copied().zip(ends.iter().copied())
106    }
107
108    fn check(&self, nodes: u32) -> Result<(), RelationsError> {
109        let consistent = self.offsets.len() == to_usize(nodes).saturating_add(1)
110            && self.kinds.len() == self.ends.len()
111            && self
112                .offsets
113                .last()
114                .is_some_and(|&l| to_usize(l) == self.kinds.len())
115            && self.offsets.windows(2).all(|w| w.first() <= w.get(1));
116        consistent.then_some(()).ok_or(RelationsError::Inconsistent)
117    }
118}
119
120/// The typed edges of a code system, both ways.
121#[derive(Debug, Clone, PartialEq, Eq, Default)]
122pub struct Relations {
123    /// The relationship type names; an edge's type is an index into this list.
124    types: Vec<String>,
125    outgoing: Adjacency,
126    incoming: Adjacency,
127}
128
129impl Relations {
130    /// Builds the relations of `nodes` nodes from `(source, type, target)` edges.
131    ///
132    /// # Errors
133    ///
134    /// Returns [`RelationsError::OutOfRange`] for an edge beyond `nodes` or
135    /// beyond the type list.
136    pub fn build(
137        nodes: u32,
138        types: Vec<String>,
139        edges: Vec<(Ordinal, u32, Ordinal)>,
140    ) -> Result<Self, RelationsError> {
141        let type_count = u32::try_from(types.len()).unwrap_or(u32::MAX);
142        let mut forward = Vec::with_capacity(edges.len());
143        let mut backward = Vec::with_capacity(edges.len());
144        for (source, kind, target) in edges {
145            let (s, t) = (source.index(), target.index());
146            if s >= nodes || t >= nodes || kind >= type_count {
147                return Err(RelationsError::OutOfRange {
148                    from: s,
149                    kind,
150                    target: t,
151                    nodes,
152                    types: type_count,
153                });
154            }
155            forward.push((s, kind, t));
156            backward.push((t, kind, s));
157        }
158        Ok(Self {
159            types,
160            outgoing: Adjacency::build(nodes, forward),
161            incoming: Adjacency::build(nodes, backward),
162        })
163    }
164
165    /// The relationship type names.
166    #[must_use]
167    pub fn types(&self) -> &[String] {
168        &self.types
169    }
170
171    /// The index of the type `name`.
172    #[must_use]
173    pub fn kind(&self, name: &str) -> Option<u32> {
174        self.types
175            .iter()
176            .position(|t| t == name)
177            .and_then(|i| u32::try_from(i).ok())
178    }
179
180    /// The node count.
181    #[must_use]
182    pub fn nodes(&self) -> u32 {
183        u32::try_from(self.outgoing.offsets.len().saturating_sub(1)).unwrap_or(u32::MAX)
184    }
185
186    /// The edge count.
187    #[must_use]
188    pub fn edges(&self) -> usize {
189        self.outgoing.ends.len()
190    }
191
192    /// The `(type, target)` pairs leaving `node`, by type then target.
193    pub fn outgoing(&self, node: Ordinal) -> impl Iterator<Item = (u32, Ordinal)> + '_ {
194        self.outgoing.edges(node).map(|(k, n)| (k, Ordinal::new(n)))
195    }
196
197    /// The `(type, source)` pairs arriving at `node`, by type then source.
198    pub fn incoming(&self, node: Ordinal) -> impl Iterator<Item = (u32, Ordinal)> + '_ {
199        self.incoming.edges(node).map(|(k, n)| (k, Ordinal::new(n)))
200    }
201
202    /// The sources of edges of type `kind` arriving at `node`.
203    pub fn sources(&self, node: Ordinal, kind: u32) -> impl Iterator<Item = Ordinal> + '_ {
204        self.incoming(node)
205            .filter(move |(k, _)| *k == kind)
206            .map(|(_, n)| n)
207    }
208
209    /// The targets of edges of type `kind` leaving `node`.
210    pub fn targets(&self, node: Ordinal, kind: u32) -> impl Iterator<Item = Ordinal> + '_ {
211        self.outgoing(node)
212            .filter(move |(k, _)| *k == kind)
213            .map(|(_, n)| n)
214    }
215
216    /// Writes the layout.
217    ///
218    /// # Errors
219    ///
220    /// Returns [`RelationsError::Io`] when writing fails.
221    pub fn write_to(&self, out: &mut impl Write) -> Result<(), RelationsError> {
222        out.write_all(MAGIC)?;
223        out.write_all(&VERSION.to_le_bytes())?;
224        let count = crate::persist::u32_len(self.types.len(), "the type count")?;
225        out.write_all(&count.to_le_bytes())?;
226        for name in &self.types {
227            let len = crate::persist::u32_len(name.len(), "a type name length")?;
228            out.write_all(&len.to_le_bytes())?;
229            out.write_all(name.as_bytes())?;
230        }
231        for side in [&self.outgoing, &self.incoming] {
232            write_u32s(out, &side.offsets)?;
233            write_u32s(out, &side.kinds)?;
234            write_u32s(out, &side.ends)?;
235        }
236        Ok(())
237    }
238
239    /// Reads the layout.
240    ///
241    /// # Errors
242    ///
243    /// Returns [`RelationsError`] for a truncated, foreign, or inconsistent artifact.
244    pub fn read_from(input: &mut impl Read) -> Result<Self, RelationsError> {
245        let mut magic = [0_u8; 8];
246        input.read_exact(&mut magic)?;
247        if &magic != MAGIC {
248            return Err(RelationsError::Magic);
249        }
250        let version = read_u32(input)?;
251        if version != VERSION {
252            return Err(RelationsError::Version {
253                found: version,
254                expected: VERSION,
255            });
256        }
257        let count = read_u32(input)?;
258        let mut types = Vec::with_capacity(to_usize(count));
259        for _ in 0..count {
260            let len = read_u32(input)?;
261            let mut bytes = vec![0_u8; to_usize(len)];
262            input.read_exact(&mut bytes)?;
263            types.push(String::from_utf8(bytes)?);
264        }
265        let mut sides = Vec::with_capacity(2);
266        for _ in 0..2 {
267            sides.push(Adjacency {
268                offsets: read_u32s(input)?,
269                kinds: read_u32s(input)?,
270                ends: read_u32s(input)?,
271            });
272        }
273        let incoming = sides.pop().ok_or(RelationsError::Inconsistent)?;
274        let outgoing = sides.pop().ok_or(RelationsError::Inconsistent)?;
275        // A node count past u32::MAX is an inconsistent artifact; the conversion
276        // error adds nothing to that.
277        let Ok(nodes) = u32::try_from(outgoing.offsets.len().saturating_sub(1)) else {
278            return Err(RelationsError::Inconsistent);
279        };
280        outgoing.check(nodes)?;
281        incoming.check(nodes)?;
282        Ok(Self {
283            types,
284            outgoing,
285            incoming,
286        })
287    }
288}
289
290fn write_u32s(out: &mut impl Write, values: &[u32]) -> io::Result<()> {
291    let len = crate::persist::u32_len(values.len(), "an array length")?;
292    out.write_all(&len.to_le_bytes())?;
293    for value in values {
294        out.write_all(&value.to_le_bytes())?;
295    }
296    Ok(())
297}
298
299fn read_u32(input: &mut impl Read) -> io::Result<u32> {
300    let mut buffer = [0_u8; 4];
301    input.read_exact(&mut buffer)?;
302    Ok(u32::from_le_bytes(buffer))
303}
304
305fn read_u32s(input: &mut impl Read) -> io::Result<Vec<u32>> {
306    let len = read_u32(input)?;
307    let mut values = Vec::with_capacity(to_usize(len));
308    for _ in 0..len {
309        values.push(read_u32(input)?);
310    }
311    Ok(values)
312}
313
314#[cfg(test)]
315mod tests {
316    use super::{Relations, RelationsError};
317    use crate::ordinal::Ordinal;
318
319    #[test]
320    fn edges_are_answered_both_ways_and_round_trip() {
321        let o = Ordinal::new;
322        let types = vec![String::from("has_ingredient"), String::from("isa")];
323        let relations = Relations::build(
324            4,
325            types,
326            vec![
327                (o(2), 0, o(0)),
328                (o(3), 0, o(0)),
329                (o(3), 1, o(2)),
330                (o(2), 0, o(0)),
331            ],
332        )
333        .expect("builds");
334        assert_eq!(relations.edges(), 3, "duplicates collapse");
335        assert_eq!(relations.kind("isa"), Some(1));
336        assert_eq!(relations.kind("part_of"), None);
337        let sources: Vec<u32> = relations.sources(o(0), 0).map(Ordinal::index).collect();
338        assert_eq!(sources, [2, 3]);
339        let targets: Vec<u32> = relations.targets(o(3), 1).map(Ordinal::index).collect();
340        assert_eq!(targets, [2]);
341        assert_eq!(relations.outgoing(o(1)).count(), 0);
342        let mut bytes = Vec::new();
343        relations.write_to(&mut bytes).expect("writes");
344        let back = Relations::read_from(&mut bytes.as_slice()).expect("reads");
345        assert_eq!(back, relations);
346        assert!(matches!(
347            Relations::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
348            Err(RelationsError::Magic)
349        ));
350        assert!(matches!(
351            Relations::build(2, Vec::new(), vec![(o(0), 0, o(1))]),
352            Err(RelationsError::OutOfRange { .. })
353        ));
354    }
355}
concept_graph/relations.rs

concept_graph/
relations.rs
