graph

func (ContribID) IsZero ¶ added in v0.1.1

func (c ContribID) IsZero() bool

IsZero reports whether c is the zero ContribID. Zero means "no identity" and disables dedup on the write path.

func (*GraphCache[S, T]) AddEdge ¶

func (c *GraphCache[S, T]) AddEdge(tail, head S, w float32)

func (*GraphCache[S, T]) AddEdgeWithExpiration ¶

func (c *GraphCache[S, T]) AddEdgeWithExpiration(tail, head S, w float32, expiration time.Time)

func (*GraphCache[S, T]) AddEdgeWithExpirationContrib ¶ added in v0.1.1

func (c *GraphCache[S, T]) AddEdgeWithExpirationContrib(tail, head S, w float32, expiration time.Time, contribID ContribID) bool

AddEdgeWithExpirationContrib is the dedup-aware additive write used by the replication apply path (#182). A non-zero contribID makes the call idempotent: re-applying the same mutation (e.g. on peer reconnect or duplicate stream delivery) leaves the stored weight unchanged. A zero contribID falls through to ordinary additive semantics, which is the local non-replicated path. Returns applied=true when the contribution was recorded; false means dedup suppressed an already-stored contribution with the same ID.

func (*GraphCache[S, T]) AddEdgeWithExpirationContribHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) AddEdgeWithExpirationContribHLC(tail, head S, w float32, expiration time.Time, contribID ContribID, ts hlc.Timestamp) bool

AddEdgeWithExpirationContribHLC is the tombstone-aware sibling of AddEdgeWithExpirationContrib used by the replication apply path (#183). When a live edge tombstone exists for (tail, head) whose HLC is strictly newer than ts the contribution is dropped and false is returned — preventing a late Add* from resurrecting a freshly-deleted edge. Otherwise behaviour matches AddEdgeWithExpirationContrib, including ContribID-based dedup. A successful apply clears any existing tombstone for the edge (the new write supersedes the deletion).

func (*GraphCache[S, T]) AddEdgeWithTTL ¶

func (c *GraphCache[S, T]) AddEdgeWithTTL(tail, head S, w float32, ttl time.Duration)

func (*GraphCache[S, T]) AddEdgesWithExpiration ¶

func (c *GraphCache[S, T]) AddEdgesWithExpiration(items []EdgeItem[S])

AddEdgesWithExpiration additively writes every supplied edge under a single write lock, auto-creating endpoint vertices on demand (matching the per-edge AddEdgeWithExpiration invariant). Concurrent readers see either the pre-batch or the post-batch state.

Each item's ContribID is honored: a non-zero id deduplicates the contribution (see AddEdgesWithExpirationContrib). Leaving ContribID at its zero value — the default — keeps the legacy non-idempotent additive path.

func (*GraphCache[S, T]) AddEdgesWithExpirationContrib ¶ added in v0.5.0

func (c *GraphCache[S, T]) AddEdgesWithExpirationContrib(items []EdgeItem[S]) (deduped int)

AddEdgesWithExpirationContrib is the dedup-aware batch sibling of AddEdgesWithExpiration. It applies the whole batch under a single write lock and returns the number of items that were deduplicated — i.e. whose non-zero ContribID matched a live contribution already stored on the (tail, head) edge, so no weight was added. Items with a zero ContribID always apply (legacy additive semantics) and never count as deduped.

The dedup guarantee mirrors the per-edge AddEdgeWithExpirationContrib used by the replication apply path (#182): replaying a batch with the same ContribIDs leaves the stored weights unchanged. This is what lets a client-supplied idempotency key make AddEdge(s) safe to retry (#588).

func (*GraphCache[S, T]) CountByPrefix ¶ added in v0.1.1

func (c *GraphCache[S, T]) CountByPrefix(prefix string) int

CountByPrefix returns the number of indexed keys whose projection starts with prefix. The count is taken from the prefix index, so it reflects entries that may have expired but not yet been flushed; for most workloads the skew is bounded by the Watch tick interval. Returns 0 when the index has not been enabled.

func (*GraphCache[S, T]) DeleteByPrefix ¶ added in v0.1.1

func (c *GraphCache[S, T]) DeleteByPrefix(ctx context.Context, prefix string, limit int) int

DeleteByPrefix removes every vertex whose projected key starts with prefix and returns the number of vertices deleted. limit caps the number of deletions in a single call; pass 0 (or a negative value) to delete the entire matching set. When the index has not been enabled, DeleteByPrefix returns 0 without touching the cache.

Deletion goes through DeleteVertex semantics for each matched key so the standard OnEvict / refcount / radix-removal chain runs uniformly. Edges incident to a deleted vertex are NOT removed eagerly here \u2014 they will be reclaimed by the next dangling-edge flush, matching the existing DeleteVertex contract.

func (*GraphCache[S, T]) DeleteByPrefixHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) DeleteByPrefixHLC(ctx context.Context, prefix string, limit uint32, ts hlc.Timestamp, expiration time.Time) (int, error)

DeleteByPrefixHLC is the tombstone-aware sibling of DeleteByPrefix: every vertex whose projected key matches prefix receives a tombstone stamped at ts/expiration. Returns the number of vertices actually deleted (matching DeleteByPrefix). limit==0 means unlimited.

func (*GraphCache[S, T]) DeleteEdge ¶

func (c *GraphCache[S, T]) DeleteEdge(tail, head S) bool

DeleteEdge removes the (tail, head) edge and returns whether it was present.

func (*GraphCache[S, T]) DeleteEdgeHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) DeleteEdgeHLC(tail, head S, ts hlc.Timestamp, expiration time.Time) bool

DeleteEdgeHLC removes the (tail, head) edge and stamps a tombstone. See DeleteVertexHLC for the late-replay rationale.

func (*GraphCache[S, T]) DeleteEdges ¶

func (c *GraphCache[S, T]) DeleteEdges(keys []EdgeKey[S]) int

DeleteEdges removes every supplied edge under a single write lock and returns the count of edges that were actually present. Concurrent readers observe either the pre-batch or the post-batch state.

func (*GraphCache[S, T]) DeleteEdgesHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) DeleteEdgesHLC(keys []EdgeKey[S], ts hlc.Timestamp, expiration time.Time) int

DeleteEdgesHLC is the batch sibling of DeleteEdgeHLC.

func (*GraphCache[S, T]) DeleteVertex ¶

func (c *GraphCache[S, T]) DeleteVertex(key S) bool

DeleteVertex removes the vertex (by key) and returns whether it was present.

func (*GraphCache[S, T]) DeleteVertexHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) DeleteVertexHLC(key S, ts hlc.Timestamp, expiration time.Time) bool

DeleteVertexHLC removes the vertex and stamps a tombstone so a late Put*/Add* with an HLC strictly older than ts is rejected for the duration of expiration. Returns whether the vertex was present at call time. Edges of the vertex are NOT tombstoned by this call — they are still GC'd via the dangling sweep when their endpoints disappear, but a late AddEdge that re-creates an endpoint can still reappear. Callers that need full subgraph fencing should pair this with DeleteEdgesHLC for the relevant (tail, head) pairs.

func (*GraphCache[S, T]) DeleteVertices ¶

func (c *GraphCache[S, T]) DeleteVertices(keys []S) int

DeleteVertices removes every supplied vertex under a single write lock and returns the count of keys that were actually present (and therefore deleted). Concurrent readers observe either the pre-batch or the post-batch state.

func (*GraphCache[S, T]) DeleteVerticesHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) DeleteVerticesHLC(keys []S, ts hlc.Timestamp, expiration time.Time) int

DeleteVerticesHLC is the batch sibling of DeleteVertexHLC. Every key receives a tombstone, including ones not present in the live cache — this is intentional so a Delete-before-Add race is still resolved by LWW once the (out-of-order) Add arrives.

func (*GraphCache[S, T]) EdgeCount ¶ added in v0.1.1

func (c *GraphCache[S, T]) EdgeCount() int

EdgeCount returns the live (tail, head) edge count under an RLock. Like VertexCount it is intended for periodic gauge sampling, not hot paths.

func (*GraphCache[S, T]) EnablePrefixIndex ¶ added in v0.1.1

func (c *GraphCache[S, T]) EnablePrefixIndex(extract func(S) string)

EnablePrefixIndex turns on the optional prefix index, projecting each key S through extract to obtain the string used by ScanByPrefix / CountByPrefix / DeleteByPrefix. It must be called before any vertex is stored; calling it on a non-empty cache panics so the caller cannot silently observe an index that disagrees with point reads. extract must not be nil.

EnablePrefixIndex is intentionally separate from the constructor:

• GraphCache is generic over S comparable, but prefix semantics are well-defined only for string-like keys. Lifting the constraint into the signature would force every caller (including those that never want prefix scans) to thread a projection through;
• opt-in keeps the put / evict hot paths free of any radix work for the existing string-keyed deployments that have not migrated.

func (*GraphCache[S, T]) GetEdgeDetail ¶

func (c *GraphCache[S, T]) GetEdgeDetail(tail, head S) (float32, time.Time, bool)

GetEdgeDetail returns the current edge weight together with the latest contribution expiration. The expiration is the moment after which the edge is guaranteed to have decayed to zero. When no edge exists, ok is false.

func (*GraphCache[S, T]) GetVertex ¶

func (c *GraphCache[S, T]) GetVertex(key S) (T, bool)

func (*GraphCache[S, T]) GetWeight ¶

func (c *GraphCache[S, T]) GetWeight(tail, head S) (float32, bool)

func (*GraphCache[S, T]) Neighbor ¶

func (c *GraphCache[S, T]) Neighbor(seed S, step int, k int, tfidf bool, selectSmallest bool) *graph.Graph[S, T]

Neighbor walks the graph from seed and returns the visited subgraph. The per-hop top-k pruning keeps the k largest-weight edges when selectSmallest is false and the k smallest-weight edges when it is true (#560) — the caller picks the direction that matches its Objective so a cost-minimiser is not handed the costliest edges. tfidf re-scores edge weights BEFORE the directional top/bottom-k selection.

func (*GraphCache[S, T]) NeighborContext ¶

func (c *GraphCache[S, T]) NeighborContext(ctx context.Context, seed S, step int, k int, tfidf bool, selectSmallest bool) (*graph.Graph[S, T], error)

NeighborContext is the context-aware variant of Neighbor. It returns ctx.Err() as soon as the context is cancelled or its deadline has expired — checked between BFS expansion steps — so handlers can short-circuit large traversals when the caller has given up.

func (*GraphCache[S, T]) NeighborWithExpirationsContext ¶

func (c *GraphCache[S, T]) NeighborWithExpirationsContext(ctx context.Context, seed S, step int, k int, tfidf bool, selectSmallest bool) (*graph.Graph[S, T], map[S]map[S]time.Time, error)

NeighborWithExpirationsContext returns the same subgraph as NeighborContext together with a parallel expirations map keyed by (tail, head). Both are computed under a single RLock so handlers can compose responses without re-acquiring the cache lock per edge.

The expirations map only contains entries for edges that ended up in the returned graph; a missing or zero value means the edge has no known expiration.

func (*GraphCache[S, T]) PutEdgeWithExpiration ¶

func (c *GraphCache[S, T]) PutEdgeWithExpiration(tail, head S, w float32, expiration time.Time)

PutEdgeWithExpiration atomically replaces the (tail, head) edge weight. AddEdgeWithExpiration is additive (Add semantics) so a naive "DeleteEdge + AddEdgeWithExpiration" sequence performed by callers exposes a window in which concurrent GetEdge readers observe a spurious NotFound. PutEdgeWithExpiration takes the write lock once and performs the delete + add under the same lock, restoring atomicity for the idempotent Put semantics.

func (*GraphCache[S, T]) PutEdgeWithExpirationHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) PutEdgeWithExpirationHLC(tail, head S, w float32, expiration time.Time, ts hlc.Timestamp) bool

PutEdgeWithExpirationHLC is the LWW-aware sibling of PutEdgeWithExpiration used by the replication apply path. Returns applied=false when the stored edge's last accepted HLC is strictly newer than ts. Endpoint vertices are auto-created (matching PutEdgeWithExpiration) regardless of the LWW outcome — the endpoints exist independently of any individual edge write's causality and must be present for downstream traversal.

func (*GraphCache[S, T]) PutEdgesWithExpiration ¶

func (c *GraphCache[S, T]) PutEdgesWithExpiration(items []EdgeItem[S])

PutEdgesWithExpiration replaces every supplied edge atomically under a single write lock. Each (tail, head) pair is deleted and re-added so the resulting weight is exactly the supplied weight — matching PutEdgeWithExpiration semantics for each item in the batch.

func (*GraphCache[S, T]) PutVertex ¶

func (c *GraphCache[S, T]) PutVertex(key S, value T)

func (*GraphCache[S, T]) PutVertexWithExpiration ¶ added in v0.1.1

func (c *GraphCache[S, T]) PutVertexWithExpiration(key S, value T, expiration time.Time)

func (*GraphCache[S, T]) PutVertexWithExpirationHLC ¶ added in v0.1.1

func (c *GraphCache[S, T]) PutVertexWithExpirationHLC(key S, value T, expiration time.Time, ts hlc.Timestamp) bool

PutVertexWithExpirationHLC is the LWW-aware sibling of PutVertexWithExpiration used by the replication apply path. When the stored HLC for key is strictly newer than ts the call is a no-op and returns applied=false. A zero ts always applies (no causality recorded). Local writers continue to use PutVertexWithExpiration; this helper is intentionally narrow to the replicated path so non-replicated workloads pay nothing.

func (*GraphCache[S, T]) PutVertexWithTTL ¶ added in v0.1.1

func (c *GraphCache[S, T]) PutVertexWithTTL(key S, value T, ttl time.Duration)

func (*GraphCache[S, T]) PutVerticesWithExpiration ¶ added in v0.1.1

func (c *GraphCache[S, T]) PutVerticesWithExpiration(items []VertexItem[S, T])

PutVerticesWithExpiration writes every supplied vertex under a single write lock. Concurrent readers observe either the pre-batch or the post-batch state — never an intermediate snapshot where some keys are present and others are not.

func (*GraphCache[S, T]) ScanByPrefix ¶ added in v0.1.1

func (c *GraphCache[S, T]) ScanByPrefix(ctx context.Context, prefix string, fn func(projected string, key S, value T) bool) bool

ScanByPrefix iterates every live vertex whose projected key starts with prefix, in lexicographic order, invoking fn for each one. fn may return false to stop the walk early; iteration also stops when ctx is cancelled. The boolean return is fn's last verdict (true means the caller exhausted the result set without asking to stop).

Consistency: ScanByPrefix takes a point-in-time snapshot of the matching (projected, key, value) triples under c.mu.RLock and then releases the lock BEFORE invoking fn. As a result fn is free to call back into any GraphCache method (including writers) without deadlock, at the cost of possibly observing keys whose live state has since changed \u2014 the snapshot itself is consistent, but the cache may have moved on by the time fn runs. Callers that need to react to the live state should re-fetch via GetVertex inside fn.

Releasing the lock before fn runs also avoids the sync.RWMutex-reentrancy hazard: a concurrent writer queued on c.mu would otherwise block any nested RLock from the visitor's goroutine (Go's RWMutex forbids recursive read-locking when a writer is waiting), which previously deadlocked callers whose fn touched the cache. See #202.

If the prefix index has not been enabled (see EnablePrefixIndex), ScanByPrefix returns false immediately and invokes fn zero times. The boolean is true if the prefix index is enabled and the walk completed without fn requesting a stop.

Vertices whose TTL has already expired but which have not yet been flushed are skipped at snapshot time \u2014 ScanByPrefix returns the same set of vertices a matching sequence of GetVertex calls under the snapshot lock would have returned.

fn receives both the projected string key (the prefix-index view) and the original S key (the cache view). For S = string they coincide; for other S the projection is intentionally lossy and the original key is the one suitable for downstream GraphCache calls.

func (*GraphCache[S, T]) ScanEdgesByPrefix ¶ added in v0.1.1

func (c *GraphCache[S, T]) ScanEdgesByPrefix(
	ctx context.Context,
	tailPrefix, headPrefix string,
	fn func(tailProjected string, tail S, headProjected string, head S, weight float32, expiration time.Time) bool,
) bool

ScanEdgesByPrefix iterates every live edge whose tail projected key starts with tailPrefix AND whose head projected key starts with headPrefix, in ascending (tail, head) order, invoking fn for each one. Either prefix may be empty to disable the corresponding filter (both empty scans every edge).

fn may return false to stop the walk early; iteration also stops when ctx is cancelled. The boolean return is fn's last verdict — true means the caller exhausted the matching set without asking to stop.

Implementation: the walk reuses the vertex-side prefix index for the tail dimension. Every edge endpoint is auto-created as a vertex on insert (see AddEdgeWithExpiration / PutEdgeWithExpiration), so the radix already covers all live tails. For each matching tail the head dimension is served by a per-tail head radix (Issue #167) when available — see scanTailHeadsFast — or falls back to the v1 materialise-and-sort path (scanTailHeadsFallback) when the head index is disabled. The two paths emit identical (tailProj, headProj) sets for any given graph state.

Locking contract is identical to ScanByPrefix: the walk holds c.mu.RLock for its duration. Callers MUST NOT invoke any GraphCache write method from inside fn. Long-running fn bodies starve writers; callers that need to do non-trivial per-edge work should accumulate into a slice and process after ScanEdgesByPrefix returns.

Returns false when the prefix index is not enabled or fn requested an early stop; true on a clean exhaustion of the matching set.

func (*GraphCache[S, T]) SetGCHooks ¶ added in v0.1.1

func (c *GraphCache[S, T]) SetGCHooks(onExpire func(kind string, n int), onGCDuration func(d time.Duration))

SetGCHooks installs optional observability callbacks invoked from Watch after every GC tick. Either argument may be nil. Hooks must not call back into the cache (re-entrant locking would deadlock). Safe for concurrent use.

func (*GraphCache[S, T]) SnapshotEdges ¶ added in v0.1.1

func (c *GraphCache[S, T]) SnapshotEdges() []SnapshotEdge[S]

SnapshotEdges returns a materialised snapshot of every live edge in the cache, preserving the per-contribution weight decomposition. The snapshot is taken under a single write-lock pass; the returned slice is independent of the cache. Edges whose every contribution has decayed are skipped (they would otherwise show up as ghost entries with zero total weight).

Memory cost is O(E + sum of bucket sizes); same scope rationale as SnapshotVertices.

func (*GraphCache[S, T]) SnapshotVertices ¶ added in v0.1.1

func (c *GraphCache[S, T]) SnapshotVertices() []SnapshotVertex[S, T]

SnapshotVertices returns a materialised snapshot of every live vertex in the cache. The snapshot is taken under a single write-lock pass; the returned slice is independent of the cache and safe to iterate without further locking. Expired vertices (those past Expiration at snapshot time) are skipped.

Memory cost is O(N) in the live vertex count — the API is intended for replication bootstrap (#184), which is a bounded, infrequent operation. Hot read paths should keep using GetVertex.

func (*GraphCache[S, T]) VertexCount ¶ added in v0.1.1

func (c *GraphCache[S, T]) VertexCount() int

VertexCount returns the live vertex count under an RLock. Intended for Prometheus gauges that sample the cache periodically.

func (*GraphCache[S, T]) Watch ¶

func (c *GraphCache[S, T]) Watch(ctx context.Context, interval time.Duration)