"""
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) elements may occur on either an item
or a skill domain. This class supports them; item-level QUERY assumes
a discriminative domain.
Storage and views:
The class stores supplied non-reflexive pairs (a != b), which may
include transitive pairs and need not form a cover or a closed relation;
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:
"""Prerequisite pairs representing a surmise relation or its generators.
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) on the domain are omitted from storage.
Call ``transitive_closure()`` to obtain the mathematical quasi-order;
the constructor preserves the supplied generating pairs.
"""
__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:
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}"
)
if a == b:
continue # self-loops on the domain are implicit
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]:
"""Minimal elements of the generated quasi-order.
Equivalent items may be mutually prerequisite; they are minimal
when there is no prerequisite outside their equivalence class.
"""
closed = self.transitive_closure().relations
return frozenset(
q for q in self._items if all((q, p) in closed for p, r in closed if r == q)
)
[docs]
def maximal_items(self) -> frozenset[str]:
"""Maximal elements of the generated quasi-order."""
closed = self.transitive_closure().relations
return frozenset(
q for q in self._items if all((r, q) in closed for p, r in closed if p == q)
)
[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)
[docs]
def item_equivalence_classes(self) -> frozenset[frozenset[str]]:
"""Classes of mutual prerequisites in the generated quasi-order.
Uses the equivalence R intersect inverse(R) after transitive closure,
including singleton classes. No knowledge states are enumerated.
This is reduction of a quasi-order (Learning Spaces, 2011, §1.6.6).
"""
closed = self.transitive_closure()
return frozenset(
frozenset(p for p in self._items if (q, p) in closed and (p, q) in closed)
for q in self._items
)
[docs]
def quotient(self) -> tuple[SurmiseRelation, dict[str, frozenset[str]]]:
"""Reduce the generated quasi-order to a partial order on its classes.
The returned relation is transitively closed. Each class is labelled
by its lexicographically first original item, and the second result
maps that label to all members (including singleton classes).
As with SetFamily.quotient, these representatives are identifiers,
not lost or arbitrarily discarded items. The input is unchanged.
"""
closed = self.transitive_closure()
classes = {
min(group): group for group in sorted(closed.item_equivalence_classes(), key=min)
}
representatives = {q: label for label, members in classes.items() for q in members}
pairs = {(representatives[a], representatives[b]) for a, b in closed}
return SurmiseRelation(classes, pairs), classes
# ------------------------------------------------------------------
# Conversion
# ------------------------------------------------------------------
[docs]
def to_adjacency_dict(self) -> dict[str, set[str]]:
"""Return {item: set of its *direct* prerequisites}.
An item is never listed as its own prerequisite. All stored
pairs are retained, including any transitive pairs already present.
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].
Requires a square binary matrix and unique item labels.
"""
if len(set(items)) != len(items):
raise ValueError("Adjacency matrix item labels must be unique.")
if len(matrix) != len(items) or any(len(row) != len(items) for row in matrix):
raise ValueError("Adjacency matrix must be square and match the number of items.")
if any(value not in (0, 1) for row in matrix for value in row):
raise ValueError("Adjacency matrix must contain only 0 and 1.")
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)})"