Structural reports and paths

These operations complement the structural models without silently closing a family or expanding a compact base.

Item heights and compact neighbourhoods

The height of item \(q\) is \(\min\{|K|:q\in K\in\mathcal K\}-1\). It counts the smallest number of other items in a state containing \(q\). It is neither the Hasse level of an item nor the number of individually necessary prerequisites: different minimal states may use different items. For a knowledge space the minimum can be taken over its base, without enumerating the space. This is the quantity in kstMatrix::kmheights.

from knowledgespaces import KnowledgeBase, KnowledgeStructure, SetFamily

base = KnowledgeBase("abc", ["a", "b", "ac", "bc"])
assert base.item_heights == {"a": 0, "b": 0, "c": 1}
assert base.neighbourhood("a") == {frozenset(), frozenset("ab"), frozenset("ac")}
assert frozenset("a") in base.neighbourhood("a", include=True)

space = base.to_knowledge_space()
assert space.item_heights == base.item_heights
assert base.neighbourhood("a") == space.neighbourhood("a")
assert space.neighbourhood("a", distance=0, include=True) == {frozenset("a")}

KnowledgeBase.neighbourhood uses the canonical inner and outer fringes and supports radius one. KnowledgeStructure.neighbourhood also supports larger symmetric-difference radii. These radii are set distances, not graph distances, so intermediate states need not exist. Both methods require a valid centre and optionally include it. An empty neighbourhood is an empty family. No height is inferred for an unused item of an arbitrary SetFamily; the height API is defined on structures and bases, which contain or generate Q.

Paths, required states, and matrices

iter_learning_paths enumerates maximal inclusion chains. Adjacent states are inclusion covers, which may add several items. iter_gradations restricts steps to one-item additions. With default endpoints, these run from ∅ to Q; start and target select an interval. through filters either iterator to paths containing the required state, including either endpoint. A valid state outside the interval yields no paths; an unknown state raises an error.

from knowledgespaces.io.patterns import matrix_to_states, states_to_matrix
from knowledgespaces.structures.reports import is_gradation

structure = KnowledgeStructure("abc", ["a", "ab", "ac"])
paths = list(structure.iter_learning_paths(through="ab"))
assert paths == [(frozenset(), frozenset("a"), frozenset("ab"), frozenset("abc"))]
assert is_gradation(structure, paths[0])

# Matrix rows preserve the path sequence; the item order is explicit.
items = ["c", "a", "b"]
matrices = [states_to_matrix(path, items=items) for path in paths]
assert matrices[0].tolist() == [[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1]]
assert matrix_to_states(matrices[0], items=items) == paths[0]

segment = next(structure.iter_gradations(start="a", target="ab"))
assert is_gradation(structure, segment, start="a", target="ab")

is_gradation validates the supplied states, their inclusion, their one-item steps and the requested endpoints. Cardinality differences alone would incorrectly accept repetitions, deletions or item substitutions. Path enumeration can have factorial output; consume the iterator with itertools.islice when an explicitly limited sample is sufficient. This does not assert that a truncated list contains every path.

The iterator/matrix composition covers the substantive options of kstMatrix::kmlearningpaths and kmlearningpathmatrices; item labels and state identities remain separate from printing. Unlike kstpy’s learningpaths, a general learning path here need not be a gradation.

Changes involving several items

Canonical fringes contain individual items. To express the generalized kstpy.fringe(..., maxdist=...) operation, use the separate state_changes report. Its fields contain sets of changed items:

from knowledgespaces.structures.reports import state_changes

family = SetFamily("abc", ["a", "b", "abc"])
changes = state_changes(family, "a", distance=2)
assert changes.additions == {frozenset("bc")}  # a -> abc
assert changes.removals == frozenset()
assert changes.mixed == {frozenset("ab")}      # a -> b
assert changes.all_changes == changes.additions | changes.mixed
assert {changes.centre ^ change for change in changes.all_changes} == {
    frozenset("b"), frozenset("abc")
}

removals reach subsets of the centre, additions reach supersets, and mixed reaches incomparable states. With radius one, removals/additions are precisely singleton sets of the canonical fringe items. A SetFamily input retains its exact members; no endpoints or closure are inserted.

Irredundant generators and the empty-operation convention

SetFamily.union_reduction() removes members obtainable as unions of other nonempty subfamilies. intersection_reduction() does the dual operation. Both preserve the domain and require no closure enumeration. This matches the sets operations used by kst::reduction.

family = SetFamily("ab", ["", "a", "b", "ab"])
assert family.union_reduction() == SetFamily("ab", ["", "a", "b"])
assert family.intersection_reduction() == SetFamily("ab", ["a", "b", "ab"])
assert family.union_reduction().union_closure() == family.union_closure()
assert family.intersection_reduction().intersection_closure() == family.intersection_closure()

An existing ∅ is retained by union reduction, and an existing Q by intersection reduction. Neither is inserted. This differs from KnowledgeBase, which omits ∅ because it generates it by the empty union. The closure methods include the nullary operation (∅ for union, Q for intersection), whereas the sets closure uses nonempty subfamilies. For exact nonempty-closure parity, remove a generated ∅/Q when it was absent from the original family:

family = SetFamily("ab", ["a", "b"])
nonempty_unions = family.union_closure()
if frozenset() not in family:
    nonempty_unions = nonempty_unions.difference(SetFamily(family.domain, [frozenset()]))
nonempty_intersections = family.intersection_closure()
if family.domain not in family:
    nonempty_intersections = nonempty_intersections.difference(
        SetFamily(family.domain, [family.domain])
    )
assert nonempty_unions == SetFamily("ab", ["a", "b", "ab"])
assert nonempty_intersections == SetFamily("ab", ["", "a", "b"])

A reduction of an arbitrary family is not automatically a knowledge-space base. Discriminative reduction is a separate operation: family.quotient() returns the reduced family and the reversible item map.

Reference differences

The comparison uses the fixed versions kst 0.5-5, kstMatrix 3.0-0, and kstpy 1.0.0. Python follows the finite-set definitions where upstream edge cases disagree:

  • kstMatrix 3.0-0 omits paths when through is the starting state. The Python filter includes the start, as membership requires.

  • Its compact inner-fringe implementation reshapes multiple base rows inconsistently and can return neighbours that are not states; its empty-neighbourhood construction can also raise an error. For example, in {∅, {a}, {a,b,c}}, Q has no one-item neighbours. Python returns the empty family, checked against the explicit span.

  • kst::lpath_is_gradation only checks cardinality differences. Python’s public predicate additionally checks membership, inclusion and endpoints.

These are documented differences, not claims of identical output for invalid or defective upstream cases. The tests include independent finite oracles on all three-item families/structures and native comparisons.