use crate::description_logic::{Concept, TableauxReasoner};
use crate::{RuleAtom, Term};
use anyhow::Result;
use scirs2_core::metrics::{Counter, Gauge, Timer};
use std::collections::{HashMap, HashSet, VecDeque};
pub struct PelletClassifier {
dl_reasoner: TableauxReasoner,
concepts: HashSet<String>,
individuals: HashSet<String>,
told_subsumers: HashMap<String, Vec<String>>,
subsumers: HashMap<String, Vec<String>>,
direct_superclasses: HashMap<String, Vec<String>>,
instances: HashMap<String, Vec<String>>,
satisfiability_cache: HashMap<String, bool>,
metrics: ClassificationMetrics,
use_told_subsumers: bool,
use_absorption: bool,
use_caching: bool,
}
pub struct ClassificationMetrics {
total_classifications: Counter,
subsumption_tests: Counter,
cache_hits: Counter,
#[allow(dead_code)]
classification_timer: Timer,
active_concepts: Gauge,
}
impl ClassificationMetrics {
fn new() -> Self {
Self {
total_classifications: Counter::new("pellet_total_classifications".to_string()),
subsumption_tests: Counter::new("pellet_subsumption_tests".to_string()),
cache_hits: Counter::new("pellet_cache_hits".to_string()),
classification_timer: Timer::new("pellet_classification_time".to_string()),
active_concepts: Gauge::new("pellet_active_concepts".to_string()),
}
}
}
impl PelletClassifier {
pub fn new() -> Self {
Self {
dl_reasoner: TableauxReasoner::new(),
concepts: HashSet::new(),
individuals: HashSet::new(),
told_subsumers: HashMap::new(),
subsumers: HashMap::new(),
direct_superclasses: HashMap::new(),
instances: HashMap::new(),
satisfiability_cache: HashMap::new(),
metrics: ClassificationMetrics::new(),
use_told_subsumers: true,
use_absorption: true,
use_caching: true,
}
}
pub fn load_ontology(&mut self, axioms: Vec<RuleAtom>) -> Result<()> {
for axiom in &axioms {
self.extract_names(axiom);
}
self.build_told_subsumers(&axioms)?;
self.metrics.active_concepts.set(self.concepts.len() as f64);
Ok(())
}
fn extract_names(&mut self, axiom: &RuleAtom) {
if let RuleAtom::Triple {
subject,
predicate: Term::Constant(pred),
object,
} = axiom
{
if pred.contains("subClassOf") {
if let Term::Constant(s) = subject {
self.concepts.insert(s.clone());
}
if let Term::Constant(o) = object {
self.concepts.insert(o.clone());
}
} else if pred.contains("type") {
if let Term::Constant(s) = subject {
self.individuals.insert(s.clone());
}
if let Term::Constant(o) = object {
self.concepts.insert(o.clone());
}
}
}
}
fn build_told_subsumers(&mut self, axioms: &[RuleAtom]) -> Result<()> {
for axiom in axioms {
if let RuleAtom::Triple {
subject,
predicate: Term::Constant(pred),
object,
} = axiom
{
if pred.contains("subClassOf") {
if let (Term::Constant(sub), Term::Constant(sup)) = (subject, object) {
self.told_subsumers
.entry(sub.clone())
.or_default()
.push(sup.clone());
}
}
}
}
Ok(())
}
pub fn classify(&mut self) -> Result<()> {
self.metrics.total_classifications.inc();
let start_time = std::time::Instant::now();
if self.use_told_subsumers {
for (concept, told) in &self.told_subsumers {
self.subsumers.insert(concept.clone(), told.clone());
}
}
let concepts: Vec<_> = self.concepts.iter().cloned().collect();
for concept_a in &concepts {
let mut all_subsumers = Vec::new();
if let Some(told) = self.told_subsumers.get(concept_a) {
all_subsumers.extend(told.clone());
}
for concept_b in &concepts {
if concept_a == concept_b {
continue;
}
if all_subsumers.contains(concept_b) {
continue;
}
if self.test_subsumption(concept_a, concept_b)? {
all_subsumers.push(concept_b.clone());
}
}
self.subsumers.insert(concept_a.clone(), all_subsumers);
}
self.compute_direct_superclasses()?;
let _elapsed = start_time.elapsed();
Ok(())
}
fn test_subsumption(&mut self, concept_a: &str, concept_b: &str) -> Result<bool> {
self.metrics.subsumption_tests.inc();
let cache_key = format!("{}|{}", concept_a, concept_b);
if self.use_caching {
if let Some(&result) = self.satisfiability_cache.get(&cache_key) {
self.metrics.cache_hits.inc();
return Ok(result);
}
}
let concept_a_dl = Concept::Atomic(concept_a.to_string());
let concept_b_dl = Concept::Atomic(concept_b.to_string());
let negation = Concept::Not(Box::new(concept_b_dl));
let conjunction = Concept::And(Box::new(concept_a_dl), Box::new(negation));
let is_satisfiable = self.dl_reasoner.is_satisfiable(&conjunction)?;
let result = !is_satisfiable;
if self.use_caching {
self.satisfiability_cache.insert(cache_key, result);
}
Ok(result)
}
fn compute_direct_superclasses(&mut self) -> Result<()> {
for (concept, all_subsumers) in &self.subsumers {
let mut direct = Vec::new();
for subsumer in all_subsumers {
let mut is_direct = true;
for other in all_subsumers {
if other == subsumer {
continue;
}
if let Some(other_subsumers) = self.subsumers.get(other) {
if other_subsumers.contains(subsumer) {
is_direct = false;
break;
}
}
}
if is_direct {
direct.push(subsumer.clone());
}
}
self.direct_superclasses.insert(concept.clone(), direct);
}
Ok(())
}
pub fn is_subsumed_by(&self, concept_a: &str, concept_b: &str) -> Result<bool> {
if let Some(subsumers) = self.subsumers.get(concept_a) {
Ok(subsumers.contains(&concept_b.to_string()))
} else {
Ok(false)
}
}
pub fn get_superclasses(&self, concept: &str) -> Option<&Vec<String>> {
self.subsumers.get(concept)
}
pub fn get_direct_superclasses(&self, concept: &str) -> Option<&Vec<String>> {
self.direct_superclasses.get(concept)
}
pub fn get_subclasses(&self, concept: &str) -> Vec<String> {
let mut subclasses = Vec::new();
for (sub, subsumers) in &self.subsumers {
if subsumers.contains(&concept.to_string()) {
subclasses.push(sub.clone());
}
}
subclasses
}
pub fn realize(&mut self) -> Result<()> {
let individuals: Vec<_> = self.individuals.iter().cloned().collect();
let concepts: Vec<_> = self.concepts.iter().cloned().collect();
for individual in &individuals {
let mut classes = Vec::new();
for concept in &concepts {
if self.is_instance_of(individual, concept)? {
classes.push(concept.clone());
}
}
let mut most_specific = Vec::new();
for class in &classes {
let mut is_most_specific = true;
for other in &classes {
if class == other {
continue;
}
if let Some(subsumers) = self.subsumers.get(other) {
if subsumers.contains(class) {
is_most_specific = false;
break;
}
}
}
if is_most_specific {
most_specific.push(class.clone());
}
}
self.instances.insert(individual.clone(), most_specific);
}
Ok(())
}
pub fn is_instance_of(&mut self, individual: &str, concept: &str) -> Result<bool> {
let _type_axiom = RuleAtom::Triple {
subject: Term::Constant(individual.to_string()),
predicate: Term::Constant("rdf:type".to_string()),
object: Term::Constant(concept.to_string()),
};
Ok(false)
}
pub fn get_types(&self, individual: &str) -> Option<&Vec<String>> {
self.instances.get(individual)
}
pub fn get_instances(&self, concept: &str) -> Vec<String> {
let mut instances = Vec::new();
for (individual, types) in &self.instances {
if types.contains(&concept.to_string()) {
instances.push(individual.clone());
}
}
instances
}
pub fn get_metrics(&self) -> &ClassificationMetrics {
&self.metrics
}
pub fn set_optimization(&mut self, told_subsumers: bool, absorption: bool, caching: bool) {
self.use_told_subsumers = told_subsumers;
self.use_absorption = absorption;
self.use_caching = caching;
}
pub fn to_dot_graph(&self) -> String {
let mut dot = String::from("digraph ClassHierarchy {\n");
dot.push_str(" rankdir=BT;\n");
for (concept, superclasses) in &self.direct_superclasses {
for superclass in superclasses {
dot.push_str(&format!(" \"{}\" -> \"{}\";\n", concept, superclass));
}
}
dot.push_str("}\n");
dot
}
pub fn clear(&mut self) {
self.subsumers.clear();
self.direct_superclasses.clear();
self.instances.clear();
self.satisfiability_cache.clear();
}
pub fn incremental_classify(&mut self, new_axioms: Vec<RuleAtom>) -> Result<()> {
for axiom in &new_axioms {
self.extract_names(axiom);
}
self.build_told_subsumers(&new_axioms)?;
self.classify()
}
}
impl Default for PelletClassifier {
fn default() -> Self {
Self::new()
}
}
pub struct SubsumptionHierarchyBuilder {
classifier: PelletClassifier,
levels: Vec<Vec<String>>,
}
impl SubsumptionHierarchyBuilder {
pub fn new() -> Self {
Self {
classifier: PelletClassifier::new(),
levels: Vec::new(),
}
}
pub fn build(&mut self, axioms: Vec<RuleAtom>) -> Result<()> {
self.classifier.load_ontology(axioms)?;
self.classifier.classify()?;
self.compute_levels()?;
Ok(())
}
fn compute_levels(&mut self) -> Result<()> {
let concepts: Vec<_> = self.classifier.concepts.iter().cloned().collect();
let mut roots = Vec::new();
for concept in &concepts {
if let Some(superclasses) = self.classifier.get_direct_superclasses(concept) {
if superclasses.is_empty() {
roots.push(concept.clone());
}
} else {
roots.push(concept.clone());
}
}
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
self.levels.push(roots.clone());
for root in roots {
visited.insert(root.clone());
queue.push_back((root, 0));
}
let mut max_level = 0;
while let Some((concept, level)) = queue.pop_front() {
let subclasses = self.classifier.get_subclasses(&concept);
for subclass in subclasses {
if visited.contains(&subclass) {
continue;
}
visited.insert(subclass.clone());
let next_level = level + 1;
while self.levels.len() <= next_level {
self.levels.push(Vec::new());
}
self.levels[next_level].push(subclass.clone());
queue.push_back((subclass, next_level));
max_level = max_level.max(next_level);
}
}
Ok(())
}
pub fn get_levels(&self) -> &Vec<Vec<String>> {
&self.levels
}
pub fn get_classifier(&self) -> &PelletClassifier {
&self.classifier
}
}
impl Default for SubsumptionHierarchyBuilder {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn create_subclass_axiom(sub: &str, sup: &str) -> RuleAtom {
RuleAtom::Triple {
subject: Term::Constant(sub.to_string()),
predicate: Term::Constant("rdfs:subClassOf".to_string()),
object: Term::Constant(sup.to_string()),
}
}
fn create_type_axiom(individual: &str, class: &str) -> RuleAtom {
RuleAtom::Triple {
subject: Term::Constant(individual.to_string()),
predicate: Term::Constant("rdf:type".to_string()),
object: Term::Constant(class.to_string()),
}
}
#[test]
fn test_classifier_creation() {
let classifier = PelletClassifier::new();
assert_eq!(classifier.concepts.len(), 0);
assert_eq!(classifier.individuals.len(), 0);
}
#[test]
fn test_load_ontology() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![
create_subclass_axiom("Dog", "Animal"),
create_subclass_axiom("Cat", "Animal"),
];
classifier.load_ontology(axioms)?;
assert!(classifier.concepts.contains("Dog"));
assert!(classifier.concepts.contains("Cat"));
assert!(classifier.concepts.contains("Animal"));
Ok(())
}
#[test]
fn test_told_subsumers() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![create_subclass_axiom("Dog", "Animal")];
classifier.load_ontology(axioms)?;
let told = classifier.told_subsumers.get("Dog");
assert!(told.is_some());
assert_eq!(told.ok_or("expected Some value")?[0], "Animal");
Ok(())
}
#[test]
fn test_classify() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![
create_subclass_axiom("Dog", "Animal"),
create_subclass_axiom("Animal", "LivingThing"),
];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let subsumers = classifier.get_superclasses("Dog");
assert!(subsumers.is_some());
Ok(())
}
#[test]
fn test_is_subsumed_by() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![create_subclass_axiom("Dog", "Animal")];
classifier.load_ontology(axioms)?;
classifier.classify()?;
assert!(classifier.is_subsumed_by("Dog", "Animal")?);
assert!(!classifier.is_subsumed_by("Animal", "Dog")?);
Ok(())
}
#[test]
fn test_get_subclasses() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![
create_subclass_axiom("Dog", "Animal"),
create_subclass_axiom("Cat", "Animal"),
];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let subclasses = classifier.get_subclasses("Animal");
assert!(subclasses.contains(&"Dog".to_string()));
assert!(subclasses.contains(&"Cat".to_string()));
Ok(())
}
#[test]
fn test_direct_superclasses() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![
create_subclass_axiom("Dog", "Mammal"),
create_subclass_axiom("Mammal", "Animal"),
];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let direct = classifier.get_direct_superclasses("Dog");
assert!(direct.is_some());
Ok(())
}
#[test]
fn test_metrics_tracking() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![create_subclass_axiom("Dog", "Animal")];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let _metrics = classifier.get_metrics();
Ok(())
}
#[test]
fn test_optimization_flags() {
let mut classifier = PelletClassifier::new();
classifier.set_optimization(true, true, true);
assert!(classifier.use_told_subsumers);
assert!(classifier.use_absorption);
assert!(classifier.use_caching);
}
#[test]
fn test_clear() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![create_subclass_axiom("Dog", "Animal")];
classifier.load_ontology(axioms)?;
classifier.classify()?;
classifier.clear();
assert!(classifier.subsumers.is_empty());
Ok(())
}
#[test]
fn test_hierarchy_builder_creation() {
let builder = SubsumptionHierarchyBuilder::new();
assert_eq!(builder.levels.len(), 0);
}
#[test]
fn test_hierarchy_builder_build() -> Result<(), Box<dyn std::error::Error>> {
let mut builder = SubsumptionHierarchyBuilder::new();
let axioms = vec![
create_subclass_axiom("Dog", "Mammal"),
create_subclass_axiom("Mammal", "Animal"),
];
builder.build(axioms)?;
let levels = builder.get_levels();
assert!(!levels.is_empty());
Ok(())
}
#[test]
fn test_to_dot_graph() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![create_subclass_axiom("Dog", "Animal")];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let dot = classifier.to_dot_graph();
assert!(dot.contains("digraph"));
Ok(())
}
#[test]
fn test_extract_names() {
let mut classifier = PelletClassifier::new();
let axiom = create_subclass_axiom("Dog", "Animal");
classifier.extract_names(&axiom);
assert!(classifier.concepts.contains("Dog"));
assert!(classifier.concepts.contains("Animal"));
}
#[test]
fn test_extract_individuals() {
let mut classifier = PelletClassifier::new();
let axiom = create_type_axiom("fido", "Dog");
classifier.extract_names(&axiom);
assert!(classifier.individuals.contains("fido"));
assert!(classifier.concepts.contains("Dog"));
}
#[test]
fn test_transitive_subsumption() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![
create_subclass_axiom("Poodle", "Dog"),
create_subclass_axiom("Dog", "Mammal"),
create_subclass_axiom("Mammal", "Animal"),
];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let subsumers = classifier.get_superclasses("Poodle");
assert!(subsumers.is_some());
Ok(())
}
#[test]
fn test_multiple_superclasses() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![
create_subclass_axiom("FlyingFish", "Fish"),
create_subclass_axiom("FlyingFish", "FlyingAnimal"),
];
classifier.load_ontology(axioms)?;
classifier.classify()?;
let subsumers = classifier.get_superclasses("FlyingFish");
assert!(subsumers.is_some());
assert!(subsumers
.ok_or("expected Some value")?
.contains(&"Fish".to_string()));
assert!(subsumers
.ok_or("expected Some value")?
.contains(&"FlyingAnimal".to_string()));
Ok(())
}
#[test]
fn test_cache_usage() -> Result<(), Box<dyn std::error::Error>> {
let mut classifier = PelletClassifier::new();
let axioms = vec![create_subclass_axiom("Dog", "Animal")];
classifier.load_ontology(axioms)?;
classifier.classify()?;
classifier.classify()?;
let _metrics = classifier.get_metrics();
Ok(())
}
}