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).
• Directed graphs. Digraph/DigraphBuilder mirror the undirected pair, with the CSR stored in both directions: OutNeighbors(u) and InNeighbors(u) are equally cheap, which is what reverse-flow algorithms like PageRank and "who links here" queries need. Built for mapping dependency graphs at ecosystem scale (millions of nodes).
• 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/Digraph (CSR), Builder/DigraphBuilder, 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, PageRank, WeaklyConnectedComponents

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 focused on undirected, unweighted graphs; v1.1 adds directed graphs (Digraph), PageRank, and WeaklyConnectedComponents, extracted from real usage mapping large dependency graphs. Weighted graphs, generic node labels, serialization, and further algorithms (strongly connected components, more centralities, community detection) remain 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. Digraph and DigraphBuilder are the directed counterparts; a Digraph stores both edge directions in CSR form, so out-neighbors and in-neighbors are equally cheap to walk.

Node IDs are dense integers in the range [0, N). Graphs are unweighted and always simple (no self-loops or duplicate edges). All randomized operations take an explicit *math/rand/v2.Rand so results are fully reproducible; the package never touches a global RNG.

Example

package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	// Assemble a topology with Builder, then freeze it into an immutable CSR
	// Graph for reading.
	b := gonx.NewBuilder(4)
	b.AddEdge(0, 1)
	b.AddEdge(0, 2)
	b.AddEdge(2, 3)
	g := b.Build()

	fmt.Println(g.NumNodes(), g.NumEdges())
	fmt.Println(g.Neighbors(0))
	fmt.Println(g.HasEdge(1, 2))
}

Output:
4 3
[1 2]
false

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 Digraph
  • func (g *Digraph) Degree(u int) int
  • func (g *Digraph) Edges() iter.Seq2[int, int]
  • func (g *Digraph) HasEdge(u, v int) bool
  • func (g *Digraph) InDegree(u int) int
  • func (g *Digraph) InNeighbors(u int) []int32
  • func (g *Digraph) InNeighborsSeq(u int) iter.Seq[int]
  • func (g *Digraph) Nodes() iter.Seq[int]
  • func (g *Digraph) NumEdges() int
  • func (g *Digraph) NumNodes() int
  • func (g *Digraph) OutDegree(u int) int
  • func (g *Digraph) OutNeighbors(u int) []int32
  • func (g *Digraph) OutNeighborsSeq(u int) iter.Seq[int]
  • func (g *Digraph) RandomInNeighbor(u int, r *rand.Rand) (v int, ok bool)
  • func (g *Digraph) RandomOutNeighbor(u int, r *rand.Rand) (v int, ok bool)
  • func (g *Digraph) ToBuilder() *DigraphBuilder
• type DigraphBuilder
  • func NewDigraphBuilder(n int) *DigraphBuilder
  • func (b *DigraphBuilder) AddEdge(u, v int) bool
  • func (b *DigraphBuilder) AddEdgeUnchecked(u, v int) bool
  • func (b *DigraphBuilder) AddNode() int
  • func (b *DigraphBuilder) Build() *Digraph
  • func (b *DigraphBuilder) HasEdge(u, v int) bool
  • func (b *DigraphBuilder) InDegree(u int) int
  • func (b *DigraphBuilder) NumEdges() int
  • func (b *DigraphBuilder) NumNodes() int
  • func (b *DigraphBuilder) OutDegree(u int) int
  • func (b *DigraphBuilder) 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

Examples

• Package
• Digraph
• Digraph.OutNeighborsSeq
• Graph.Edges
• Graph.NeighborsSeq

Variables

var (
	// ErrInvalidParam indicates a generator, transform, or metric was given
	// parameters it cannot work with (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 Digraph

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

Digraph is an immutable, directed, unweighted graph stored in Compressed Sparse Row form, twice: the out-neighbors of node u occupy outData[outOffsets[u]:outOffsets[u+1]] and its in-neighbors mirror that in a second CSR, both sorted ascending. Storing both directions costs 2x the edge memory and buys O(1) access from either end, which is what reverse-flow algorithms (PageRank pulls rank from in-neighbors) and "who links here" queries need. A Digraph is safe for concurrent reads.

In networkx terms, OutNeighbors are a node's successors and InNeighbors its predecessors.

Accessors that take a node ID panic with a descriptive message when the ID is outside [0, N); HasEdge is the exception and reports false for out-of-range endpoints. The zero value is not a valid Digraph; obtain one from DigraphBuilder.Build.

Example

package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	// A tiny citation graph: later papers cite earlier ones. Direction
	// matters, and a Digraph keeps both adjacency directions, so asking
	// "whom does 3 cite?" and "who cites 0?" are equally cheap.
	b := gonx.NewDigraphBuilder(4)
	b.AddEdge(1, 0)
	b.AddEdge(2, 0)
	b.AddEdge(3, 0)
	b.AddEdge(3, 2)
	g := b.Build()

	fmt.Println(g.OutNeighbors(3)) // what 3 cites
	fmt.Println(g.InNeighbors(0))  // who cites 0
	fmt.Println(g.HasEdge(3, 2), g.HasEdge(2, 3))
}

Output:
[0 2]
[1 2 3]
true false

func (*Digraph) Degree

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

Degree returns InDegree(u) + OutDegree(u), matching networkx's DiGraph.degree. It panics if u is out of range.

func (*Digraph) Edges

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

Edges iterates over each directed edge exactly once as (u, v), ordered by source and then by target.

func (*Digraph) HasEdge

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

HasEdge reports whether the directed edge u->v exists. It binary-searches the shorter of u's out-list and v's in-list, so it runs in O(log deg).

func (*Digraph) InDegree

func (g *Digraph) InDegree(u int) int

InDegree returns the number of incoming edges of u. It panics if u is out of range.

func (*Digraph) InNeighbors

func (g *Digraph) InNeighbors(u int) []int32

InNeighbors returns the sources of u's incoming edges 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 (*Digraph) InNeighborsSeq

func (g *Digraph) InNeighborsSeq(u int) iter.Seq[int]

InNeighborsSeq iterates over the sources of u's incoming edges in ascending order as ints. Hot paths should prefer Digraph.InNeighbors, which exposes the backing slice with no per-element call overhead. It panics if u is out of range.

func (*Digraph) Nodes

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

Nodes iterates over all node IDs in ascending order.

func (*Digraph) NumEdges

func (g *Digraph) NumEdges() int

NumEdges reports the number of directed edges.

func (*Digraph) NumNodes

func (g *Digraph) NumNodes() int

NumNodes reports the number of nodes.

func (*Digraph) OutDegree

func (g *Digraph) OutDegree(u int) int

OutDegree returns the number of outgoing edges of u. It panics if u is out of range.

func (*Digraph) OutNeighbors

func (g *Digraph) OutNeighbors(u int) []int32

OutNeighbors returns the targets of u's outgoing edges 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 (*Digraph) OutNeighborsSeq

func (g *Digraph) OutNeighborsSeq(u int) iter.Seq[int]

OutNeighborsSeq iterates over the targets of u's outgoing edges in ascending order as ints. Hot paths should prefer Digraph.OutNeighbors, which exposes the backing slice with no per-element call overhead. It panics if u is out of range.

Example

package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	b := gonx.NewDigraphBuilder(4)
	b.AddEdge(0, 3)
	b.AddEdge(0, 1)
	sum := 0
	g := b.Build()
	for v := range g.OutNeighborsSeq(0) {
		sum += v
	}
	fmt.Println(sum)
}

Output:
4

func (*Digraph) RandomInNeighbor

func (g *Digraph) RandomInNeighbor(u int, r *rand.Rand) (v int, ok bool)

RandomInNeighbor returns a uniformly random source of u's incoming edges. ok is false when u has none. It panics if u is out of range.

func (*Digraph) RandomOutNeighbor

func (g *Digraph) RandomOutNeighbor(u int, r *rand.Rand) (v int, ok bool)

RandomOutNeighbor returns a uniformly random target of u's outgoing edges. ok is false when u has none. It panics if u is out of range.

func (*Digraph) ToBuilder

func (g *Digraph) ToBuilder() *DigraphBuilder

ToBuilder returns a mutable copy of the graph.

type DigraphBuilder

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

DigraphBuilder is a mutable directed graph used to assemble a topology before freezing it into an immutable Digraph. It is not safe for concurrent use.

Like Builder, it keeps the graph simple: self-loops and duplicate edges are rejected. The directed edge u->v and its reverse v->u are distinct edges and may coexist.

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

func NewDigraphBuilder

func NewDigraphBuilder(n int) *DigraphBuilder

NewDigraphBuilder returns a DigraphBuilder 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 (*DigraphBuilder) AddEdge

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

AddEdge inserts the directed 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. Inserting v->u afterwards is a distinct edge and succeeds.

func (*DigraphBuilder) AddEdgeUnchecked

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

AddEdgeUnchecked inserts the directed 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 ordered pair is known to be produced at most once, where skipping the duplicate scan turns dense O(n*m) builds into O(m).

func (*DigraphBuilder) AddNode

func (b *DigraphBuilder) AddNode() int

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

func (*DigraphBuilder) Build

func (b *DigraphBuilder) Build() *Digraph

Build freezes the Builder into an immutable CSR Digraph, materializing both adjacency directions: the out-lists directly, the in-lists by a counting pass over them. Both are sorted, so the resulting Digraph supports binary-search edge tests and has a canonical, deterministic layout. The Builder may be reused afterwards.

Build panics if the edge count exceeds 2^31-1, the capacity of the int32 CSR offsets.

func (*DigraphBuilder) HasEdge

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

HasEdge reports whether the directed edge u->v exists. O(outdeg(u)).

func (*DigraphBuilder) InDegree

func (b *DigraphBuilder) InDegree(u int) int

InDegree returns the number of incoming edges of u. It panics if u is out of range.

func (*DigraphBuilder) NumEdges

func (b *DigraphBuilder) NumEdges() int

NumEdges reports the number of directed edges.

func (*DigraphBuilder) NumNodes

func (b *DigraphBuilder) NumNodes() int

NumNodes reports the number of nodes.

func (*DigraphBuilder) OutDegree

func (b *DigraphBuilder) OutDegree(u int) int

OutDegree returns the number of outgoing edges of u. It panics if u is out of range.

func (*DigraphBuilder) RemoveEdge

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

RemoveEdge deletes the directed edge u->v, returning whether it existed. The reverse edge v->u, if present, is unaffected.

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. The zero value is not a valid Graph; obtain one from Builder.Build.

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.

Example

package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	b := gonx.NewBuilder(3)
	b.AddEdge(0, 1)
	b.AddEdge(1, 2)
	g := b.Build()
	for u, v := range g.Edges() {
		fmt.Println(u, v)
	}
}

Output:
0 1
1 2

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.

Example

package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	b := gonx.NewBuilder(3)
	b.AddEdge(0, 2)
	b.AddEdge(0, 1)
	g := b.Build()
	for v := range g.NeighborsSeq(0) {
		fmt.Println(v)
	}
}

Output:
1
2

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.