adjlist

package
v0.8.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 14, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package adjlist provides a mutable, sharded adjacency-list backend for the gograph module.

AdjList is the canonical builder used to assemble a graph incrementally before it is frozen into an immutable CSR view for analytics. It supports directed and undirected graphs (mirrored insertion), parallel edges (multigraph mode), and self-loops.

Storage and concurrency

Storage is split into 256 independently locked shards aligned with the graph.Mapper's sharding (the low 8 bits of every NodeID identify the shard). Within a shard, adjacency entries are indexed by the intra-shard component of the NodeID — a direct slice access with no map lookup.

Reads (HasEdge, Neighbours, Order, Size) are lock-free: a reader performs a single atomic load on the shard's slot slice, a single atomic load on the slot itself, and operates on the immutable snapshot of neighbours/weights stored in the resulting entry.

Writes (AddEdge, RemoveEdge) take the shard mutex, copy the entry's slices with the modification applied, and publish the new entry pointer via sync/atomic.StorePointer. Compact likewise takes the shard mutex and republishes each slack-bearing entry with its backing arrays right-sized to exact length. Concurrent readers always observe a consistent snapshot — either the entry before the write or the entry after it.

The yield callback of AdjList.Neighbours iterates over slices owned by a snapshotted entry and may safely call any other AdjList operation; no locks are held during yield.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrShardFull = errors.New("adjlist: shard capacity exhausted")

ErrShardFull is returned by AdjList.AddNode and AdjList.AddEdge when the shard responsible for a new NodeID would have to grow beyond Config.MaxShardCapacity. Callers inspect this error with errors.Is; the AdjList state is unchanged when this error is returned (no node interned, no edge published, size counter not advanced).

Functions

This section is empty.

Types

type AdjList 

type AdjList[N comparable, W any] struct {
	// contains filtered or unexported fields
}

AdjList is a mutable adjacency-list graph generic over the user node type N and the edge weight type W. Construct one with New.

Concurrency: AdjList is safe for any number of concurrent readers (Neighbours, LoadEntry, HasEdge, Order, Size) AND concurrent writers (AddEdge, AddNode, RemoveEdge). The 256-way shard layout serialises only writers landing in the same shard; readers never take a mutex and observe a consistent snapshot via atomic.Pointer.

Bounded growth: when Config.MaxShardCapacity is set, AddEdge and AddNode return ErrShardFull instead of growing the affected shard past the cap. Callers must propagate the error and stop offering new work to the saturated shard; the AdjList state is unchanged when ErrShardFull is returned.

NodeID stability: NodeIDs assigned by the Mapper are monotonically increasing within each shard and are never reused. Removing an edge does not remove the endpoint nodes from the Mapper; their NodeIDs remain valid for the lifetime of the AdjList. Code that caches NodeIDs (e.g., an external CSR snapshot) may rely on them remaining stable as long as the originating AdjList is live.

Example

ExampleAdjList builds a small directed weighted graph and reads back its order (node count), size (edge count), and edge membership. The Config selects the graph variant; here Directed means AddEdge inserts only the forward edge. 

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
)

func main() {
	g := adjlist.New[string, int](adjlist.Config{Directed: true})

	// AddEdge auto-creates endpoint nodes; the third argument is the
	// edge weight (here an int).
	_ = g.AddEdge("a", "b", 10)
	_ = g.AddEdge("a", "c", 20)

	fmt.Println("order:", g.Order())
	fmt.Println("size:", g.Size())
	fmt.Println("a->b:", g.HasEdge("a", "b"))
	fmt.Println("b->a:", g.HasEdge("b", "a")) // directed: reverse absent
}

Output:
order: 3
size: 2
a->b: true
b->a: false
Example (Undirected)

ExampleAdjList_undirected shows that an undirected Config mirrors every insertion: AddEdge("a","b") makes both a->b and b->a present. 

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
)

func main() {
	g := adjlist.New[string, int](adjlist.Config{Directed: false})
	_ = g.AddEdge("a", "b", 1)

	fmt.Println("a->b:", g.HasEdge("a", "b"))
	fmt.Println("b->a:", g.HasEdge("b", "a"))
}

Output:
a->b: true
b->a: true

func New 

func New[N comparable, W any](cfg Config) *AdjList[N, W]

New returns an empty AdjList configured by cfg.

func (*AdjList[N, W]) AddEdge 

func (a *AdjList[N, W]) AddEdge(src, dst N, w W) error

AddEdge inserts a directed edge from src to dst with weight w, also interning the endpoints if they are not yet known. When the graph is undirected, the mirrored edge (dst, src) is inserted as well. Implements graph.Graph.

AddEdge returns ErrShardFull when Config.MaxShardCapacity is set and the responsible shard would have to grow past the cap to store the new entry. In that case no edge is published; the size counter is not advanced. The endpoints may, however, remain interned in the underlying graph.Mapper: callers that need strict orphan-free behaviour should detect ErrShardFull and treat the graph as saturated.

func (*AdjList[N, W]) AddEdgeH 

func (a *AdjList[N, W]) AddEdgeH(src, dst N, w W, handle uint64) error

AddEdgeH is AdjList.AddEdge with an explicit, caller-supplied stable edge handle. The handle is stored in the slot's parallel handle column (see [adjEntry.handles]) so the read path can recover per-slot edge identity without inferring it from CSR slot order. The handle is carried verbatim across compaction on AdjList.RemoveEdge: a surviving parallel slot keeps its original handle, and handles are never reused or renumbered.

For an undirected graph the mirrored (dst, src) slot receives the SAME handle, so both directions of one logical edge share one identity.

AddEdgeH honours the same ErrShardFull and all-or-nothing contract as AdjList.AddEdge. In simple-graph mode a duplicate (src, dst) is still a no-op and the supplied handle is ignored (the existing slot keeps its original handle).

func (*AdjList[N, W]) AddEdgeLabeled added in v0.6.0 

func (a *AdjList[N, W]) AddEdgeLabeled(src, dst N, w W, label uint32) error

AddEdgeLabeled is AdjList.AddEdge with an OPAQUE 4-byte label supplied AT edge-insertion time. The label is written into the slot's parallel label column (see [adjEntry.labels]) within the SAME O(1)-amortised append fast path that writes the neighbour and weight — no separate copy-on-write of the whole column afterwards. This is the bulk-build path for a labelled graph: a degree-d source is assembled in O(d) amortised total, not O(d²).

adjlist treats label as opaque: any uint32 is accepted, including 0 (the higher layer's "no label" sentinel). A label-free graph that never calls this method keeps the labels column nil and pays no extra memory.

For an undirected graph the mirrored (dst, src) slot receives the SAME label, so both directions of one logical edge carry the same relationship type.

AddEdgeLabeled honours the same ErrShardFull and all-or-nothing contract as AdjList.AddEdge. In simple-graph mode a duplicate (src, dst) is still a no-op and the supplied label is ignored (the existing slot keeps its label). Use AdjList.SetEdgeLabelSlot to (re)label a slot of a pre-existing edge.

func (*AdjList[N, W]) AddEdgeLabeledH added in v0.6.0 

func (a *AdjList[N, W]) AddEdgeLabeledH(src, dst N, w W, handle uint64, label uint32) error

AddEdgeLabeledH fuses AdjList.AddEdgeH and AdjList.AddEdgeLabeled: it stores both a caller-supplied stable handle and an opaque label on the new slot within the same append fast path. Both optional columns are written at position oldLen at insertion time, so a labelled, handle-carrying edge is still an O(1)-amortised append.

func (*AdjList[N, W]) AddEdgeLabeledWithProp added in v0.6.0 

func (a *AdjList[N, W]) AddEdgeLabeledWithProp(src, dst N, w W, label uint32, payload any) error

AddEdgeLabeledWithProp fuses AdjList.AddEdgeLabeled with one opaque edge-property value written into the new slot's AuxColumn AT append time. Like the label, the property value lands on the new slot at position oldLen within the SAME O(1)-amortised append that writes the neighbour and weight — no separate copy-on-write of the whole aux column afterwards. This is the bulk-build fast path for a property-carrying graph: a degree-d source that stamps one property per edge is assembled in O(d) amortised total, not the O(d²) a per-edge AdjList.UpdateEntryAux copy-on-write would cost.

payload is opaque to adjlist: it is forwarded verbatim to AuxColumn.GrowSlotWithValue when the source already has an aux column, or to the factory registered via AdjList.SetAuxFactory when this is the source's FIRST edge (no column exists yet to grow). A nil aux factory on the fresh-entry path silently drops the payload, so the higher layer must register one before using this method; lpg always does.

For an undirected graph the mirrored (dst, src) slot receives the SAME label (relationship type is symmetric) but NOT the property payload: the aux column is directional, matching AdjList.UpdateEntryAux / the higher layer's SetEdgeProperty, which writes only the source's entry. The higher layer reads a pair's properties from the source's entry, so stamping the payload only on the forward slot reproduces exactly the two-step AddEdgeLabeled + per-source property write it replaces. AddEdgeLabeledWithProp honours the same ErrShardFull and all-or-nothing contract as AdjList.AddEdge. In simple-graph mode a duplicate (src, dst) is still a no-op and neither the label nor the payload is stamped on the existing slot; use AdjList.SetEdgeLabelSlot / AdjList.UpdateEntryAux to mutate a pre-existing edge.

func (*AdjList[N, W]) AddNode 

func (a *AdjList[N, W]) AddNode(n N) error

AddNode inserts n if not already present. The node enters the adjacency list lazily on its first outgoing edge; AddNode only interns the value with the Mapper, which is sufficient for AdjList.Order to account for it. Implements graph.Graph.

AddNode never returns ErrShardFull on its own because it does not touch any shard's slot array; the bounded-growth contract becomes observable on the first AddEdge for which the responsible shard would have to grow past Config.MaxShardCapacity. The error return exists to satisfy the graph.Graph contract and to leave room for future implementations that reserve shard storage eagerly.

func (*AdjList[N, W]) BeginCommit added in v0.6.0 

func (a *AdjList[N, W]) BeginCommit()

BeginCommit opens a commit window so that the writes of one transaction clone each touched shard's slot array AT MOST ONCE (on first touch) and mutate that private builder in place for the rest of the window, instead of cloning the whole array on every write. It bounds a multi-op commit's copy-on-write cost to O(distinct shards touched) rather than O(ops). The matching AdjList.EndCommit freezes every touched shard's builder.

Single-writer contract (load-bearing)

BeginCommit/EndCommit are NOT internally synchronised and MUST be called only by a single writer that holds an exclusive section excluding every other writer AND every reader for the window's whole duration. The higher layer supplies exactly this: it brackets the visibility barrier (lpg.Graph.ApplyAtomically / LockBarrier = visMu.Lock), under which the engine is single-writer and reads run under visMu.RLock (mutually excluded). The window state (commitDepth, dirtyShards, and each shard's building) is therefore mutated by one goroutine only; it is not guarded by an atomic or a global lock because the exclusive section already guarantees that.

The only other sanctioned caller is a provably-exclusive bulk build with NO concurrent reader and NO concurrent AdjList.PinSnapshot for the window's whole duration (e.g. single-threaded WAL recovery replay, or a bulk-ingest loop the concurrent public API cannot reach). Wrapping such a loop in ONE window restores baseline write cost (clone once per shard, then in place).

Calls nest: a nested BeginCommit/EndCommit pair (e.g. an inner statement applied inside an explicit transaction that already opened the window) just adjusts the depth; only the outermost EndCommit freezes the builders.

F3.5 / #1671 UNWIND ITEM

The in-place builder mutation that makes this dedup work is correct ONLY while reads consume the adjacency under the visibility barrier. See the unwind note on [AdjList.storeEntry]: when reads go lock-free (task #1671) this shortcut must be removed in favour of true per-op/end-of-window immutable publication.

BeginCommit is safe to call only as described above; misuse (concurrent callers, or reads not excluded) is undefined.

func (*AdjList[N, W]) ClearEdgeLabelSlotValue added in v0.6.0 

func (a *AdjList[N, W]) ClearEdgeLabelSlotValue(src, dst graph.NodeID, v uint32) bool

ClearEdgeLabelSlotValue clears the opaque label of the FIRST adjacency slot of src whose neighbour is dst AND whose label equals v, publishing a new immutable entry snapshot. It returns true when such a slot was found and cleared. This targets a specific label value so a multigraph pair whose parallel slots carry different labels can drop exactly one of them without disturbing the others. No-op when v is 0, src has no label column, or no dst-matching slot carries v.

Concurrency: copy-on-write, identical to AdjList.SetEdgeLabelSlot; safe for concurrent use.

func (*AdjList[N, W]) ClearEdgeLabelSlots added in v0.6.0 

func (a *AdjList[N, W]) ClearEdgeLabelSlots(src, dst graph.NodeID)

ClearEdgeLabelSlots clears the opaque label of EVERY adjacency slot of src whose neighbour is dst (all parallel slots in a multigraph), publishing a single new immutable entry snapshot. It is the bulk inverse used when the last edge between an endpoint pair is removed and the higher layer must drop the pair's per-slot labels in lockstep with its own overflow state. No-op (and no allocation) when src has no label column or no dst-matching slot carries a label.

Concurrency: copy-on-write, identical to AdjList.SetEdgeLabelSlot; safe for concurrent use.

func (*AdjList[N, W]) Compact 

func (a *AdjList[N, W]) Compact(ctx context.Context)

Compact right-sizes every adjacency entry's backing arrays to their exact live length, reclaiming the slack left by geometric (×2) append growth. After a bulk build a degree-d hub typically over-allocates its neighbours/weights (and optional handles/labels) columns by up to ~2×; across a graph the wasted capacity averages ≈21% of the adjacency arrays. Compact walks every shard, and for each occupied slot whose entry has any column with spare capacity (cap > len) it builds a fresh entry whose every column is allocated at EXACT length (cap == len), copying only the live [0:len] data, then publishes it via the same atomic store-pointer mechanism the writers use. Entries with no slack (every column already cap == len) are skipped to avoid useless churn.

Compact is best run once after a build-then-query workload has finished mutating the graph and before the read-heavy query phase, so the resident footprint reflects the tight arrays.

Concurrency: Compact is safe for concurrent use with lock-free readers. It takes one shard mutex at a time (never two simultaneously, so it can never participate in a lock-ordering cycle with the two-lock cross-shard [AdjList.addEdge] path) and publishes each trimmed entry with sync/atomic.StorePointer. A reader holding the prior entry pointer keeps iterating the old, untrimmed — but never mutated — backing arrays; a reader that loads after the store observes the trimmed entry. No reader ever sees a torn or half-trimmed entry. The trimmed entry preserves the nil-vs-empty distinction of the optional handles/labels columns exactly: a nil column stays nil (a label- or handle-free graph never gains a zero-length slice).

Compact honours ctx cancellation between shards, so a cancelled Compact of a very large graph stops promptly with whatever shards it has already trimmed left consistently published.

func (*AdjList[N, W]) Config added in v0.2.0 

func (a *AdjList[N, W]) Config() Config

Config returns the Config the AdjList was constructed with. The configuration is fixed at New and never mutated thereafter, so Config is safe to call concurrently with any other operation and always returns the same value for the lifetime of the AdjList. It is used by the snapshot writer to persist the originating graph's directed/multigraph shape so recovery can reconstruct the same variant instead of guessing.

func (*AdjList[N, W]) Directed 

func (a *AdjList[N, W]) Directed() bool

Directed reports whether the graph is directed.

func (*AdjList[N, W]) EndCommit added in v0.6.0 

func (a *AdjList[N, W]) EndCommit()

EndCommit closes the innermost commit window opened by AdjList.BeginCommit. On the OUTERMOST close (depth returns to 0) it freezes every shard touched during the window: it clears each dirty shard's private builder so the already-published slot array becomes immutable (no further in-place write can reach it), and resets the dirty list. Nested closes only decrement the depth.

The published slotsRef of each touched shard already reflects every write of the window (storeEntry published the builder on first touch), so EndCommit performs no additional atomic store — it only relinquishes the right to mutate the builders in place. EndCommit must be called by the same writer that called BeginCommit, exactly once per BeginCommit, under the same exclusive section.

func (*AdjList[N, W]) HasEdge 

func (a *AdjList[N, W]) HasEdge(src, dst N) bool

HasEdge reports whether an edge from src to dst is present. HasEdge is lock-free and allocation-free on the hot path. Implements graph.Graph.

func (*AdjList[N, W]) LoadEntry 

func (a *AdjList[N, W]) LoadEntry(id graph.NodeID) (neighbours []graph.NodeID, weights []W)

LoadEntry returns immutable snapshots of the neighbours and parallel weights of the node identified by id, or (nil, nil) if id has no outgoing edges. The returned slices are owned by the current adjacency snapshot and must not be mutated by the caller.

For a weightless graph (see Config.Weightless) the weights return is always nil even when neighbours is non-empty; callers that index it positionally must nil-check and treat an absent weight as the zero value of W.

func (*AdjList[N, W]) LoadEntryAux added in v0.6.0 

func (a *AdjList[N, W]) LoadEntryAux(id graph.NodeID) AuxColumn

LoadEntryAux returns the opaque AuxColumn currently attached to the adjacency entry of the node identified by id, or nil when id has no outgoing edges or no caller has attached an aux column via AdjList.UpdateEntryAux. The returned column is part of the current immutable adjacency snapshot and must not be mutated by the caller; the higher layer reads it lock-free. To align positionally with the column, read the neighbours from the SAME logical snapshot via AdjList.LoadEntry and bound any per-slot scan by the shorter of the two lengths (a concurrent writer may publish a longer neighbours snapshot after the column is loaded).

LoadEntryAux is lock-free and safe for concurrent use.

func (*AdjList[N, W]) LoadEntryH 

func (a *AdjList[N, W]) LoadEntryH(id graph.NodeID) (neighbours []graph.NodeID, weights []W, handles []uint64)

LoadEntryH returns immutable snapshots of the neighbours, parallel weights, and parallel stable handles of the node identified by id. The handles slice is nil when this graph carries no per-slot handles (no caller ever used AdjList.AddEdgeH for id); when non-nil it is the same length as neighbours and handles[i] is the stable handle of the edge to neighbours[i]. The returned slices are owned by the current adjacency snapshot and must not be mutated by the caller.

For a weightless graph (see Config.Weightless) the weights return is always nil even when neighbours is non-empty; the CSR builder relies on this to skip the weights array (see graph/csr.BuildFromAdjList).

func (*AdjList[N, W]) LoadEntryLabels added in v0.6.0 

func (a *AdjList[N, W]) LoadEntryLabels(id graph.NodeID) []uint32

LoadEntryLabels returns an immutable snapshot of the optional per-slot label column of the node identified by id, or nil when id has no outgoing edges or no caller has ever set a label on any of id's slots. When non-nil the slice is the same length as the neighbours returned by AdjList.LoadEntry and labels[i] is the OPAQUE label value of the edge to neighbours[i] (0 means "no label on that slot"). adjlist never interprets the value; the higher layer owns its meaning. The returned slice is owned by the current adjacency snapshot and must not be mutated by the caller.

func (*AdjList[N, W]) Mapper 

func (a *AdjList[N, W]) Mapper() *graph.Mapper[N]

Mapper returns the underlying graph.Mapper that translates between user-facing N values and compact NodeIDs.

func (*AdjList[N, W]) MaxNodeID 

func (a *AdjList[N, W]) MaxNodeID() graph.NodeID

MaxNodeID returns one more than the largest graph.NodeID that has been assigned by the underlying Mapper. The value is a stable upper bound on the NodeID space at the moment of the call and is the natural size of a NodeID-indexed companion array (for example, the CSR offsets array).

func (*AdjList[N, W]) Multigraph 

func (a *AdjList[N, W]) Multigraph() bool

Multigraph reports whether parallel edges are allowed.

func (*AdjList[N, W]) Neighbours 

func (a *AdjList[N, W]) Neighbours(src N) iter.Seq2[N, W]

Neighbours returns an iterator over the live out-neighbours of src and the weight of each connecting edge. The iterator captures a consistent immutable snapshot of src's adjacency at the time of the first call; concurrent mutations of src after that point do not affect this iteration. Implements graph.Graph.

For a weightless graph (see Config.Weightless) the entry carries no weights column, so every neighbour is yielded with the zero value of W — the all-zero "unweighted" representation.

Example

ExampleAdjList_Neighbours iterates the out-neighbours of a node with the Go 1.23 range-over-func form, yielding each neighbour together with its edge weight. Iteration order is unspecified. 

package main

import (
	"fmt"

	"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
)

func main() {
	g := adjlist.New[string, int](adjlist.Config{Directed: true})
	_ = g.AddEdge("a", "b", 10)
	_ = g.AddEdge("a", "c", 20)

	for n, w := range g.Neighbours("a") {
		fmt.Printf("a -> %s (weight %d)\n", n, w)
	}
}

Output:
a -> b (weight 10)
a -> c (weight 20)

func (*AdjList[N, W]) Order 

func (a *AdjList[N, W]) Order() uint64

Order returns the number of distinct nodes currently referenced. The count is read from the underlying graph.Mapper, which acts as the authoritative registry. Order is O(shardCount) and intended for occasional inspection rather than hot-path use. Implements graph.Graph.

func (*AdjList[N, W]) PinSnapshot added in v0.6.0 

func (a *AdjList[N, W]) PinSnapshot() *Snapshot[N, W]

PinSnapshot captures the current per-shard adjacency versions and returns an immutable Snapshot over them. It performs one atomic load per shard (shardCount loads total) and allocates a single Snapshot; it takes no lock and never blocks a writer. A nil shard version (a shard that has never been written) is captured as nil and read back as an empty adjacency, so an empty or partially-populated graph is handled without special-casing.

PinSnapshot is lock-free and safe for concurrent use. The returned Snapshot is valid until it is dropped; the captured versions are kept alive by the reference and reclaimed by GC afterwards.

func (*AdjList[N, W]) RemoveAllEdgesFrom added in v0.3.0 

func (a *AdjList[N, W]) RemoveAllEdgesFrom(src N)

RemoveAllEdgesFrom removes all edges incident from src in O(d) time for a degree-d hub, instead of the O(d²) cost of d sequential AdjList.RemoveEdge calls.

For directed graphs the method zeroes src's adjacency slot atomically and decrements the edge counter by the number of removed edges. For undirected graphs it additionally removes the mirror entry (src from each dst's list) with one removeOneEdge call per neighbour; those calls are each O(degree-of- dst), which is O(1) for typical star topologies.

Concurrent readers observe either the full pre-deletion state or the post- deletion state; no partial state is ever visible (the src slot is published atomically, and each mirror removal is a separate atomic store).

RemoveAllEdgesFrom is safe for concurrent use.

func (*AdjList[N, W]) RemoveEdge 

func (a *AdjList[N, W]) RemoveEdge(src, dst N)

RemoveEdge removes the directed edge from src to dst if present. For multigraphs only one occurrence is removed per call. The endpoints remain in the graph. Implements graph.Graph.

For undirected multigraphs, after removing the first-match slot from the forward direction, the mirror is removed by handle identity (when the removed slot carried a non-zero handle). This ensures that — even after concurrent parallel adds that may have reshuffled slot positions relative to what they were at creation time — the same logical edge is retired from both directions. When no handle is present (plain AddEdge path) the mirror falls back to first-match behaviour, which is correct in the single-writer case that plain AddEdge implies.

func (*AdjList[N, W]) SetAuxFactory added in v0.6.0 

func (a *AdjList[N, W]) SetAuxFactory(fn func(length int, payload any) AuxColumn)

SetAuxFactory registers the constructor the fused property-carrying append path uses to build the higher layer's opaque AuxColumn for the FIRST edge of a node (see the auxFactory field). It must be called once, before any fused AdjList.AddEdgeLabeledWithProp that may create a node's first edge, and is the seam that lets adjlist stay oblivious to the column's concrete type: the factory is owned by the higher layer (lpg) and produces a single-slot block carrying the supplied payload at slot 0.

SetAuxFactory is not safe to call concurrently with itself or with fused appends; it is part of one-time wiring at graph construction.

func (*AdjList[N, W]) SetEdgeLabelSlot added in v0.6.0 

func (a *AdjList[N, W]) SetEdgeLabelSlot(src, dst graph.NodeID, v uint32) bool

SetEdgeLabelSlot stores the opaque label value v on the first adjacency slot of src whose neighbour is dst, publishing a new immutable entry snapshot. It returns true when such a slot was found and updated, false when src has no edge to dst (the caller's higher layer is responsible for the no-live-edge case via its own overflow store).

adjlist treats v as opaque: any uint32 is accepted, including 0 (which the higher layer uses as the "no label" sentinel, so passing 0 clears the slot's label). When src's entry carries no label column yet, one is allocated lazily, length-aligned with neighbours, with every other slot at 0; a label-free graph therefore never pays for the column.

Cost: one call is O(degree(src)) — it scans src's neighbours for the slot and copies the whole label column to publish the change. A loop that re-labels every one of a hub's d slots one call at a time is therefore O(d²); use AdjList.SetEdgeLabelSlots to re-label many slots in a single O(d) copy-on-write publication instead.

Concurrency: the update is copy-on-write. The label column (and the entry) is copied with the change applied and published via the same atomic store-pointer mechanism as AdjList.AddEdgeH; the slot's existing index is never mutated in place, so a concurrent lock-free reader holding the prior snapshot is unaffected. SetEdgeLabelSlot is safe for concurrent use.

func (*AdjList[N, W]) SetEdgeLabelSlots added in v0.6.0 

func (a *AdjList[N, W]) SetEdgeLabelSlots(src graph.NodeID, updates map[graph.NodeID]uint32) int

SetEdgeLabelSlots stores opaque label values on many of src's adjacency slots in a SINGLE copy-on-write publication. For each (neighbour, value) pair in updates it writes value to the FIRST slot of src whose neighbour matches — the same first-slot rule as AdjList.SetEdgeLabelSlot — and returns the number of slots written. A zero value clears that slot's label, exactly as SetEdgeLabelSlot(…, 0) does. Neighbours in updates that src has no slot for are ignored.

This is the amortized bulk form: the whole label column is copied at most once and the new entry is published once, regardless of how many slots are written. Re-labelling all d outgoing slots of a hub therefore costs O(d), versus the O(d²) of d separate AdjList.SetEdgeLabelSlot calls — each of which copies the entire column. Prefer this method for bulk or post-build re-labelling. The column is allocated lazily, so a call that matches no neighbour neither allocates nor publishes.

Concurrency: copy-on-write, identical to AdjList.SetEdgeLabelSlot. The existing column is never mutated in place — a fresh column is published via the same atomic store-pointer mechanism — so a concurrent lock-free reader holding the prior snapshot is unaffected. Safe for concurrent use.

func (*AdjList[N, W]) Size 

func (a *AdjList[N, W]) Size() uint64

Size returns the number of edges currently in the graph. For an undirected graph each AddEdge call is counted once; the mirrored neighbour entry is stored but not double-counted. In multigraph mode every parallel edge counts. Implements graph.Graph.

func (*AdjList[N, W]) UpdateEntryAux added in v0.6.0 

func (a *AdjList[N, W]) UpdateEntryAux(
	src graph.NodeID,
	fn func(cur AuxColumn, neighbours []graph.NodeID) (AuxColumn, bool),
) bool

UpdateEntryAux atomically replaces the opaque AuxColumn of src's adjacency entry under the shard write lock, using the caller-supplied transform fn. fn receives the entry's CURRENT aux column (nil when none has been attached yet) and an immutable snapshot of its neighbours, and returns the NEW aux column plus a bool reporting whether anything changed. When fn reports false the entry is left untouched and no new snapshot is published; when it reports true a fresh immutable [adjEntry] sharing the unchanged neighbours / weights / handles / labels headers and carrying the returned aux is published via the same atomic store-pointer mechanism the writers use.

UpdateEntryAux returns false when src has no adjacency entry (no outgoing edge), in which case fn is not called — the higher layer's contract is that an aux value (an edge property) is only ever attached to a live edge slot, so there is no entry to attach to. It returns the bool fn reported otherwise.

The transform MUST build the new column copy-on-write and return it fully-populated: adjlist publishes it with a single atomic store, so a concurrent lock-free reader observes either the prior column or the new one, never a half-built column. fn runs under the shard write lock and must not call back into any AdjList method that takes the same shard lock.

UpdateEntryAux is safe for concurrent use.

func (*AdjList[N, W]) Weightless added in v0.6.0 

func (a *AdjList[N, W]) Weightless() bool

Weightless reports whether the graph carries no per-edge weight column (see Config.Weightless). When true, AdjList.LoadEntry and AdjList.LoadEntryH always return a nil weights slice and the weight argument of AdjList.AddEdge is ignored. The CSR builder (graph/csr.BuildFromAdjList) reads this to skip the weights array, so a weightless graph yields a nil-weights CSR that the snapshot writer persists with hasWeights=0. The value is fixed at New and never mutated, so Weightless is safe to call concurrently with any other operation.

type AuxColumn added in v0.6.0 

type AuxColumn interface {
	// GrowSlot returns a new column of length oldLen+1 whose existing slots
	// [0,oldLen) are unchanged and whose new slot at index oldLen is ABSENT
	// (carries no value — the implementation must clear any presence/validity
	// bit for that slot, never reusing a stale value from recycled backing
	// storage). oldLen is the neighbour count of the entry BEFORE the append.
	GrowSlot(oldLen int) AuxColumn

	// GrowSlotWithValue is the value-carrying analogue of [AuxColumn.GrowSlot]:
	// it returns a new column of length oldLen+1 whose existing slots [0,oldLen)
	// are unchanged and whose new slot at index oldLen is PRESENT, carrying the
	// opaque payload. adjlist never interprets payload; it forwards verbatim the
	// value the higher layer supplied to the fused append entry point so the
	// per-slot value is written during the same O(1)-amortised append that grows
	// the entry, with no separate copy-on-write of the whole column afterwards
	// (the mechanism that makes a bulk property-carrying build O(degree) per
	// source rather than O(degree²)).
	//
	// The new slot at oldLen MUST be marked present (its validity bit set, or
	// for a sparse representation its index appended) so a subsequent read finds
	// the value — this is the only structural difference from [AuxColumn.GrowSlot],
	// which leaves the slot absent. Because oldLen is strictly greater than every
	// existing slot index, an implementation may append the value at the tail of
	// its backing (and, for a coordinate-list representation, append oldLen at the
	// end of its strictly-ascending index array) in O(1) amortised — never an
	// ordered insert.
	//
	// Like [AuxColumn.GrowSlot] the returned column is a fresh immutable
	// copy-on-write value published the same lock-free way; the receiver is never
	// mutated. oldLen is the neighbour count of the entry BEFORE the append.
	GrowSlotWithValue(oldLen int, payload any) AuxColumn

	// CompactSlot returns a new column of length n-1 with the slot at idx
	// excised: result slots [0,idx) equal the receiver's [0,idx) and result
	// slots [idx,n-1) equal the receiver's [idx+1,n). idx is a valid index in
	// [0,n) where n is the receiver's current length.
	CompactSlot(idx int) AuxColumn

	// Compact returns a column logically equal to the receiver but with its
	// internal backing storage right-sized to the live contents, reclaiming any
	// slack an amortised-growth build path left behind, or the receiver itself
	// when it already holds no slack. It is the column analogue of
	// [AdjList.Compact]'s topology-array trimming and is invoked from the same
	// pass. An implementation whose representation is always exactly sized (no
	// over-allocation) may return the receiver unchanged. The returned column
	// must read identically to the receiver and is published the same lock-free
	// way, so it must be a fresh immutable value when it differs.
	Compact() AuxColumn
}

AuxColumn is an opaque, immutable per-entry side column the higher layer attaches to a node's adjacency entry to carry one logical value per neighbour slot, aligned 1:1 to the entry's neighbours array. adjlist never interprets the contents; it only drives the column's lifecycle so the per-slot alignment is preserved across the two structural slot mutations adjlist performs:

  • an APPEND grows the entry by one slot at position oldLen;
  • a REMOVE excises one slot at position idx and shifts the tail down.

Both lifecycle methods return a NEW immutable column (copy-on-write); the receiver is never mutated, so a concurrent lock-free reader holding the prior entry (and thus the prior column) is unaffected. An implementation must keep its own length equal to the entry's neighbour count at all observable points.

Concurrency: an AuxColumn value is published as part of an immutable [adjEntry] via atomic.StorePointer and is read lock-free thereafter, so an implementation must be safe for concurrent reads once returned from a lifecycle method. adjlist holds the shard mutex when it calls GrowSlot / CompactSlot, so those calls never race each other for one entry.

type Config 

type Config struct {
	// Directed, when true, treats AddEdge as a directed insertion. When
	// false, AddEdge also inserts the reverse edge (mirrored insertion).
	Directed bool

	// Multigraph, when true, allows parallel edges between the same
	// pair of endpoints; AddEdge always appends. When false (simple
	// graph), repeated AddEdge calls on the same endpoint pair are
	// idempotent — the existing edge stays and the new weight is
	// ignored.
	Multigraph bool

	// MaxShardCapacity, when > 0, caps the number of node-slots that
	// any individual shard may grow to. AddNode (or AddEdge that
	// would create a new node or store an outgoing entry in the
	// responsible shard) returns [ErrShardFull] when growth past the
	// cap would otherwise occur; the AdjList state is left unchanged.
	// The default (0) places no upper bound — a shard doubles its
	// slot slice indefinitely.
	MaxShardCapacity int

	// Weightless, when true, builds a graph that carries NO per-edge weight
	// payload: the [adjEntry.weights] column is never allocated and stays nil
	// for every node, so a degree-d hub costs d fewer W values (8 B/edge for
	// the common W=float64). The weight argument of [AdjList.AddEdge] and the
	// fused-append entry points is accepted but IGNORED, and [AdjList.LoadEntry]
	// / [AdjList.LoadEntryH] return a nil weights slice. This is the explicit
	// "unweighted graph" representation: every edge is treated as having the
	// zero value of W (NOT 1), exactly the all-zero special case the immutable
	// CSR snapshot already encodes for a zero-size W (see [graph/csr]).
	//
	// Weightless is the right choice for a property graph queried only by
	// relationships and properties — for example the Cypher engine, which is
	// hardwired to W=float64 yet never reads edge weights. It is left
	// caller-opt-in (the engine is not auto-defaulted to it) because the weight
	// column is load-bearing for weighted algorithms.
	//
	// Contract for weighted algorithms: a weightless graph models the weight≡0
	// special case. Structure-only algorithms (BFS, DFS, connectivity,
	// PageRank, label propagation, unweighted betweenness) are unaffected —
	// they never read the weight. Weight-consuming algorithms (Dijkstra, A*,
	// Bellman-Ford, Johnson, weighted betweenness, MST, max-flow) run on a
	// weightless graph as if every edge weight were 0, which yields degenerate
	// all-zero distances — this is NOT BFS hop count (that would require every
	// weight to be 1). Do not enable Weightless for a graph you intend to query
	// with a weighted algorithm.
	//
	// Weightless is fixed at [New] and never mutated, so [AdjList.Weightless]
	// is safe for concurrent use and always returns the same value for the
	// lifetime of the AdjList.
	Weightless bool
}

Config selects the variant of graph implemented by an AdjList.

The zero value (Directed=false, Multigraph=false) builds a simple undirected graph, which is rarely what users want; prefer constructing a Config explicitly.

type Snapshot added in v0.6.0 

type Snapshot[N comparable, W any] struct {
	// contains filtered or unexported fields
}

Snapshot is an immutable, pinned view of an AdjList's adjacency captured at one instant: it holds, per shard, the [shardSlots] version that was current when the snapshot was taken (task #1526, F3.2). Because every adjacency write now publishes a FRESH immutable shardSlots (copy-on-write — see [storeEntry]) rather than mutating the published one in place, the per-shard versions a Snapshot captured stay valid and unchanged for the snapshot's whole lifetime, even while concurrent writers publish newer versions the Snapshot does not see. The Go garbage collector reclaims a retired version once the last Snapshot (and any other reader) holding it is released — the runtime supplies the RCU grace period.

A Snapshot reads adjacency exactly like the live AdjList accessors (Snapshot.LoadEntry, Snapshot.LoadEntryH, Snapshot.LoadEntryLabels, Snapshot.LoadEntryAux, Snapshot.HasEdge) but resolves every slot through its pinned per-shard versions instead of re-loading slotsRef per call, so all reads of one query observe a single, transaction-atomic adjacency state.

Concurrency and the current isolation contract

Snapshot is the in-memory groundwork for a future lock-free adjacency read path (task #1671). In the current stage adjacency reads still run under the higher layer's visibility barrier (lpg.Graph.View / ApplyAtomically), which already gives a barriered reader a stable cross-substructure instant; the pin's per-query stability is therefore redundant with — never weaker than — the barrier today. The Snapshot becomes load-bearing only when reads move out from under the barrier, at which point its pinned immutable versions are what keep an unbarriered reader from observing a partial transaction's adjacency.

The mapper is shared (not copied): NodeIDs are stable for the AdjList's lifetime, so resolving a captured NodeID through the live mapper is sound. Order and Size are intentionally NOT snapshotted here (they read the live mapper / size counter); a Snapshot pins the adjacency topology, which is the F3.2 scope.

Snapshot is safe for concurrent reads from any number of goroutines.

func (*Snapshot[N, W]) HasEdge added in v0.6.0 

func (s *Snapshot[N, W]) HasEdge(src, dst N) bool

HasEdge reports whether the pinned snapshot holds an edge from src to dst, mirroring AdjList.HasEdge. It resolves both endpoints through the shared mapper (NodeIDs are stable for the AdjList's lifetime) and scans the pinned neighbours of src.

func (*Snapshot[N, W]) LoadEntry added in v0.6.0 

func (s *Snapshot[N, W]) LoadEntry(id graph.NodeID) (neighbours []graph.NodeID, weights []W)

LoadEntry returns the pinned neighbours and weights of id, mirroring AdjList.LoadEntry but reading the snapshot's captured per-shard version. The returned slices are owned by the immutable snapshot and must not be mutated. weights is nil for a weightless graph.

func (*Snapshot[N, W]) LoadEntryAux added in v0.6.0 

func (s *Snapshot[N, W]) LoadEntryAux(id graph.NodeID) AuxColumn

LoadEntryAux returns the pinned opaque AuxColumn of id, mirroring AdjList.LoadEntryAux over the snapshot's captured version.

func (*Snapshot[N, W]) LoadEntryH added in v0.6.0 

func (s *Snapshot[N, W]) LoadEntryH(id graph.NodeID) (neighbours []graph.NodeID, weights []W, handles []uint64)

LoadEntryH returns the pinned neighbours, weights, and stable handles of id, mirroring AdjList.LoadEntryH over the snapshot's captured version.

func (*Snapshot[N, W]) LoadEntryLabels added in v0.6.0 

func (s *Snapshot[N, W]) LoadEntryLabels(id graph.NodeID) []uint32

LoadEntryLabels returns the pinned per-slot label column of id, mirroring AdjList.LoadEntryLabels over the snapshot's captured version.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.