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, Compact) take the shard mutex, copy the entry's slices with the modification applied, and publish the new entry pointer via sync/atomic.StorePointer. 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 ¶
- Variables
- type AdjList
- func (a *AdjList[N, W]) AddEdge(src, dst N, w W) error
- func (a *AdjList[N, W]) AddEdgeH(src, dst N, w W, handle uint64) error
- func (a *AdjList[N, W]) AddNode(n N) error
- func (a *AdjList[N, W]) Compact()
- func (a *AdjList[N, W]) Directed() bool
- func (a *AdjList[N, W]) HasEdge(src, dst N) bool
- func (a *AdjList[N, W]) LoadEntry(id graph.NodeID) (neighbours []graph.NodeID, weights []W)
- func (a *AdjList[N, W]) LoadEntryH(id graph.NodeID) (neighbours []graph.NodeID, weights []W, handles []uint64)
- func (a *AdjList[N, W]) Mapper() *graph.Mapper[N]
- func (a *AdjList[N, W]) MaxNodeID() graph.NodeID
- func (a *AdjList[N, W]) Multigraph() bool
- func (a *AdjList[N, W]) Neighbours(src N) iter.Seq2[N, W]
- func (a *AdjList[N, W]) Order() uint64
- func (a *AdjList[N, W]) RemoveEdge(src, dst N)
- func (a *AdjList[N, W]) Size() uint64
- type Config
Examples ¶
Constants ¶
This section is empty.
Variables ¶
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 ¶
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 ¶
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]) AddNode ¶
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]) Compact ¶
func (a *AdjList[N, W]) Compact()
Compact is a no-op in the current copy-on-write implementation: removed edges already release their slots' previous slices on the next write. It is retained for API symmetry with future backends that may benefit from explicit compaction.
func (*AdjList[N, W]) HasEdge ¶
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 ¶
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.
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.
func (*AdjList[N, W]) Mapper ¶
Mapper returns the underlying graph.Mapper that translates between user-facing N values and compact NodeIDs.
func (*AdjList[N, W]) MaxNodeID ¶
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 ¶
Multigraph reports whether parallel edges are allowed.
func (*AdjList[N, W]) Neighbours ¶
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.
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 ¶
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]) 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.
func (*AdjList[N, W]) Size ¶
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.
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
}
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.
Source Files