Source code for knowledgespaces.derivation.cbkst

"""
Competence-Based Knowledge Space Theory (CB-KST) derivation.

Given a skill map μ (items → skills) and a surmise relation on skills,
derives the knowledge structure on items through the problem function.

The pipeline:
1. Build competence structure C from skill prerequisites.
2. Apply problem function p(C) to each competence state.
3. Collect unique knowledge states → knowledge structure K.

Additionally provides conversion from skill prerequisites to item
prerequisites (surmise relation on items).

References:
    Doignon, J.-P., & Falmagne, J.-C. (1999).
    Knowledge Spaces, Chapter 7. Springer-Verlag.
"""

from __future__ import annotations

from dataclasses import dataclass

from knowledgespaces.derivation.skill_map import SkillMap
from knowledgespaces.structures.knowledge_structure import KnowledgeStructure
from knowledgespaces.structures.relations import SurmiseRelation




@dataclass
class CBKSTResult:
    """Result of a CB-KST derivation."""

    competence_structure: KnowledgeStructure
    knowledge_structure: KnowledgeStructure
    mapping: dict[frozenset[str], frozenset[str]]
    skill_map: SkillMap
    skill_relation: SurmiseRelation



def _validate_skill_domains(skill_map: SkillMap, skill_relation: SurmiseRelation) -> None:
    """Ensure the skill relation covers all skills used by the skill map."""
    missing = skill_map.skills - skill_relation.items
    if missing:
        raise ValueError(f"SkillMap uses skills not present in the SurmiseRelation: {missing}")




def derive_knowledge_structure(
    skill_map: SkillMap,
    skill_relation: SurmiseRelation,
) -> CBKSTResult:
    """Derive a knowledge structure from a competence model.

    Parameters
    ----------
    skill_map : SkillMap
        The mapping μ: items → required skills.
    skill_relation : SurmiseRelation
        Prerequisite relation on skills (will be transitively closed).
        Must cover all skills referenced by the skill map.

    Returns
    -------
    CBKSTResult
        Contains the competence structure C, knowledge structure K,
        and the mapping from competence states to knowledge states.

    Raises
    ------
    ValueError
        If skill_map references skills not in skill_relation's domain.
    """
    _validate_skill_domains(skill_map, skill_relation)
    closure = skill_relation.transitive_closure()

    # 1. Competence structure: downsets of the skill order
    competence = KnowledgeStructure.from_surmise_relation(closure)

    # 2. Apply problem function to each competence state
    c_to_k: dict[frozenset[str], frozenset[str]] = {}
    knowledge_states: set[frozenset[str]] = set()

    for comp_state in competence.states:
        know_state = skill_map.problem_function(comp_state)
        knowledge_states.add(know_state)
        c_to_k[comp_state] = know_state

    # 3. Build knowledge structure on items
    knowledge = KnowledgeStructure(skill_map.items, knowledge_states)

    return CBKSTResult(
        competence_structure=competence,
        knowledge_structure=knowledge,
        mapping=c_to_k,
        skill_map=skill_map,
        skill_relation=closure,
    )





def skill_to_item_relation(
    skill_map: SkillMap,
    skill_relation: SurmiseRelation,
) -> SurmiseRelation:
    """Derive an item surmise relation from skills.

    Item p is a prerequisite of item q iff every skill required by p
    is "covered" by q — meaning the skill is either directly required
    by q or is a prerequisite of a skill required by q.

    Formally:
        covers(q) = μ(q) ∪ {s : ∃t ∈ μ(q), (s,t) ∈ closure}
        p ≺ q  iff  μ(p) ⊆ covers(q)

    Note: the result is already transitively closed.

    Parameters
    ----------
    skill_map : SkillMap
        The mapping μ: items → required skills.
    skill_relation : SurmiseRelation
        Prerequisite relation on skills.

    Returns
    -------
    SurmiseRelation
        Surmise relation on items.

    Raises
    ------
    ValueError
        If skill_map references skills not in skill_relation's domain.
    """
    _validate_skill_domains(skill_map, skill_relation)
    closure = skill_relation.transitive_closure()

    # Precompute covers(q) for each item q
    covers: dict[str, frozenset[str]] = {}
    for item in skill_map.items:
        mu_q = skill_map.skills_for(item)
        # All skills required by q, plus all their prerequisites
        covered: set[str] = set(mu_q)
        for skill in mu_q:
            covered |= set(closure.prerequisites_of(skill))
            covered.add(skill)  # reflexive
        covers[item] = frozenset(covered)

    # p ≺ q iff μ(p) ⊆ covers(q) and p ≠ q
    items = list(skill_map.items)
    relations: set[tuple[str, str]] = set()
    for p in items:
        mu_p = skill_map.skills_for(p)
        for q in items:
            if p != q and mu_p.issubset(covers[q]):
                relations.add((p, q))

    return SurmiseRelation(items, relations)