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 ¶
- Variables
- type CSR
- 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]) NeighboursByID(src graph.NodeID) iter.Seq2[graph.NodeID, W]
- func (c *CSR[W]) Order() uint64
- func (c *CSR[W]) Size() uint64
- func (c *CSR[W]) Validate() error
- func (c *CSR[W]) VerticesSlice() []uint64
- func (c *CSR[W]) WeightsSlice() []W
Examples ¶
Constants ¶
This section is empty.
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 ¶
This section is empty.
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 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.
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 (the bulk loader preserves input order).
- 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]) 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]) 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 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.
Source Files