odis 2026.4.0

Formal Concept Analysis algorithms and data structures
Documentation 
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

//! Trait for iceberg concept enumeration algorithms.

use std::collections::HashSet;

use crate::data_structures::{formal_context::FormalContext, iceberg_lattice::IcebergLattice};

/// An algorithm that enumerates iceberg concepts from a formal context.
///
/// An iceberg concept is a formal concept whose extent (set of objects) has at least
/// `min_support` elements. The set of iceberg concepts forms a sub-lattice of the
/// full concept lattice (the "iceberg concept lattice").
pub trait IcebergConceptEnumerator {
    /// Enumerate all concepts with support ≥ `min_support`.
    ///
    /// Returns a poset ordered by extent inclusion. The result is empty if
    /// `min_support > ctx.objects.len()`.
    fn enumerate<T>(&self, ctx: &FormalContext<T>, min_support: u32) -> IcebergLattice;

    /// Named variant of `enumerate`; translates index pairs to `(HashSet<T>, HashSet<T>)` pairs.
    ///
    /// Returns an empty `Vec` if no concepts meet the support threshold.
    fn enumerate_named_concepts<T>(
        &self,
        ctx: &FormalContext<T>,
        min_support: u32,
    ) -> Vec<(HashSet<T>, HashSet<T>)>
    where
        T: Eq + std::hash::Hash + Clone,
    {
        self.enumerate(ctx, min_support)
            .poset
            .nodes
            .iter()
            .map(|(extent_bits, intent_bits)| {
                let extent = extent_bits.iter().map(|i| ctx.objects[i].clone()).collect();
                let intent = intent_bits.iter().map(|i| ctx.attributes[i].clone()).collect();
                (extent, intent)
            })
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use std::{fs};

    use crate::{algorithms::Titanic, traits::IcebergConceptEnumerator, FormalContext};

    fn load_living_beings() -> FormalContext<String> {
        FormalContext::<String>::from(
            &fs::read("test_data/living_beings_and_water.cxt").unwrap(),
        )
        .unwrap()
    }

    #[test]
    fn test_enumerate_named_concepts_count_matches_enumerate() {
        let ctx = load_living_beings();
        let min_support = 3;
        let lattice = Titanic.enumerate(&ctx, min_support);
        let named = Titanic.enumerate_named_concepts(&ctx, min_support);
        assert_eq!(
            named.len(),
            lattice.poset.nodes.len(),
            "enumerate_named_concepts count must match enumerate node count"
        );
    }

    #[test]
    fn test_enumerate_named_concepts_min_support_exceeds_objects_is_empty() {
        let ctx = load_living_beings();
        // min_support larger than the total number of objects → no concepts
        let min_support = ctx.objects.len() as u32 + 1;
        let named = Titanic.enumerate_named_concepts(&ctx, min_support);
        assert!(
            named.is_empty(),
            "enumerate_named_concepts should return empty vec when min_support > object count"
        );
    }

    #[test]
    fn test_enumerate_named_concepts_empty_context_is_empty() {
        let ctx = FormalContext::<String>::new();
        let named = Titanic.enumerate_named_concepts(&ctx, 0);
        assert!(
            named.is_empty(),
            "enumerate_named_concepts on empty context should return empty vec"
        );
    }
}