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 ¶
- 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]) VerticesSlice() []uint64
- func (c *CSR[W]) WeightsSlice() []W
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
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.
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 (*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]) 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