"""Finite families of subsets without silently inserting structure axioms."""
from __future__ import annotations
from collections.abc import Collection, Iterator
from typing import TYPE_CHECKING
from knowledgespaces.structures.attribution import _positive_limit
if TYPE_CHECKING:
from knowledgespaces.structures.knowledge_base import KnowledgeBase
from knowledgespaces.structures.knowledge_structure import KnowledgeStructure
[docs]
class SetFamily:
"""Immutable family of subsets of an explicit finite domain.
The family and the domain may be empty. Duplicates are removed; neither
the empty set nor the full domain is inserted. This representation is
useful for bases, reductions and intermediate operations that need not
themselves be knowledge structures.
"""
__slots__ = ("_domain", "_sets")
def __init__(self, domain: Collection[str], sets: Collection[Collection[str]]) -> None:
self._domain = frozenset(domain)
self._sets = frozenset(frozenset(s) for s in sets)
if any(not s <= self._domain for s in self._sets):
raise ValueError("A family member contains items outside the domain.")
@property
def domain(self) -> frozenset[str]:
return self._domain
@property
def sets(self) -> frozenset[frozenset[str]]:
return self._sets
@property
def minimal_sets(self) -> frozenset[frozenset[str]]:
"""Inclusion-minimal members (not necessarily smallest cardinality)."""
return frozenset(s for s in self._sets if not any(t < s for t in self._sets))
@property
def maximal_sets(self) -> frozenset[frozenset[str]]:
return frozenset(s for s in self._sets if not any(s < t for t in self._sets))
def _same_domain(self, other: SetFamily) -> None:
if self._domain != other.domain:
raise ValueError("Family operations require the same item domain.")
[docs]
def union_with(self, other: SetFamily) -> SetFamily:
"""Union of the two families, without closing under item-set unions."""
self._same_domain(other)
return SetFamily(self._domain, self._sets | other.sets)
[docs]
def intersection_with(self, other: SetFamily) -> SetFamily:
"""Members occurring in both families, not pairwise set intersections."""
self._same_domain(other)
return SetFamily(self._domain, self._sets & other.sets)
def difference(self, other: SetFamily) -> SetFamily:
self._same_domain(other)
return SetFamily(self._domain, self._sets - other.sets)
[docs]
def dual(self) -> SetFamily:
"""Complement each member relative to the declared domain."""
return SetFamily(self._domain, [self._domain - s for s in self._sets])
def projection(self, domain: Collection[str]) -> SetFamily:
domain = frozenset(domain)
if not domain <= self._domain:
raise ValueError("Projection domain contains unknown items.")
return SetFamily(domain, [s & domain for s in self._sets])
[docs]
def union_closure(self, *, max_sets: int = 100_000) -> SetFamily:
"""All unions of subfamilies, including the empty union ∅.
The full declared domain is not inserted unless it is generated.
The guard bounds output cardinality and never truncates a result.
"""
_positive_limit(max_sets, "max_sets")
result: set[frozenset[str]] = {frozenset()}
for member in sorted(self._sets, key=lambda s: (len(s), sorted(s))):
for previous in tuple(result):
result.add(previous | member)
if len(result) > max_sets:
raise ValueError("Union closure exceeds max_sets.")
return SetFamily(self._domain, result)
[docs]
def intersection_closure(self, *, max_sets: int = 100_000) -> SetFamily:
"""All intersections of subfamilies, including the empty intersection Q.
Unlike kstMatrix's ``kmclosure(..., closure='intersection')``, this
closes only under intersection, not under both union and intersection.
"""
return self.dual().union_closure(max_sets=max_sets).dual()
[docs]
def union_reduction(self) -> SetFamily:
"""Remove members expressible as unions of other nonempty subfamilies.
This is the ``sets``/``kst`` reduction convention: an existing empty
member is retained, unlike a knowledge-space base. No closure is
enumerated, no endpoint is inserted, and the domain is preserved.
The result generates the same unions of nonempty subfamilies.
"""
reduced = []
for member in self:
smaller = [s for s in self._sets if s < member]
if not smaller or frozenset().union(*smaller) != member:
reduced.append(member)
return SetFamily(self._domain, reduced)
[docs]
def intersection_reduction(self) -> SetFamily:
"""Remove intersections of other nonempty subfamilies.
Dual to ``union_reduction``; an existing Q is retained. This is not
a knowledge-space base and does not require intersection closure.
"""
return self.dual().union_reduction().dual()
[docs]
def item_equivalence_classes(self) -> frozenset[frozenset[str]]:
"""Items with identical membership profiles across this family."""
groups: dict[frozenset[frozenset[str]], set[str]] = {}
for item in self._domain:
signature = frozenset(s for s in self._sets if item in s)
groups.setdefault(signature, set()).add(item)
return frozenset(frozenset(g) for g in groups.values())
[docs]
def quotient(self) -> tuple[SetFamily, dict[str, frozenset[str]]]:
"""Collapse equivalent items, returning the family and label-to-class map.
The lexicographically first original item labels each class; the
second return value makes the reduction reversible by expansion.
"""
classes = {min(c): c for c in self.item_equivalence_classes()}
representatives = {q: label for label, members in classes.items() for q in members}
return SetFamily(classes, [{representatives[q] for q in s} for s in self._sets]), classes
[docs]
def refine(self, base: KnowledgeBase, *, max_sets: int = 100_000) -> SetFamily:
"""Replace co-occurring items by the rows of a refining base.
The base domain must be a nonempty subset of a single item-equivalence
class. For each member containing that domain D, replace D in turn by
every base set; members disjoint from D stay unchanged. This is the
family-level operation described by kstMatrix ``kmrefine``. It need
not yield a knowledge structure or contain Q. To interpret the rows
as generators, explicitly call ``to_knowledge_base`` afterwards.
"""
_positive_limit(max_sets, "max_sets")
domain = base.domain
if not any(domain <= notion for notion in self.item_equivalence_classes()):
raise ValueError("Refining base domain must lie within one item-equivalence class.")
result: set[frozenset[str]] = set()
for member in self._sets:
replacements = base.base if domain <= member else {domain & member}
for replacement in replacements:
result.add((member - domain) | replacement)
if len(result) > max_sets:
raise ValueError("Refined family exceeds max_sets.")
return SetFamily(self._domain, result)
[docs]
def to_knowledge_structure(self) -> KnowledgeStructure:
"""Convert only if the family already contains ∅ and its nonempty domain."""
from knowledgespaces.structures.knowledge_structure import KnowledgeStructure
if not self._domain or frozenset() not in self._sets or self._domain not in self._sets:
raise ValueError("A knowledge structure requires a nonempty domain and both endpoints.")
return KnowledgeStructure(self._domain, self._sets)
[docs]
def to_knowledge_base(self) -> KnowledgeBase:
"""Treat this family as union generators, removing redundant rows.
The union must equal the nonempty declared domain; no state span is
enumerated. This is an explicit change of interpretation.
"""
from knowledgespaces.structures.knowledge_base import KnowledgeBase
return KnowledgeBase(self._domain, self._sets)
def __contains__(self, member: Collection[str]) -> bool:
return frozenset(member) in self._sets
def __iter__(self) -> Iterator[frozenset[str]]:
return iter(sorted(self._sets, key=lambda s: (len(s), sorted(s))))
def __len__(self) -> int:
return len(self._sets)
def __eq__(self, other: object) -> bool:
if not isinstance(other, SetFamily):
return NotImplemented
return self._domain == other._domain and self._sets == other._sets
def __repr__(self) -> str:
return f"SetFamily(n_items={len(self._domain)}, n_sets={len(self._sets)})"