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 =
225            u32::try_from(self.types.len()).map_err(|_| io::Error::other("too many types"))?;
226        out.write_all(&count.to_le_bytes())?;
227        for name in &self.types {
228            let len = u32::try_from(name.len()).map_err(|_| io::Error::other("name too long"))?;
229            out.write_all(&len.to_le_bytes())?;
230            out.write_all(name.as_bytes())?;
231        }
232        for side in [&self.outgoing, &self.incoming] {
233            write_u32s(out, &side.offsets)?;
234            write_u32s(out, &side.kinds)?;
235            write_u32s(out, &side.ends)?;
236        }
237        Ok(())
238    }
239
240    /// Reads the layout.
241    ///
242    /// # Errors
243    ///
244    /// Returns [`RelationsError`] for a truncated, foreign, or inconsistent artifact.
245    pub fn read_from(input: &mut impl Read) -> Result<Self, RelationsError> {
246        let mut magic = [0_u8; 8];
247        input.read_exact(&mut magic)?;
248        if &magic != MAGIC {
249            return Err(RelationsError::Magic);
250        }
251        let version = read_u32(input)?;
252        if version != VERSION {
253            return Err(RelationsError::Version {
254                found: version,
255                expected: VERSION,
256            });
257        }
258        let count = read_u32(input)?;
259        let mut types = Vec::with_capacity(to_usize(count));
260        for _ in 0..count {
261            let len = read_u32(input)?;
262            let mut bytes = vec![0_u8; to_usize(len)];
263            input.read_exact(&mut bytes)?;
264            types.push(String::from_utf8(bytes)?);
265        }
266        let mut sides = Vec::with_capacity(2);
267        for _ in 0..2 {
268            sides.push(Adjacency {
269                offsets: read_u32s(input)?,
270                kinds: read_u32s(input)?,
271                ends: read_u32s(input)?,
272            });
273        }
274        let incoming = sides.pop().ok_or(RelationsError::Inconsistent)?;
275        let outgoing = sides.pop().ok_or(RelationsError::Inconsistent)?;
276        let nodes = u32::try_from(outgoing.offsets.len().saturating_sub(1))
277            .map_err(|_| RelationsError::Inconsistent)?;
278        outgoing.check(nodes)?;
279        incoming.check(nodes)?;
280        Ok(Self {
281            types,
282            outgoing,
283            incoming,
284        })
285    }
286}
287
288fn write_u32s(out: &mut impl Write, values: &[u32]) -> io::Result<()> {
289    let len = u32::try_from(values.len()).map_err(|_| io::Error::other("array too long"))?;
290    out.write_all(&len.to_le_bytes())?;
291    for value in values {
292        out.write_all(&value.to_le_bytes())?;
293    }
294    Ok(())
295}
296
297fn read_u32(input: &mut impl Read) -> io::Result<u32> {
298    let mut buffer = [0_u8; 4];
299    input.read_exact(&mut buffer)?;
300    Ok(u32::from_le_bytes(buffer))
301}
302
303fn read_u32s(input: &mut impl Read) -> io::Result<Vec<u32>> {
304    let len = read_u32(input)?;
305    let mut values = Vec::with_capacity(to_usize(len));
306    for _ in 0..len {
307        values.push(read_u32(input)?);
308    }
309    Ok(values)
310}
311
312#[cfg(test)]
313mod tests {
314    use super::{Relations, RelationsError};
315    use crate::ordinal::Ordinal;
316
317    #[test]
318    fn edges_are_answered_both_ways_and_round_trip() {
319        let o = Ordinal::new;
320        let types = vec![String::from("has_ingredient"), String::from("isa")];
321        let relations = Relations::build(
322            4,
323            types,
324            vec![
325                (o(2), 0, o(0)),
326                (o(3), 0, o(0)),
327                (o(3), 1, o(2)),
328                (o(2), 0, o(0)),
329            ],
330        )
331        .expect("builds");
332        assert_eq!(relations.edges(), 3, "duplicates collapse");
333        assert_eq!(relations.kind("isa"), Some(1));
334        assert_eq!(relations.kind("part_of"), None);
335        let sources: Vec<u32> = relations.sources(o(0), 0).map(Ordinal::index).collect();
336        assert_eq!(sources, [2, 3]);
337        let targets: Vec<u32> = relations.targets(o(3), 1).map(Ordinal::index).collect();
338        assert_eq!(targets, [2]);
339        assert_eq!(relations.outgoing(o(1)).count(), 0);
340        let mut bytes = Vec::new();
341        relations.write_to(&mut bytes).expect("writes");
342        let back = Relations::read_from(&mut bytes.as_slice()).expect("reads");
343        assert_eq!(back, relations);
344        assert!(matches!(
345            Relations::read_from(&mut b"XXXXXXXX\0\0\0\0".as_slice()),
346            Err(RelationsError::Magic)
347        ));
348        assert!(matches!(
349            Relations::build(2, Vec::new(), vec![(o(0), 0, o(1))]),
350            Err(RelationsError::OutOfRange { .. })
351        ));
352    }
353}
concept_graph/relations.rs

concept_graph/
relations.rs
