gonx

README

gonx

A performance-oriented graph library for Go, in the spirit of Python's networkx but built around dense integer node IDs and a compact, cache-friendly representation.

gonx targets workloads that build a graph once and then read it intensively — agent-based simulations, network metrics, repeated traversals. It separates mutation from reading: a Builder assembles the topology, then freezes into an immutable Graph stored in Compressed Sparse Row form for zero-copy, O(1) neighbor iteration.

import (
    "github.com/LuisLSousa/gonx"
    "github.com/LuisLSousa/gonx/generators"
    "github.com/LuisLSousa/gonx/metrics"
)

r := gonx.NewRand(42)                                  // reproducible PCG RNG
g, _ := generators.WattsStrogatz(1000, 8, 0.1, r)      // small-world graph

apl, _ := metrics.AveragePathLength(g)                 // parallel all-pairs BFS
cc := metrics.Transitivity(g)                          // global clustering

for u := range g.Nodes() {
    for _, v := range g.Neighbors(u) {                 // zero-alloc, cache-friendly
        _ = v
    }
}

Gallery

Every image below is produced by a runnable example in examples/: gonx builds the graph, and a small dependency-free helper (examples/internal/render) does the force-directed layout and writes the SVG. Regenerate any of them from the repo root, e.g. go run ./examples/scalefree.

Scale-free network — Barabási–Albert preferential attachment; nodes sized and colored by degree, so the hubs glow.

r := gonx.NewRand(7)
g, _ := generators.BarabasiAlbert(150, 2, r) // 150 nodes, 2 edges per arrival

Small-world network — Watts–Strogatz ring lattice with 12% of edges rewired; the long-range shortcuts that collapse path lengths are drawn in cyan.

r := gonx.NewRand(11)
g, _ := generators.WattsStrogatz(48, 4, 0.12, r) // k=4 ring, p=0.12 rewiring

Community structure — a planted partition assembled with Builder: four dense blocks with sparse bridges between them, colored by block.

b := gonx.NewBuilder(88) // 4 blocks of 22 nodes
for u := 0; u < 88; u++ {
    for v := u + 1; v < 88; v++ {
        p := 0.005                       // sparse between blocks...
        if u/22 == v/22 { p = 0.28 }     // ...dense inside them
        if r.Float64() < p { b.AddEdge(u, v) }
    }
}
g := b.Build()

Zachary's Karate Club — the classic 34-member social network, colored by the faction each member joined after the club split (indigo: Mr. Hi, node 0; amber: the Officer, node 33) and sized by degree.

b := gonx.NewBuilder(34)
for _, e := range zacharyEdges { // the standard 78-edge list
    b.AddEdge(e[0], e[1])
}
g := b.Build()

Design

• Dense integer nodes. IDs are 0..N-1 (up to 2³¹−1 nodes and adjacency entries — enforced, not silently overflowed). No generic node types in the core — that would reintroduce a map indirection and defeat CSR's locality. A labeled wrapper can sit on top if needed.
• Immutable Graph (CSR). Neighbors of u live in a contiguous, sorted slice returned zero-copy by Neighbors(u); NeighborsSeq(u) wraps the same data as an iter.Seq[int] for callers who prefer plain ints. HasEdge is O(log deg) via binary search.
• Mutable Builder. Add/remove nodes and edges, then Build() to freeze. The result is always simple (no self-loops or duplicate edges).
• Reproducible randomness. Every randomized operation takes an explicit *math/rand/v2.Rand. Same seed + parameters ⇒ byte-identical graph. The package never touches a global RNG.
• Parallel where it pays. All-pairs shortest paths and triangle counting are parallelized over independent source nodes with order-independent reductions, so results are deterministic regardless of GOMAXPROCS. Generators and edge swaps are inherently sequential and kept single-threaded.

Packages

Package	Contents
gonx	Graph (CSR), Builder, iterators, NewRand
gonx/generators	WattsStrogatz, BarabasiAlbert, Complete, RandomAvgDegree, ErdosRenyi
gonx/transform	DoubleEdgeSwap, RelabelNodes, Shuffle, Copy
gonx/metrics	Transitivity, AverageClustering, AveragePathLength(+LCC), Diameter, ConnectedComponents, IsConnected, BFS

Note on BarabasiAlbert(n, m, r): m is the number of edges added per new node (matching networkx), not the average degree — the resulting average degree is approximately 2m.

Status

v1 focuses on undirected, unweighted graphs. Directed/weighted graphs, generic node labels, serialization, and advanced algorithms (centralities, community detection) are intentionally out of scope for now.

Testing

go test ./... -race        # unit, property, determinism, known-value tests
go test -bench . -benchmem  # benchmarks
go test -fuzz FuzzDoubleEdgeSwap ./transform   # degree-preservation fuzzing

License

MIT — see LICENSE.

Documentation

Overview

Package gonx is a performance-oriented graph library for Go, in the spirit of Python's networkx but built around dense integer node IDs and a compact, cache-friendly representation.

The library separates mutation from reading. A Builder accumulates nodes and edges, and Builder.Build freezes it into an immutable Graph stored in Compressed Sparse Row (CSR) form. The CSR layout gives zero-copy, O(1) neighbor iteration, which is the dominant access pattern for the simulations and graph metrics this library targets.

Node IDs are dense integers in the range [0, N). Graphs are undirected and unweighted. All randomized operations take an explicit *math/rand/v2.Rand so results are fully reproducible; the package never touches a global RNG.

Index

• Variables
• func NewRand(seed uint64) *rand.Rand
• type Builder
  • func NewBuilder(n int) *Builder
  • func (b *Builder) AddEdge(u, v int) bool
  • func (b *Builder) AddEdgeUnchecked(u, v int) bool
  • func (b *Builder) AddNode() int
  • func (b *Builder) Build() *Graph
  • func (b *Builder) Degree(u int) int
  • func (b *Builder) HasEdge(u, v int) bool
  • func (b *Builder) NumEdges() int
  • func (b *Builder) NumNodes() int
  • func (b *Builder) RemoveEdge(u, v int) bool
• type Graph
  • func (g *Graph) Degree(u int) int
  • func (g *Graph) Edges() iter.Seq2[int, int]
  • func (g *Graph) HasEdge(u, v int) bool
  • func (g *Graph) Neighbors(u int) []int32
  • func (g *Graph) NeighborsSeq(u int) iter.Seq[int]
  • func (g *Graph) Nodes() iter.Seq[int]
  • func (g *Graph) NumEdges() int
  • func (g *Graph) NumNodes() int
  • func (g *Graph) RandomNeighbor(u int, r *rand.Rand) (v int, ok bool)
  • func (g *Graph) ToBuilder() *Builder

Variables

var (
	// ErrInvalidParam indicates a generator or transform was given parameters
	// that cannot produce a valid graph (e.g. odd degree for Watts-Strogatz).
	ErrInvalidParam = errors.New("gonx: invalid parameter")
	// ErrNotPermutation indicates a relabeling slice is not a permutation of [0, N).
	ErrNotPermutation = errors.New("gonx: not a permutation of node ids")
)

Sentinel errors returned by constructors and algorithms. Wrap-friendly: callers may test with errors.Is.

Functions

func NewRand

func NewRand(seed uint64) *rand.Rand

NewRand returns a deterministic PCG-based RNG seeded from a single value. Identical seeds yield identical streams across runs and platforms, which is the basis for reproducible graph generation.

Types

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder is a mutable undirected graph used to assemble a topology before freezing it into an immutable Graph. It is not safe for concurrent use.

Edge methods (AddEdge, RemoveEdge, HasEdge) treat out-of-range endpoints as absent edges and report false; Degree panics on an out-of-range node.

func NewBuilder

func NewBuilder(n int) *Builder

NewBuilder returns a Builder with n isolated nodes (IDs 0..n-1). It panics if n exceeds 2^31-1, the maximum node count supported by the int32 CSR layout.

func (*Builder) AddEdge

func (b *Builder) AddEdge(u, v int) bool

AddEdge inserts the undirected edge {u, v}. It returns false (and does nothing) for self-loops, out-of-range endpoints, or edges that already exist, so the resulting graph is always simple.

func (*Builder) AddEdgeUnchecked

func (b *Builder) AddEdgeUnchecked(u, v int) bool

AddEdgeUnchecked inserts the undirected edge {u, v} without checking whether it already exists. Endpoints are still validated and self-loops rejected (returning false), but inserting an edge that is already present corrupts the Builder: the graph silently becomes a multigraph with a double-counted NumEdges. Use it only when each pair is known to be produced at most once — e.g. generators that enumerate pairs with u < v — where skipping the duplicate scan turns dense O(n*m) builds into O(m).

func (*Builder) AddNode

func (b *Builder) AddNode() int

AddNode appends a new isolated node and returns its ID. It panics if the node count would exceed 2^31-1.

func (*Builder) Build

func (b *Builder) Build() *Graph

Build freezes the Builder into an immutable CSR Graph. Neighbor lists are sorted so the resulting Graph supports binary-search edge tests and has a canonical, deterministic layout. The Builder may be reused afterwards.

Build panics if the total adjacency size (2 * edges) exceeds 2^31-1, the capacity of the int32 CSR offsets.

func (*Builder) Degree

func (b *Builder) Degree(u int) int

Degree returns the number of neighbors of u. It panics if u is out of range.

func (*Builder) HasEdge

func (b *Builder) HasEdge(u, v int) bool

HasEdge reports whether the undirected edge {u, v} exists. O(deg(u)).

func (*Builder) NumEdges

func (b *Builder) NumEdges() int

NumEdges reports the number of undirected edges.

func (*Builder) NumNodes

func (b *Builder) NumNodes() int

NumNodes reports the number of nodes.

func (*Builder) RemoveEdge

func (b *Builder) RemoveEdge(u, v int) bool

RemoveEdge deletes the undirected edge {u, v}, returning whether it existed.

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph is an immutable, undirected, unweighted graph stored in Compressed Sparse Row form. The neighbors of node u occupy data[offsets[u]:offsets[u+1]] and are sorted ascending. A Graph is safe for concurrent reads.

Accessors that take a node ID (Degree, Neighbors, NeighborsSeq, RandomNeighbor) panic with a descriptive message when the ID is outside [0, N); HasEdge is the exception and reports false for out-of-range endpoints.

func (*Graph) Degree

func (g *Graph) Degree(u int) int

Degree returns the number of neighbors of u. It panics if u is out of range.

func (*Graph) Edges

func (g *Graph) Edges() iter.Seq2[int, int]

Edges iterates over each undirected edge exactly once as (u, v) with u < v.

func (*Graph) HasEdge

func (g *Graph) HasEdge(u, v int) bool

HasEdge reports whether the undirected edge {u, v} exists. It uses binary search over the smaller-degree endpoint, so it runs in O(log deg).

func (*Graph) Neighbors

func (g *Graph) Neighbors(u int) []int32

Neighbors returns u's neighbor IDs as a sorted, zero-copy slice into the graph's backing storage. Callers MUST NOT modify the returned slice. It panics if u is out of range.

func (*Graph) NeighborsSeq

func (g *Graph) NeighborsSeq(u int) iter.Seq[int]

NeighborsSeq iterates over u's neighbors in ascending order as ints. It is a convenience wrapper over Graph.Neighbors for callers who want int node IDs end-to-end; hot paths should prefer Neighbors, which exposes the backing slice with no per-element call overhead. It panics if u is out of range.

func (*Graph) Nodes

func (g *Graph) Nodes() iter.Seq[int]

Nodes iterates over all node IDs in ascending order.

func (*Graph) NumEdges

func (g *Graph) NumEdges() int

NumEdges reports the number of undirected edges.

func (*Graph) NumNodes

func (g *Graph) NumNodes() int

NumNodes reports the number of nodes.

func (*Graph) RandomNeighbor

func (g *Graph) RandomNeighbor(u int, r *rand.Rand) (v int, ok bool)

RandomNeighbor returns a uniformly random neighbor of u. ok is false when u is isolated. It panics if u is out of range.

func (*Graph) ToBuilder

func (g *Graph) ToBuilder() *Builder

ToBuilder returns a mutable copy of the graph.