"""
Surmise relations (partial orders) on item domains.
A surmise relation is a partial order (reflexive, antisymmetric, 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.
Note: the class stores only strict pairs (a != b) and treats reflexivity
as implicit. The QUERY algorithm (Block 1) assumes antisymmetry during
pruning, consistent with the standard KST formulation where the surmise
relation is a partial order (Learning Spaces, Falmagne & Doignon, 2011).
References:
Falmagne, J.-C., & Doignon, J.-P. (2011).
Learning Spaces. Springer-Verlag.
"""
from __future__ import annotations
from collections.abc import Collection, Iterator, Mapping
[docs]
class SurmiseRelation:
"""A partial order on items 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). Antisymmetry is assumed by the QUERY
algorithm but 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 (Floyd-Warshall).
Returns a new SurmiseRelation containing all transitively implied pairs.
If (a, b) and (b, c) are in the relation, (a, c) is added.
"""
closed: set[tuple[str, str]] = set(self._relations)
changed = True
while changed:
changed = False
new_edges: set[tuple[str, str]] = set()
for a, b in closed:
for c, d in closed:
if b == c and (a, d) not in closed and a != d:
new_edges.add((a, d))
if new_edges:
closed |= new_edges
changed = True
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.
"""
closure = self.transitive_closure()
closed = closure.relations
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 (a partial order)."""
return all((b, a) not in self._relations for a, b in self._relations)
# ------------------------------------------------------------------
# Conversion
# ------------------------------------------------------------------
[docs]
def to_adjacency_dict(self) -> dict[str, set[str]]:
"""Return {item: set of direct prerequisites}."""
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, adjacency matrix).
matrix[i][j] = 1 iff items[i] is a prerequisite of items[j].
"""
ordered = sorted(self._items)
idx = {item: i for i, item in enumerate(ordered)}
n = len(ordered)
matrix = [[0] * n for _ in range(n)]
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)})"