Documentation
¶
Overview ¶
Package csr provides an immutable Compressed Sparse Row (CSR) view of a graph for read-mostly analytical workloads.
CSR stores adjacency as two parallel arrays: vertices, a length V+1 offsets array such that the out-neighbours of node id occupy the half-open range edges[vertices[id]:vertices[id+1]]; and edges itself, a flat array of NodeIDs sorted by source. Weighted graphs additionally carry a parallel weights array of the same length as edges.
The layout is the de-facto standard for high-performance graph analytics (Mehlhorn-Sanders, GraphBLAS, GAP, Gunrock). Because the arrays are contiguous and source-sorted, full-graph scans achieve peak memory bandwidth; because the structure is immutable, reads are completely lock-free and trivially safe under any level of concurrency.
Index ¶
- Constants
- Variables
- func OrderRuns[W any](vertices []uint64, edges []graph.NodeID, weights []W, handles []uint64)
- type CSR
- func BuildFromAdjList[N comparable, W any](adj *adjlist.AdjList[N, W]) *CSR[W]
- func BuildFromAdjListAsOf[N comparable, W any](adj *adjlist.AdjList[N, W], live func(graph.NodeID) bool, startTS, txID uint64) *CSR[W]
- func BuildFromAdjListLive[N comparable, W any](adj *adjlist.AdjList[N, W], live func(graph.NodeID) bool) *CSR[W]
- func FromArrays[W any](vertices []uint64, edges []graph.NodeID, weights []W, order, size uint64) *CSR[W]
- func (c *CSR[W]) BuildReverse() *CSR[W]
- func (c *CSR[W]) EdgesSlice() []graph.NodeID
- func (c *CSR[W]) HandlesSlice() []uint64
- func (c *CSR[W]) IsSymmetric() bool
- func (c *CSR[W]) LiveCount() int
- func (c *CSR[W]) LiveMask() []bool
- func (c *CSR[W]) LiveNodes() []graph.NodeID
- func (c *CSR[W]) MaxNodeID() graph.NodeID
- func (c *CSR[W]) NeighbourRange(src graph.NodeID) (Range, bool)
- func (c *CSR[W]) NeighboursByID(src graph.NodeID) iter.Seq2[graph.NodeID, W]
- func (c *CSR[W]) Order() uint64
- func (c *CSR[W]) RunsOrdered() bool
- func (c *CSR[W]) Size() uint64
- func (c *CSR[W]) Validate() error
- func (c *CSR[W]) VerticesSlice() []uint64
- func (c *CSR[W]) WeightsSlice() []W
- type Intersector
- type Range
Examples ¶
Constants ¶
const MaxIntersectWays = 8
MaxIntersectWays bounds how many ranges one Intersector can intersect.
The bound is explicit rather than dynamic because the project forbids unbounded per-operation state, and because the pattern shapes that reach this primitive are small by construction: a variable in a Cypher pattern acquires one participating range per already-bound neighbour, so a triangle or a square needs 2 and a densely chorded pattern needs 3–4. Eight leaves generous headroom while keeping the cursor arrays inside a couple of cache lines.
Variables ¶
var ErrMalformedCSR = errors.New("csr: malformed snapshot")
ErrMalformedCSR is returned (wrapped) by CSR.Validate when the snapshot's backing arrays are internally inconsistent — for example an out-of-range destination NodeID or a non-monotonic offsets array. It signals a caller contract violation at the FromArrays boundary, not a runtime fault.
Functions ¶
func OrderRuns ¶ added in v0.11.0
OrderRuns stably orders every source's neighbour run of a CSR in place, by the total key (destination, handle), permuting the parallel weights and handles columns under the SAME permutation. vertices is the length V+1 offsets array; edges is the flat neighbour array; weights and handles are the parallel columns and may each be nil.
It is exported because a caller that assembles CSR arrays itself and hands them to FromArrays must apply the same ordering to obtain a snapshot that carries this package's ordering invariant — store/bulk's counting-sort build does exactly that, and its byte-identity contract with BuildFromAdjList depends on using this same function.
Complexity is O(V + Σ d log d), which for a property graph's degree distribution is dominated by the O(V + E) copy that produced the arrays. Allocation is at most one scratch buffer per column, sized to the LONGEST run and reused across every source; a CSR whose longest run is within [runOrderInsertionCutoff] allocates nothing at all.
Types ¶
type CSR ¶
type CSR[W any] struct { // contains filtered or unexported fields }
CSR is an immutable compressed-sparse-row adjacency snapshot.
CSR is safe for concurrent reads by any number of goroutines and requires no synchronisation: the backing arrays are not mutated after BuildFromAdjList returns.
func BuildFromAdjList ¶
func BuildFromAdjList[N comparable, W any](adj *adjlist.AdjList[N, W]) *CSR[W]
BuildFromAdjList constructs an immutable CSR snapshot of the adjacency stored in adj. The build is consistent against any single quiescent state of adj; callers responsible for ingestion typically invoke this once their writers have completed.
Complexity is O(V + E) work plus O(V + E) memory for the resulting arrays. The function performs no concurrent fan-out and never blocks the caller on adjacency mutations.
BuildFromAdjList is tombstone-agnostic: it faithfully reflects the raw adjacency it is given. When the source is an [lpg.Graph]'s adjacency that may hold nodes removed via RemoveNode (which tombstones the node but does not strip its incident edges), those nodes' arcs would survive into the snapshot as ghost edges. Callers building a search snapshot from such a graph must use BuildFromAdjListLive with the graph's live-node predicate (#1790).
Example ¶
ExampleBuildFromAdjList freezes a mutable adjacency list into an immutable CSR snapshot suitable for lock-free analytical reads, and reads back its order (node count) and size (edge count).
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
)
func main() {
g := adjlist.New[string, int](adjlist.Config{Directed: true})
_ = g.AddEdge("a", "b", 1)
_ = g.AddEdge("b", "c", 1)
snap := csr.BuildFromAdjList(g)
fmt.Println("order:", snap.Order())
fmt.Println("size:", snap.Size())
}
Output: order: 3 size: 2
func BuildFromAdjListAsOf ¶ added in v0.11.0
func BuildFromAdjListAsOf[N comparable, W any]( adj *adjlist.AdjList[N, W], live func(graph.NodeID) bool, startTS, txID uint64, ) *CSR[W]
BuildFromAdjListAsOf is BuildFromAdjListLive resolving every adjacency entry as it stood at startTS for a reader running as txID, rather than as it stands now.
Why a snapshot build has to exist ¶
A CSR is the topology its consumers expand over — nothing downstream of it re-checks an arc's visibility — so under MVCC it must describe the READER's instant. Building from the current adjacency instead lets a read observe an edge committed after its snapshot started, which is an isolation violation and not a stale-cache annoyance (rmp #2293).
It is also REPEATABLE, which the present-reading build is not ¶
The entry visible at a fixed startTS is immutable, and the reclamation horizon pins it for as long as the reader holds its slot, so pass one and pass two resolve the SAME entry for every node. A build that reads the current entry twice has no such guarantee: a writer landing between the passes makes pass two find arcs pass one did not count. That is why the present-reading path needs the surplus-arc stop below and this one does not.
live is applied exactly as BuildFromAdjListLive applies it, and callers pass a predicate resolved at the same instant.
Complexity is O(V + E), and on a graph with no live version the per-entry resolution is one atomic load plus one uncontended gate read — what the present-reading build already costs.
What selecting the instant costs ¶
Measured, benchstat n=6, Apple M4: the branch selecting the arm costs the isolated build 4.89% geomean against the pre-MVCC build. It does NOT reach query time — the 960k-edge cypher_scale Expand1Hop trio moves +0.62% geomean with every individual result statistically indistinguishable (p=0.55, 0.22, 0.84) — because the build is a small share of a query and the pair cache amortises it across queries. That is the documented price of closing the isolation violation above.
func BuildFromAdjListLive ¶ added in v0.6.0
func BuildFromAdjListLive[N comparable, W any](adj *adjlist.AdjList[N, W], live func(graph.NodeID) bool) *CSR[W]
BuildFromAdjListLive is BuildFromAdjList with an optional liveness filter: any arc whose source or destination fails live is omitted from the snapshot, so a CSR built from an [lpg.Graph] holding tombstoned-but-not-stripped nodes reflects exactly the live topology rather than ghost edges (#1790).
When live is nil the build is identical to BuildFromAdjList — the common, zero-overhead fast path. lpg callers pass [lpg.Graph.LiveNodeFilter], which returns nil when the graph carries no tombstones, so a tombstone-free graph never pays the per-arc predicate cost. Complexity is O(V + E) either way.
It reads the CURRENT entry of every node, so the caller must exclude writers for the duration — see BuildFromAdjListAsOf for the snapshot build, which needs no such exclusion.
func FromArrays ¶ added in v0.6.0
func FromArrays[W any](vertices []uint64, edges []graph.NodeID, weights []W, order, size uint64) *CSR[W]
FromArrays assembles a CSR directly from caller-supplied, already final-sized adjacency arrays, bypassing BuildFromAdjList and its source adjlist.AdjList. It is the building block for high-throughput loaders (see store/bulk) that compute the offsets, flat edge array, and parallel weights in a single counting-sort pass and would otherwise pay for an intermediate mutable adjacency list.
The arguments map one-to-one onto the fields BuildFromAdjList produces, and the caller is responsible for supplying values that are already consistent with that builder's output:
- vertices is the length V+1 offsets array; vertices[id] is the start of node id's out-neighbours and vertices[len-1] is the total edge count. For an empty graph it is exactly []uint64{0}.
- edges is the flat out-neighbour array, length vertices[len-1], grouped by source in ascending NodeID order. Within a source the order is the caller's: FromArrays does NOT order the runs, because it is the zero-copy path and carries no O(E) pass. A caller that needs the snapshot to satisfy this package's within-source ordering invariant — which every CSR from BuildFromAdjList, BuildFromAdjListLive and CSR.BuildReverse does satisfy, and which the query executor's O(log d) probes rely on — must call OrderRuns on its arrays first. store/bulk's counting-sort build does exactly that, and its byte-identity contract with BuildFromAdjList depends on it.
- weights is parallel to edges, or nil for an unweighted/weightless snapshot (rendered as the zero W by CSR.NeighboursByID).
- order is the number of distinct nodes; size is the number of edges (it must equal vertices[len-1]).
FromArrays does not copy: it retains the supplied slices, which must therefore be treated as immutable from the call onward, exactly like a CSR returned by BuildFromAdjList. The handle column is always nil; loaders that need stable per-slot edge handles must use the adjacency path. The function performs no validation beyond what the type system enforces — it is the zero-copy bulk-load fast path and intentionally carries no O(E) scan. Supplying inconsistent arrays yields a malformed snapshot whose later traversal panics with a raw out-of-range index. A caller that does not fully trust its inputs should call CSR.Validate once after construction to obtain a typed ErrMalformedCSR at the boundary instead.
func (*CSR[W]) BuildReverse ¶
BuildReverse returns a fresh CSR representing the same vertex set as c but with every edge (u, v) replaced by its reverse (v, u). Weights are carried over unchanged.
The reverse CSR is the canonical adjacency for in-edge enumeration: it pairs with the forward CSR to support algorithms that require both directions (bidirectional Dijkstra, weakly-connected components, semi-external in-degree queries). On an undirected graph (one whose CSR is already symmetric) the returned CSR is structurally identical to c.
Complexity: O(V + E) time, O(V + E) memory. The returned CSR is independent of c; mutating its slices does not affect c (per the immutable-snapshot contract callers must in any case respect).
func (*CSR[W]) EdgesSlice ¶
EdgesSlice returns the underlying edges array. The slice must be treated as immutable; callers that mutate it break the snapshot's contract and any concurrent readers.
func (*CSR[W]) HandlesSlice ¶
HandlesSlice returns the underlying stable-edge-handle array, or nil when the source graph carried no per-slot handles (a simple graph that never used adjlist.AdjList.AddEdgeH). When non-nil the slice is the same length as CSR.EdgesSlice and aligns slot-for-slot with it: handles[pos] is the stable handle of the edge stored at edges[pos]. The slice must be treated as immutable.
A nil return is the read path's signal to fall back to its prior positional per-instance inference, so callers must nil-check before indexing.
func (*CSR[W]) IsSymmetric ¶
IsSymmetric reports whether the CSR is symmetric — that is, whether every directed edge (u, v) has a matching reverse edge (v, u). A symmetric CSR is the canonical representation of an undirected graph built via adjlist.AdjList with Directed: false.
Algorithms that conceptually operate on undirected graphs ([BiBFS], connected components, undirected Eulerian circuits) use this check to reject directed input early with a typed error rather than returning silently-wrong results.
Complexity: O(V + E) time, O(E) space (hash set of edge pairs).
func (*CSR[W]) LiveCount ¶
LiveCount returns the number of NodeIDs with at least one incident edge. Equivalent to len(c.LiveNodes()) but cheaper when the caller only needs the cardinality.
Complexity: O(V + E).
Example ¶
ExampleCSR_LiveCount counts the nodes that participate in the snapshot — those with at least one incident edge. LiveCount and the length of LiveNodes always agree, and LiveMask is the underlying per-NodeID boolean view they are both derived from.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
)
func main() {
g := adjlist.New[string, int](adjlist.Config{Directed: true})
_ = g.AddEdge("a", "b", 1)
_ = g.AddEdge("b", "c", 1)
snap := csr.BuildFromAdjList(g)
fmt.Println("live count:", snap.LiveCount())
fmt.Println("live nodes len:", len(snap.LiveNodes()))
fmt.Println("count == len(nodes):", snap.LiveCount() == len(snap.LiveNodes()))
// LiveMask reports liveness per NodeID; the number of true entries
// equals LiveCount.
var liveInMask int
for _, live := range snap.LiveMask() {
if live {
liveInMask++
}
}
fmt.Println("count == mask trues:", snap.LiveCount() == liveInMask)
}
Output: live count: 3 live nodes len: 3 count == len(nodes): true count == mask trues: true
func (*CSR[W]) LiveMask ¶
LiveMask returns a NodeID-indexed bitmap of length MaxNodeID() where mask[i] is true iff NodeID i participates in at least one edge as source or destination.
On graphs constructed via a sharded Mapper, the NodeID space is sparse: MaxNodeID() rounds up to multiples driven by the shard count, so many indices are ghost slots with no incident edge. Algorithms that iterate the full [0, MaxNodeID()) range and treat every slot as a real vertex must filter through LiveMask to avoid O(MaxNodeID()) blow-up on small graphs.
Complexity: O(V + E). The returned slice is freshly allocated; the CSR's own state is not retained or cached.
func (*CSR[W]) LiveNodes ¶
LiveNodes returns the sorted slice of NodeIDs with at least one incident edge. The companion to CSR.LiveMask when callers need a compact enumeration rather than a bitmap.
Complexity: O(V + E). The returned slice is freshly allocated.
func (*CSR[W]) MaxNodeID ¶
MaxNodeID returns the smallest NodeID strictly greater than every NodeID used as a source in the snapshot. The vertices offsets array has length MaxNodeID()+1.
func (*CSR[W]) NeighbourRange ¶ added in v0.11.0
NeighbourRange returns the half-open slot window holding src's neighbours, and whether src is present in this CSR's vertex space.
A cached CSR pair can legitimately be NARROWER than the live node space — a bare node CREATE does not change edge topology and so does not invalidate it — so callers must not index the offsets array unguarded. This accessor is that guard. A node with no edges correctly yields an empty range.
func (*CSR[W]) NeighboursByID ¶
NeighboursByID returns an iterator over the out-neighbours of src and the weight (if any) of each connecting edge. The iterator is backed by a slice owned by the CSR.
Allocation contract: the returned iter.Seq2 is allocation-free when used as a direct range expression at the call site ("for x, y := range g.NeighboursByID(src) { }"); the Go compiler inlines the closure in that case. Storing the iterator in a variable or passing it across function boundaries triggers closure heap-escape and one allocation per call. Hot paths in search/ deliberately bypass this method and read VerticesSlice() / EdgesSlice() directly to keep the inner loop allocation-free regardless of compiler decisions.
If src is outside the snapshot's NodeID range the iterator yields no values. The zero value of W is yielded for unweighted snapshots.
func (*CSR[W]) RunsOrdered ¶ added in v0.11.0
RunsOrdered reports whether every source's neighbour run is ordered by the total key (destination, handle). It is a VERIFICATION helper for tests and diagnostics, not a hot-path predicate: probes rely on the invariant rather than re-checking it.
Complexity is O(V + E). It does not allocate and never panics; a malformed offsets array yields false rather than an index panic.
func (*CSR[W]) Validate ¶ added in v0.6.0
Validate checks that the snapshot's backing arrays are internally consistent and returns a wrapped ErrMalformedCSR describing the first violation, or nil when the snapshot is well-formed. It is the opt-in boundary check for callers of FromArrays that pass untrusted arrays; snapshots produced by BuildFromAdjList / [BuildReverse] are always well-formed and need not be validated.
Validate deliberately does NOT check the within-source ordering invariant. FromArrays legitimately admits unordered runs (see its contract), so a failure here would reject well-formed input; and the invariant is a property of a run's order rather than of the arrays' structural consistency, which is what "malformed" means. Use CSR.RunsOrdered to assert ordering.
Validate is O(order + size). It does not allocate and never panics.
func (*CSR[W]) VerticesSlice ¶
VerticesSlice returns the underlying offsets array. The slice must be treated as immutable.
func (*CSR[W]) WeightsSlice ¶
func (c *CSR[W]) WeightsSlice() []W
WeightsSlice returns the underlying weights array, or nil if the snapshot is unweighted. The slice must be treated as immutable.
type Intersector ¶ added in v0.11.0
type Intersector struct {
// contains filtered or unexported fields
}
Intersector yields the destinations present in every one of its ranges, in ascending order, each exactly once.
Not safe for concurrent use. Reuse it across intersections to stay allocation-free; Init resets all state.
func (*Intersector) Init ¶ added in v0.11.0
func (it *Intersector) Init(ranges []Range) bool
Init prepares it to intersect ranges and reports whether a non-empty result is still possible. It allocates nothing.
It returns false — and leaves the Intersector exhausted — when there are no ranges, when more than MaxIntersectWays are supplied, or when ANY range is empty. The empty case is not an error: the intersection is provably empty, and short-circuiting it is exactly the "a cycle where one leg is empty" case the SPIKE identified as strictly cheaper than the plan it replaces, which would still scan the other leg in full.
A single range is accepted and yields that range's distinct destinations.
type Range ¶ added in v0.11.0
Range is a half-open [Start, End) window into one source's neighbour slots.
Edges must be ascending by destination over that window, which every CSR built by this package guarantees in BOTH directions: BuildFromAdjList and BuildFromAdjListLive call OrderRuns explicitly, and BuildReverse's runs come out ordered by construction — an invariant pinned by TestBuildReverse_RunsAreNeighbourAndHandleOrdered_2151 precisely because a binary search over an unordered run returns wrong rows rather than failing.
Source Files