pcalc.basis_topology

  1# -*- coding: utf-8 -*-
  2# Copyright (c) 2025 Krishna Kumar
  3# SPDX-License-Identifier: MIT
  4"""
  5The `BasisTopology` class defines a topological structure over a set of presences—
  6interval-based assertions of an element’s presence on a boundary. This topology enables
  7reasoning about continuity, connectedness, and neighborhood relationships among presences,
  8without assuming any geometric structure.
  9
 10---
 11
 12## Intuition
 13
 14A topology tells us which subsets of a space are considered "open"—intuitively, these
 15are the sets where you can move slightly without falling out of the set. In our case, the space
 16consists of presences, each defined over a time interval on a particular boundary.
 17
 18A topology can be generated from a collection of these open sets, called a **basis**.
 19Each basis element represents a minimal unit of observable presence, such as a single
 20presence interval or a region formed by intersections and unions of intervals of presence.
 21
 22With this structure, we can:
 23
 24- Define neighborhoods around a presence,
 25- Construct connected components or trajectories of an element,
 26- Analyze continuity and coverage properties of the observation,
 27- Build sheaf structures over local observations.
 28
 29---
 30
 31## Formal Definition
 32
 33Let $P$ be a set of presence assertions, each of the form:
 34
 35$$
 36(e, b, t_0, t_1)
 37$$
 38
 39where:
 40
 41- $e \\\in E$: the element present,
 42- $b \\\in B$: the boundary where presence is observed,
 43- $[t_0, t_1) \\\subset \\\mathbb{R}$: the half-open time interval of presence.
 44
 45A **basis** $\\\mathcal{B}$ over $P$ is a collection of subsets of $P$ such that:
 46
 471. For each $p \\\in P$, there exists some $B \\\in \\\mathcal{B}$ with $p \\\in B$,
 482. If $p \\\in B_1 \\\cap B_2$, then there exists $B_3 \\\in \\\mathcal{B}$ such that
 49   $p \\\in B_3 \\\subset B_1 \\\cap B_2$.
 50
 51The topology $\\\mathcal{T}$ generated by $\\\mathcal{B}$ is the set of all unions
 52of basis sets.
 53
 54---
 55
 56## Applications
 57
 58This structure underlies more advanced constructions such as:
 59
 60- **Connected trajectories**: identifying maximal paths of an element through multiple boundaries over time.
 61- **Presence matrices**: capturing observable structure over a timescale and supporting topological invariants
 62  across time scales.
 63- **Simplicial complexes**: revealing higher-dimensional intersections between boundaries where elements are
 64  simultaneously present, enabling analysis of boundary relationships and topological features
 65  like presence clusters and holes induced by element co-presence.
 66- **Sheaves of presence assertions**: supporting the gluing of local observations into globally coherent structures.
 67
 68The `BasisTopology` class provides methods to define, traverse, and query this topology
 69efficiently over arbitrary collections of presences defined over the domain.
 70"""
 71
 72from collections import defaultdict
 73from typing import Iterable, Tuple
 74from sortedcontainers import SortedSet
 75from .presence import PresenceAssertion, EMPTY_PRESENCE
 76
 77
 78class BasisTopology:
 79    """
 80    The foundational topology generated by a set of presence assertions.
 81
 82    Presences are treated as basis elements defining basic open sets.
 83    Internally, presences are grouped into sorted open covers per (element, boundary)
 84    and exposed through join, closure, and overlap operations.
 85    """
 86
 87    def __init__(self, presences: Iterable[PresenceAssertion]) -> None:
 88        """
 89        Initializes the topology from a set of presences.
 90
 91        Internally maintains a SortedSet for each (element, boundary) pair,
 92        ordered by onset_time for efficient merge and overlap operations.
 93        """
 94        self.cover_index: dict[Tuple, SortedSet[PresenceAssertion]] = defaultdict(
 95            lambda: SortedSet(key=presence_sort_key)
 96        )
 97
 98        for p in presences:
 99            key = (p.element, p.boundary)
100            self.cover_index[key].add(p)
101
102    def get_cover(self, element, boundary) -> SortedSet[PresenceAssertion]:
103        """
104        Returns the open cover for a given (element, boundary) pair.
105        """
106        return self.cover_index.get((element, boundary), SortedSet(key=presence_sort_key))
107
108    @staticmethod
109    def join(p1: PresenceAssertion, p2: PresenceAssertion) -> PresenceAssertion:
110        """
111        Returns the join of two basis elements if they overlap or touch in time.
112        Returns EMPTY_PRESENCE if the presences are disjoint or incompatible.
113        """
114        if (p1.element, p1.boundary) != (p2.element, p2.boundary):
115            return EMPTY_PRESENCE
116
117        if p1.reset_time < p2.onset_time != float("-inf") and p1.reset_time != float("inf"):
118            return EMPTY_PRESENCE
119        if p2.reset_time < p1.onset_time != float("-inf") and p2.reset_time != float("inf"):
120            return EMPTY_PRESENCE
121
122        return PresenceAssertion(
123            element=p1.element,
124            boundary=p1.boundary,
125            onset_time=min(p1.onset_time, p2.onset_time),
126            reset_time=max(p1.reset_time, p2.reset_time),
127            observer="join",
128        )
129
130    def closure(self) -> set[PresenceAssertion]:
131        """
132        Computes the closure under join for each cover.
133
134        Returns a deduplicated set of merged presences that cover the same regions
135        as the original topology, but without adjacent overlaps.
136        """
137        closed = set()
138
139        for key, cover in self.cover_index.items():
140            merged_cover = []
141            for p in cover:
142                if not merged_cover:
143                    merged_cover.append(p)
144                    continue
145
146                last = merged_cover[-1]
147                j = self.join(last, p)
148
149                if j is not EMPTY_PRESENCE:
150                    merged_cover[-1] = j
151                else:
152                    merged_cover.append(p)
153
154            closed.update(merged_cover)
155
156        return closed
157
158    def find_overlapping(self, presence: PresenceAssertion) -> list[PresenceAssertion]:
159        """
160        Finds all presences in the same cover that overlap with the given presence.
161
162        This is a linear scan from the first potentially overlapping point onward,
163        relying on the sorted order of onset_time.
164        """
165        key = (presence.element, presence.boundary)
166        cover = self.cover_index.get(key, SortedSet(key=presence_sort_key))
167        overlapping = []
168
169        for p in cover.irange(minimum=None, maximum=None):
170            if p.onset_time >= presence.reset_time:
171                break
172            if p.reset_time > presence.onset_time:
173                overlapping.append(p)
174
175        return overlapping
176
177    def __iter__(self):
178        for cover in self.cover_index.values():
179            yield from cover
180
181
182def presence_sort_key(p: PresenceAssertion) -> float:
183    """The default sort key for presences in an open cover is onset_time"""
184    return p.onset_time