ontologos_query/
graph.rs

1use std::collections::HashMap;
2
3use ontologos_core::EntityId;
4use ontologos_core::Taxonomy;
5use petgraph::graph::{DiGraph, NodeIndex};
6use petgraph::visit::EdgeRef;
7use petgraph::Direction;
8
9/// Directed hierarchy graph built from a classified taxonomy.
10#[derive(Debug, Default)]
11pub struct TaxonomyGraph {
12    nodes: HashMap<EntityId, NodeIndex>,
13    graph: DiGraph<EntityId, ()>,
14}
15
16impl TaxonomyGraph {
17    #[must_use]
18    pub fn from_taxonomy(taxonomy: &Taxonomy) -> Self {
19        let mut tg = Self::default();
20        for &(sub, sup) in &taxonomy.subsumptions {
21            tg.add_edge(sub, sup);
22        }
23        tg
24    }
25
26    fn add_edge(&mut self, sub: EntityId, sup: EntityId) {
27        let sub_idx = *self
28            .nodes
29            .entry(sub)
30            .or_insert_with(|| self.graph.add_node(sub));
31        let sup_idx = *self
32            .nodes
33            .entry(sup)
34            .or_insert_with(|| self.graph.add_node(sup));
35        self.graph.add_edge(sub_idx, sup_idx, ());
36    }
37
38    #[must_use]
39    pub fn direct_superclasses(&self, class: EntityId) -> Vec<EntityId> {
40        let Some(&idx) = self.nodes.get(&class) else {
41            return Vec::new();
42        };
43        self.graph
44            .edges_directed(idx, Direction::Outgoing)
45            .map(|e| self.graph[e.target()])
46            .collect()
47    }
48
49    #[must_use]
50    pub fn direct_subclasses(&self, class: EntityId) -> Vec<EntityId> {
51        let Some(&idx) = self.nodes.get(&class) else {
52            return Vec::new();
53        };
54        self.graph
55            .edges_directed(idx, Direction::Incoming)
56            .map(|e| self.graph[e.source()])
57            .collect()
58    }
59
60    #[must_use]
61    pub fn is_subsumed(&self, sub: EntityId, sup: EntityId) -> bool {
62        if sub == sup {
63            return true;
64        }
65        let Some(&sub_idx) = self.nodes.get(&sub) else {
66            return false;
67        };
68        let Some(&sup_idx) = self.nodes.get(&sup) else {
69            return false;
70        };
71        petgraph::algo::has_path_connecting(&self.graph, sub_idx, sup_idx, None)
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use ontologos_core::{EntityId, Taxonomy};
78
79    use super::*;
80
81    #[test]
82    fn graph_finds_transitive_path() {
83        let a = EntityId(1);
84        let b = EntityId(2);
85        let c = EntityId(3);
86        let taxonomy = Taxonomy {
87            subsumptions: vec![(a, b), (b, c)],
88            equivalences: vec![],
89            unsatisfiable: vec![],
90        };
91        let g = TaxonomyGraph::from_taxonomy(&taxonomy);
92        assert!(g.is_subsumed(a, c));
93    }
94}
ontologos_query/graph.rs

ontologos_query/
graph.rs
