Skip to content

Filtrations

knowledgecomplex.filtration — Filtrations over knowledge complexes.

A filtration F = (C₀, C₁, …, Cₘ) is a nested sequence of subcomplexes where each Cₚ is a valid simplicial complex (closed under boundary) and Cₚ₋₁ ⊆ Cₚ. Filtrations are semantics-agnostic — they could represent temporal evolution, thematic layers, trust levels, or any ordering.

Filtration

An indexed sequence of nested subcomplexes over a KnowledgeComplex.

Each step is a valid subcomplex (closed under boundary) and each step contains all elements from the previous step (monotone nesting).

Parameters:

Name Type Description Default
kc KnowledgeComplex

The parent complex that this filtration is defined over.

 required
Example

filt = Filtration(kc) filt.append({"v1"}) filt.append({"v1", "v2", "e12"}) filt.append({"v1", "v2", "v3", "e12", "e23", "e13", "f123"}) len(filt) 3 filt.birth("e12") 1

Source code in knowledgecomplex/filtration.py 
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
class Filtration:
    """
    An indexed sequence of nested subcomplexes over a KnowledgeComplex.

    Each step is a valid subcomplex (closed under boundary) and each step
    contains all elements from the previous step (monotone nesting).

    Parameters
    ----------
    kc : KnowledgeComplex
        The parent complex that this filtration is defined over.

    Example
    -------
    >>> filt = Filtration(kc)
    >>> filt.append({"v1"})
    >>> filt.append({"v1", "v2", "e12"})
    >>> filt.append({"v1", "v2", "v3", "e12", "e23", "e13", "f123"})
    >>> len(filt)
    3
    >>> filt.birth("e12")
    1
    """

    def __init__(self, kc: "KnowledgeComplex") -> None:
        self._kc = kc
        self._steps: list[frozenset[str]] = []

    def __repr__(self) -> str:
        return f"Filtration(steps={len(self._steps)}, complete={self.is_complete})"

    @property
    def complex(self) -> "KnowledgeComplex":
        """The parent KnowledgeComplex."""
        return self._kc

    @property
    def length(self) -> int:
        """Number of steps in the filtration."""
        return len(self._steps)

    @property
    def is_complete(self) -> bool:
        """True if the last step contains all elements in the complex."""
        if not self._steps:
            return False
        all_ids = set(self._kc.element_ids())
        return set(self._steps[-1]) == all_ids

    def append(self, ids: set[str]) -> "Filtration":
        """
        Append a subcomplex to the filtration.

        Parameters
        ----------
        ids : set[str]
            Element IDs forming the next step. Must be a valid subcomplex
            and a superset of the previous step.

        Returns
        -------
        Filtration (self, for chaining)

        Raises
        ------
        ValueError
            If ids is not a valid subcomplex or violates monotonicity.
        """
        ids_set = set(ids)

        if not self._kc.is_subcomplex(ids_set):
            raise ValueError(
                "Cannot append: the given element set is not a valid subcomplex "
                "(not closed under boundary)"
            )

        if self._steps and not ids_set >= set(self._steps[-1]):
            raise ValueError(
                "Cannot append: monotone nesting violated — new step must be "
                "a superset of the previous step"
            )

        self._steps.append(frozenset(ids_set))
        return self

    def append_closure(self, ids: set[str]) -> "Filtration":
        """
        Append the closure of a set of elements, unioned with the previous step.

        Takes the closure of ids (ensuring a valid subcomplex), unions it
        with the previous step (ensuring monotonicity), and appends.

        Parameters
        ----------
        ids : set[str]
            Element IDs to close over.

        Returns
        -------
        Filtration (self, for chaining)
        """
        closed = self._kc.closure(ids)
        if self._steps:
            closed = closed | set(self._steps[-1])
        self._steps.append(frozenset(closed))
        return self

    @classmethod
    def from_function(
        cls,
        kc: "KnowledgeComplex",
        fn: Callable[[str], int | float],
    ) -> "Filtration":
        """
        Build a filtration by grouping elements by a function value.

        Calls fn(id) for every element in the complex, groups by return
        value, sorts groups, and builds closure at each cumulative step.

        Parameters
        ----------
        kc : KnowledgeComplex
            The parent complex.
        fn : Callable[[str], int | float]
            Function mapping element IDs to filtration values.

        Returns
        -------
        Filtration
        """
        all_ids = kc.element_ids()
        groups: dict[int | float, list[str]] = defaultdict(list)
        for eid in all_ids:
            groups[fn(eid)].append(eid)

        filt = cls(kc)
        accumulated: set[str] = set()
        for key in sorted(groups.keys()):
            accumulated = accumulated | set(groups[key])
            closed = kc.closure(accumulated)
            filt._steps.append(frozenset(closed))

        return filt

    def __getitem__(self, index: int) -> set[str]:
        return set(self._steps[index])

    def __len__(self) -> int:
        return len(self._steps)

    def __iter__(self) -> Iterator[set[str]]:
        for step in self._steps:
            yield set(step)

    def birth(self, id: str) -> int:
        """
        Return the index of the first step containing this element.

        Parameters
        ----------
        id : str
            Element identifier.

        Returns
        -------
        int

        Raises
        ------
        ValueError
            If the element does not appear in any step.
        """
        for i, step in enumerate(self._steps):
            if id in step:
                return i
        raise ValueError(f"Element '{id}' not found in any filtration step")

    def new_at(self, index: int) -> set[str]:
        """
        Return elements added at step index (Cₚ \\ Cₚ₋₁).

        Parameters
        ----------
        index : int
            Step index.

        Returns
        -------
        set[str]
        """
        current = set(self._steps[index])
        if index == 0:
            return current
        return current - set(self._steps[index - 1])

    def elements_at(self, index: int) -> set[str]:
        """
        Return all elements at step index (same as self[index]).

        Parameters
        ----------
        index : int
            Step index.

        Returns
        -------
        set[str]
        """
        return set(self._steps[index])

complex property

The parent KnowledgeComplex.

length property

Number of steps in the filtration.

is_complete property

True if the last step contains all elements in the complex.

append(ids)

Append a subcomplex to the filtration.

Parameters:

Name Type Description Default
ids set[str]

Element IDs forming the next step. Must be a valid subcomplex and a superset of the previous step.

 required

Returns:

Type Description
Filtration (self, for chaining)

Raises:

Type Description
ValueError

If ids is not a valid subcomplex or violates monotonicity.
Source code in knowledgecomplex/filtration.py 
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def append(self, ids: set[str]) -> "Filtration":
    """
    Append a subcomplex to the filtration.

    Parameters
    ----------
    ids : set[str]
        Element IDs forming the next step. Must be a valid subcomplex
        and a superset of the previous step.

    Returns
    -------
    Filtration (self, for chaining)

    Raises
    ------
    ValueError
        If ids is not a valid subcomplex or violates monotonicity.
    """
    ids_set = set(ids)

    if not self._kc.is_subcomplex(ids_set):
        raise ValueError(
            "Cannot append: the given element set is not a valid subcomplex "
            "(not closed under boundary)"
        )

    if self._steps and not ids_set >= set(self._steps[-1]):
        raise ValueError(
            "Cannot append: monotone nesting violated — new step must be "
            "a superset of the previous step"
        )

    self._steps.append(frozenset(ids_set))
    return self

append_closure(ids)

Append the closure of a set of elements, unioned with the previous step.

Takes the closure of ids (ensuring a valid subcomplex), unions it with the previous step (ensuring monotonicity), and appends.

Parameters:

Name Type Description Default
ids set[str]

Element IDs to close over.

 required

Returns:

Type Description
Filtration (self, for chaining)
Source code in knowledgecomplex/filtration.py 
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
def append_closure(self, ids: set[str]) -> "Filtration":
    """
    Append the closure of a set of elements, unioned with the previous step.

    Takes the closure of ids (ensuring a valid subcomplex), unions it
    with the previous step (ensuring monotonicity), and appends.

    Parameters
    ----------
    ids : set[str]
        Element IDs to close over.

    Returns
    -------
    Filtration (self, for chaining)
    """
    closed = self._kc.closure(ids)
    if self._steps:
        closed = closed | set(self._steps[-1])
    self._steps.append(frozenset(closed))
    return self

from_function(kc, fn) classmethod

Build a filtration by grouping elements by a function value.

Calls fn(id) for every element in the complex, groups by return value, sorts groups, and builds closure at each cumulative step.

Parameters:

Name Type Description Default
kc KnowledgeComplex

The parent complex.

 required
fn Callable[[str], int | float]

Function mapping element IDs to filtration values.

 required

Returns:

Type Description
Filtration
Source code in knowledgecomplex/filtration.py 
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
@classmethod
def from_function(
    cls,
    kc: "KnowledgeComplex",
    fn: Callable[[str], int | float],
) -> "Filtration":
    """
    Build a filtration by grouping elements by a function value.

    Calls fn(id) for every element in the complex, groups by return
    value, sorts groups, and builds closure at each cumulative step.

    Parameters
    ----------
    kc : KnowledgeComplex
        The parent complex.
    fn : Callable[[str], int | float]
        Function mapping element IDs to filtration values.

    Returns
    -------
    Filtration
    """
    all_ids = kc.element_ids()
    groups: dict[int | float, list[str]] = defaultdict(list)
    for eid in all_ids:
        groups[fn(eid)].append(eid)

    filt = cls(kc)
    accumulated: set[str] = set()
    for key in sorted(groups.keys()):
        accumulated = accumulated | set(groups[key])
        closed = kc.closure(accumulated)
        filt._steps.append(frozenset(closed))

    return filt

birth(id)

Return the index of the first step containing this element.

Parameters:

Name Type Description Default
id str

Element identifier.

 required

Returns:

Type Description
int

Raises:

Type Description
ValueError

If the element does not appear in any step.
Source code in knowledgecomplex/filtration.py 
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
def birth(self, id: str) -> int:
    """
    Return the index of the first step containing this element.

    Parameters
    ----------
    id : str
        Element identifier.

    Returns
    -------
    int

    Raises
    ------
    ValueError
        If the element does not appear in any step.
    """
    for i, step in enumerate(self._steps):
        if id in step:
            return i
    raise ValueError(f"Element '{id}' not found in any filtration step")

new_at(index)

Return elements added at step index (Cₚ \ Cₚ₋₁).

Parameters:

Name Type Description Default
index int

Step index.

 required

Returns:

Type Description
set[str]
Source code in knowledgecomplex/filtration.py 
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
def new_at(self, index: int) -> set[str]:
    """
    Return elements added at step index (Cₚ \\ Cₚ₋₁).

    Parameters
    ----------
    index : int
        Step index.

    Returns
    -------
    set[str]
    """
    current = set(self._steps[index])
    if index == 0:
        return current
    return current - set(self._steps[index - 1])

elements_at(index)

Return all elements at step index (same as self[index]).

Parameters:

Name Type Description Default
index int

Step index.

 required

Returns:

Type Description
set[str]
Source code in knowledgecomplex/filtration.py 
213
214
215
216
217
218
219
220
221
222
223
224
225
226
def elements_at(self, index: int) -> set[str]:
    """
    Return all elements at step index (same as self[index]).

    Parameters
    ----------
    index : int
        Step index.

    Returns
    -------
    set[str]
    """
    return set(self._steps[index])