"""
Surmise relations on item domains.
A surmise relation is a *quasi-order* (reflexive and transitive) on a set
of items that encodes prerequisite dependencies: if (a, b) is in the
relation, then mastering item a is a prerequisite for mastering item b. On
a *discriminative* item domain — the usual case when QUERY is run on items
(rather than instances or skills) — no two distinct items are equivalent,
so the relation is additionally antisymmetric, i.e. a partial order.
Mutually prerequisite (equivalent) items arise with skills/competencies
and are handled by competence-based KST (see
:mod:`knowledgespaces.derivation`), not by item-level QUERY.
Storage and views:
The class stores only the strict cover (pairs with a != b);
reflexivity is implicit. Membership (``in``) and :meth:`to_matrix`
expose the *reflexive* relation — ``(x, x)`` is always a member and the
matrix diagonal is always 1. The prerequisite/successor accessors
(:meth:`prerequisites_of`, :meth:`successors_of`,
:meth:`to_adjacency_dict`) return the *direct, strict* relation (no
self, no transitive closure); call :meth:`transitive_closure` for all
transitive prerequisites. Antisymmetry is not enforced at construction
— verify with :meth:`is_antisymmetric`.
References:
Doignon, J.-P., & Falmagne, J.-C. (1999). Knowledge Spaces. Springer.
Falmagne, J.-C., & Doignon, J.-P. (2011). Learning Spaces. Springer.
"""
from __future__ import annotations
from collections.abc import Collection, Iterator, Mapping
[docs]
class SurmiseRelation:
"""A surmise relation (quasi-order) representing prerequisite dependencies.
The relation is stored as a set of directed pairs (a, b) meaning
'a is a prerequisite of b'. Self-loops are excluded from storage
(reflexivity is implicit, so membership and :meth:`to_matrix` are
reflexive). On a discriminative item domain the relation is a partial
order (antisymmetric); antisymmetry is not enforced at construction
time — use :meth:`is_antisymmetric` to verify.
Parameters
----------
items : Collection[str]
The domain of items.
relations : Collection[tuple[str, str]]
Pairs (a, b) where a is a prerequisite of b.
Self-loops (a, a) are silently ignored.
"""
__slots__ = ("_items", "_relations")
def __init__(
self,
items: Collection[str],
relations: Collection[tuple[str, str]],
) -> None:
self._items: frozenset[str] = frozenset(items)
strict: set[tuple[str, str]] = set()
for a, b in relations:
if a == b:
continue # self-loops are implicit (reflexivity)
unknown = set()
if a not in self._items:
unknown.add(a)
if b not in self._items:
unknown.add(b)
if unknown:
raise ValueError(
f"Relation ({a!r}, {b!r}) references items not in the domain: {unknown}"
)
strict.add((a, b))
self._relations: frozenset[tuple[str, str]] = frozenset(strict)
# ------------------------------------------------------------------
# Properties
# ------------------------------------------------------------------
@property
def items(self) -> frozenset[str]:
return self._items
@property
def relations(self) -> frozenset[tuple[str, str]]:
return self._relations
@property
def size(self) -> int:
"""Number of items in the domain."""
return len(self._items)
# ------------------------------------------------------------------
# Core algorithms
# ------------------------------------------------------------------
[docs]
def transitive_closure(self) -> SurmiseRelation:
"""Compute the transitive closure.
Returns a new SurmiseRelation containing all transitively implied
pairs. If (a, b) and (b, c) are in the relation, (a, c) is added.
Uses an adjacency-set approach: for each item, the set of
successors is iteratively expanded until a fixed point is reached.
"""
# Build adjacency: succ[a] = {b : (a, b) in relation}
succ: dict[str, set[str]] = {q: set() for q in self._items}
for a, b in self._relations:
succ[a].add(b)
# Expand: succ[a] |= succ[b] for each b in succ[a], repeat
changed = True
while changed:
changed = False
for a in self._items:
new = set()
for b in succ[a]:
new |= succ[b]
before = len(succ[a])
succ[a] |= new
succ[a].discard(a) # no self-loops
if len(succ[a]) > before:
changed = True
closed = {(a, b) for a, ss in succ.items() for b in ss}
return SurmiseRelation(self._items, closed)
[docs]
def transitive_reduction(self) -> SurmiseRelation:
"""Compute the transitive reduction (Hasse diagram).
Returns a new SurmiseRelation containing only the direct
prerequisite edges — removes any edge (a, c) when there exists
an intermediate item b such that (a, b) and (b, c) are both
in the transitive closure.
Raises
------
ValueError
If the relation is not antisymmetric (its closure contains a
cycle of mutually-prerequisite items). The transitive
reduction is only well defined for partial orders; on a cyclic
relation it would silently delete real edges. Merge equivalent
items first, or check with :meth:`is_antisymmetric`.
"""
closure = self.transitive_closure()
closed = closure.relations
if any((b, a) in closed for a, b in closed):
raise ValueError(
"transitive_reduction is only defined for antisymmetric "
"relations (partial orders); this relation's closure contains "
"a cycle of mutually-prerequisite (equivalent) items. Merge "
"the equivalent items first."
)
reduced: set[tuple[str, str]] = set(closed)
for a, c in closed:
for b in self._items:
if b != a and b != c and (a, b) in closed and (b, c) in closed:
reduced.discard((a, c))
break
return SurmiseRelation(self._items, reduced)
[docs]
def prerequisites_of(self, item: str) -> frozenset[str]:
"""Return the prerequisites of an item in the stored relation.
Returns only items directly related in this instance's edges.
To get all transitive prerequisites, call ``transitive_closure()``
first, then query the result.
"""
return frozenset(a for a, b in self._relations if b == item)
[docs]
def successors_of(self, item: str) -> frozenset[str]:
"""Return the successors of an item in the stored relation.
Returns only items directly related in this instance's edges.
To get all transitive successors, call ``transitive_closure()``
first, then query the result.
"""
return frozenset(b for a, b in self._relations if a == item)
[docs]
def minimal_items(self) -> frozenset[str]:
"""Items with no prerequisites (bottom of the order)."""
has_prereq = {b for _, b in self._relations}
return self._items - has_prereq
[docs]
def maximal_items(self) -> frozenset[str]:
"""Items that are not prerequisite of anything (top of the order)."""
is_prereq = {a for a, _ in self._relations}
return self._items - is_prereq
[docs]
def levels(self) -> dict[str, int]:
"""Compute topological levels.
Level 0 items have no prerequisites. Level n items have
max predecessor level n-1.
Returns
-------
dict[str, int]
Mapping from item to its level. Items in cycles are omitted.
"""
result: dict[str, int] = {}
for item in self._items:
if not self.prerequisites_of(item):
result[item] = 0
for _ in range(len(self._items)):
progress = False
for item in self._items:
if item in result:
continue
prereqs = self.prerequisites_of(item)
if prereqs and all(p in result for p in prereqs):
result[item] = max(result[p] for p in prereqs) + 1
progress = True
if not progress:
break
return result
[docs]
def is_antisymmetric(self) -> bool:
"""Check if the relation is antisymmetric (i.e. encodes a partial order).
Antisymmetry is evaluated on the *transitive closure*: the relation
is antisymmetric iff its closure contains no symmetric pair (b, a)
for a closure pair (a, b) with a != b. This correctly detects cycles
of any length (e.g. a -> b -> c -> a), not only directly-stored
2-cycles.
"""
closed = self.transitive_closure()._relations
return all((b, a) not in closed for a, b in closed)
# ------------------------------------------------------------------
# Conversion
# ------------------------------------------------------------------
[docs]
def to_adjacency_dict(self) -> dict[str, set[str]]:
"""Return {item: set of its *direct* prerequisites}.
This is the strict (irreflexive) cover: an item is never listed as
its own prerequisite, and transitive prerequisites are excluded.
Call :meth:`transitive_closure` first for all prerequisites. For the
reflexive boolean form of the relation, use :meth:`to_matrix`.
"""
result: dict[str, set[str]] = {item: set() for item in self._items}
for a, b in self._relations:
result[b].add(a)
return result
[docs]
def to_matrix(self) -> tuple[list[str], list[list[int]]]:
"""Return (sorted items, reflexive adjacency matrix).
``matrix[i][j] == 1`` iff ``items[i]`` is a prerequisite of
``items[j]`` *or* ``i == j``. The surmise relation is reflexive, so
the diagonal is always 1 — consistent with membership testing
(``(x, x) in relation`` is always True). Off-diagonal entries
reflect the stored cover only; call :meth:`transitive_closure`
first for the full transitive matrix.
"""
ordered = sorted(self._items)
idx = {item: i for i, item in enumerate(ordered)}
n = len(ordered)
matrix = [[0] * n for _ in range(n)]
for i in range(n):
matrix[i][i] = 1 # reflexivity (surmise relations are reflexive)
for a, b in self._relations:
matrix[idx[a]][idx[b]] = 1
return ordered, matrix
# ------------------------------------------------------------------
# Factories
# ------------------------------------------------------------------
[docs]
@classmethod
def from_adjacency_matrix(
cls,
items: list[str],
matrix: list[list[int]],
) -> SurmiseRelation:
"""Create from an adjacency matrix.
matrix[i][j] = 1 means items[i] is a prerequisite of items[j].
"""
relations: set[tuple[str, str]] = set()
for i, row in enumerate(matrix):
for j, val in enumerate(row):
if val and i != j:
relations.add((items[i], items[j]))
return cls(items, relations)
[docs]
@classmethod
def from_prerequisites_dict(
cls,
prereqs: Mapping[str, Collection[str]],
) -> SurmiseRelation:
"""Create from {item: [its prerequisites]}.
Parameters
----------
prereqs : Mapping[str, Collection[str]]
For each item, the collection of its prerequisites.
"""
items = set(prereqs.keys())
relations: set[tuple[str, str]] = set()
for item, prs in prereqs.items():
for p in prs:
relations.add((p, item))
return cls(items, relations)
# ------------------------------------------------------------------
# Dunder methods
# ------------------------------------------------------------------
def __contains__(self, pair: tuple[str, str]) -> bool:
a, b = pair
if a == b:
return a in self._items # reflexivity
return pair in self._relations
def __len__(self) -> int:
return len(self._relations)
def __iter__(self) -> Iterator[tuple[str, str]]:
return iter(self._relations)
def __eq__(self, other: object) -> bool:
if not isinstance(other, SurmiseRelation):
return NotImplemented
return self._items == other._items and self._relations == other._relations
def __repr__(self) -> str:
return f"SurmiseRelation(items={len(self._items)}, relations={len(self._relations)})"