gonx

package module
v1.3.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 2, 2026 License: MIT Imports: 6 Imported by: 1

README

gonx

CI

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, such as agent-based simulations, network metrics, and repeated traversals. It separates mutation from reading: a Builder assembles the topology, then freezes into an immutable Graph stored in Compressed Sparse Row form with zero-copy, O(1) access to sorted neighbor slices.

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
    }
}

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

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

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

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

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).
  • Optional edge weights. AddEdgeW puts a float64 on an edge, or NewWeightedBuilder makes every edge weighted from the start. Weights are stored in an array laid out exactly like the adjacency, so Weights(u)[i] belongs to Neighbors(u)[i], and an unweighted graph stores no weight array. EdgeOffset and EdgeIndex expose that layout, so per-edge data of your own can live in a plain slice indexed the same way.
  • 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 The Shape of Go, which maps all 2.6 million public Go modules and their 9.4 million dependency edges.
  • One traversal interface. Adjacency is the read-only view Graph and Digraph share: node count, out-neighbors, out-weights. An algorithm that only walks edges forward takes an Adjacency and runs on either kind from one implementation. It is sealed to this package for now.
  • Views with parts hidden. RestrictedView(g, nodes, edges), after networkx's restricted_view, hides nodes and edges without copying the graph, and is an Adjacency itself, so "the shortest path if this edge were gone" is ShortestPath on a view. Only the lists that lose an entry are copied; every other node reads the graph's own slices.
  • Reproducible randomness. Every randomized operation takes an explicit *math/rand/v2.Rand. The same seed and parameters give a 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, optional edge weights), Builder/DigraphBuilder (+ NewWeighted*), Adjacency, RestrictedView, 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/BreadthFirst, Dijkstra, ShortestPath, PathFinder, Bridges, ArticulationPoints, 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.

Benchmarks

Measured against networkx, python-igraph, and gonum/graph on identical seeded inputs, with cross-library answer checks; the full harness, protocol, and caveats live in bench/ and every number below reproduces with cd bench && ./run.sh.

Benchmark receipts

Medians of 3 runs on a Barabási–Albert graph with 1M nodes / 5.0M directed edges (Apple M3 Max; ratio vs gonx in parentheses):

operation gonx networkx igraph gonum
build 65 ms 7.0 s (106×) 284 ms (4.3×) 2.9 s (45×)
PageRank 38 ms 3.1 s (82×) 164 ms (4.3×) 2.5 s (67×)
weak components 80 ms 2.0 s (25×) 229 ms (2.9×) 4.4 s (56×)
BFS reachability 33 ms 2.1 s (63×) 120 ms (3.6×) 1.8 s (55×)
Dijkstra (weighted) 272 ms 5.5 s (20×) 568 ms (2.1×) 3.4 s (12×)
peak memory 272 MB 3.1 GB 1.5 GB 2.5 GB
peak memory, Dijkstra run 440 MB 2.6 GB 1.0 GB 2.1 GB

igraph's C core comes closest, at 2.1 to 4.3 times gonx's time. networkx is the slowest on four of the five operations but implements far more algorithms. The first memory row covers the four unweighted operations; Dijkstra runs in a separate process on a weighted copy of the graph and has its own row. The table measures these five operations on this workload, nothing broader.

Status

v1 focused on undirected, unweighted graphs; v1.1 added directed graphs (Digraph), PageRank, and WeaklyConnectedComponents, extracted from real usage mapping the full Go module dependency graph (2.6M nodes, 9.4M edges). Both graph kinds now carry optional edge weights and share the Adjacency traversal interface, whose first consumers are BreadthFirst, Dijkstra and ShortestPath. Generic node labels, serialization, and community detection remain intentionally out of scope.

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 always simple (no self-loops or duplicate edges). Edges are unweighted unless the builder was given weights, through Builder.AddEdgeW or NewWeightedBuilder; a weighted graph stores one float64 per edge in an array laid out exactly like the adjacency, so the weight of Neighbors(u)[i] is Weights(u)[i], and an unweighted graph stores no weight array. Adjacency is the read-only view of each node's outgoing edges that Graph and Digraph share, for algorithms that only walk edges in their natural direction.

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

Examples

Constants

This section is empty.

Variables

View Source 
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 Adjacency added in v1.2.0 

type Adjacency interface {
	NumNodes() int
	OutNeighbors(u int) []int32
	OutWeights(u int) []float64
	Weighted() bool
	HasNegativeWeight() bool
	// contains filtered or unexported methods
}

Adjacency is the read-only view of a graph's outgoing edges that Graph and Digraph share, and that a Restricted view of either provides too: how many nodes there are and, for each node, the edges leaving it together with their weights when the graph has any. An algorithm that only ever walks edges in their natural direction takes an Adjacency and runs on either graph kind, or on a view with parts hidden, from a single implementation. On an undirected Graph the edges leaving u are its neighbors, since every edge can be walked from either end; on a Digraph only the out-side is part of the view, and the in-lists stay on the concrete type.

The contract, which every implementation honors and which algorithms rely on:

  • Node IDs are dense in [0, NumNodes).
  • OutNeighbors(u) lists the targets of u's outgoing edges in ascending order, without duplicates and without u itself.
  • Weighted is constant for the life of the graph. When it is true, OutWeights(u) has the same length as OutNeighbors(u) and OutWeights(u)[i] is the finite weight of the edge to OutNeighbors(u)[i]; when it is false, OutWeights returns nil and every edge counts as weight 1.
  • HasNegativeWeight is true if, and only if, some OutWeights entry is below zero, and like Weighted it costs O(1).
  • Returned slices are views into the graph's storage: read-only, with no spare capacity, and valid for as long as the graph is. They may be held across calls, and the graph may be read from several goroutines at once.

Adjacency is sealed: one of its methods is unexported, so only this package can define a full implementation, and the method set can grow with the algorithms that consume it. A later release may open it to other representations once that set has settled. A type that embeds one of this package's types, or an Adjacency, still satisfies the interface, and takes on the contract for every method it overrides; an override of OutWeights, for one, must keep HasNegativeWeight truthful, since Dijkstra relies on it to reject negative weights up front. RestrictedView, which builds on a graph's storage rather than its methods, accepts only this package's own types.

Example 
package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	// One function for both graph kinds: the total weight leaving each node.
	outWeight := func(g gonx.Adjacency) []float64 {
		out := make([]float64, g.NumNodes())
		for u := range out {
			if g.Weighted() {
				for _, w := range g.OutWeights(u) {
					out[u] += w
				}
			} else {
				out[u] = float64(len(g.OutNeighbors(u)))
			}
		}
		return out
	}

	ub := gonx.NewBuilder(3)
	ub.AddEdgeW(0, 1, 2)
	ub.AddEdgeW(1, 2, 3)
	db := gonx.NewDigraphBuilder(3)
	db.AddEdgeW(0, 1, 2)
	db.AddEdgeW(1, 2, 3)

	fmt.Println(outWeight(ub.Build())) // an undirected edge leaves both ends
	fmt.Println(outWeight(db.Build()))
}

Output:
[2 5 3]
[2 3 0]

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.

A Builder from NewBuilder starts unweighted, and the first successful Builder.AddEdgeW call switches it to weighted for good; one from NewWeightedBuilder is weighted from the start. See AddEdgeW for how edges without an explicit weight are treated.

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 NewWeightedBuilder added in v1.2.0 

func NewWeightedBuilder(n int) *Builder

NewWeightedBuilder returns a Builder with n isolated nodes that is weighted from the start: every edge it ever holds has a weight, 1 unless AddEdgeW gave it another, and the Graph it builds reports Weighted even with no edges. Use it when the graph is weighted by nature; a plain NewBuilder becomes weighted on its first successful AddEdgeW call instead. It panics if n exceeds 2^31-1.

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) AddEdgeW added in v1.2.0 

func (b *Builder) AddEdgeW(u, v int, w float64) bool

AddEdgeW inserts the undirected edge {u, v} with weight w. It rejects everything AddEdge rejects, plus NaN and infinite weights, returning false in each case. Any finite weight is accepted, zero and negative values included; algorithms that need non-negative weights say so and check for themselves.

The first successful AddEdgeW call makes a NewBuilder weighted. Every edge already present then has weight 1, and edges added afterwards with AddEdge or AddEdgeUnchecked get weight 1 too, so a weighted graph has a weight for every edge; 1 is also the default networkx algorithms use for a missing weight attribute. An existing edge is never re-weighted: AddEdgeW on it returns false like AddEdge does, and changing a weight means RemoveEdge followed by AddEdgeW.

Example 
package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	// A weighted triangle. Weights ride along with their edges through Build and
	// come back aligned with Neighbors.
	b := gonx.NewBuilder(3)
	b.AddEdgeW(0, 1, 2.5)
	b.AddEdgeW(1, 2, 0.5)
	b.AddEdge(0, 2) // an unweighted add on a weighted builder means weight 1
	g := b.Build()

	fmt.Println(g.Neighbors(1), g.Weights(1))
	fmt.Println(g.Weight(0, 2))
	fmt.Println(g.Weight(1, 1))
}

Output:
[0 2] [2.5 0.5]
1 true
0 false

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; on a weighted Builder each weight travels with its edge. 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(min(deg(u), deg(v))).

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.

func (*Builder) Weighted added in v1.2.0 

func (b *Builder) Weighted() bool

Weighted reports whether the Builder carries edge weights: always for a NewWeightedBuilder, and from the first successful Builder.AddEdgeW call on for a NewBuilder.

type Digraph added in v1.1.0 

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

Digraph is an immutable, directed 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. On a weighted Digraph each direction has a weight array with the same indices as its adjacency. 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, Weight, EdgeIndex and InEdgeIndex take an edge instead and report false for out-of-range endpoints. Slices returned by the accessors are views into the graph's storage with no spare capacity. 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 added in v1.1.0 

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) EdgeIndex added in v1.2.0 

func (g *Digraph) EdgeIndex(u, v int) (slot int, ok bool)

EdgeIndex returns the out slot of the edge u->v: OutEdgeOffset(u) plus the position of v in OutNeighbors(u). ok is false when the edge does not exist or an endpoint is out of range. It runs in O(log outdeg(u)).

func (*Digraph) Edges added in v1.1.0 

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 added in v1.1.0 

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) HasNegativeWeight added in v1.2.0 

func (g *Digraph) HasNegativeWeight() bool

HasNegativeWeight reports whether any edge weighs less than zero. It is always false on an unweighted graph. Build records the answer, so the call is O(1); algorithms that need non-negative weights check it once up front.

func (*Digraph) InDegree added in v1.1.0 

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) InEdgeIndex added in v1.2.0 

func (g *Digraph) InEdgeIndex(u, v int) (slot int, ok bool)

InEdgeIndex returns the in slot of the edge u->v: InEdgeOffset(v) plus the position of u in InNeighbors(v). ok is false when the edge does not exist or an endpoint is out of range. It runs in O(log indeg(v)).

func (*Digraph) InEdgeOffset added in v1.2.0 

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

InEdgeOffset is the in-edge counterpart of Digraph.OutEdgeOffset: entry i of InNeighbors(u) sits at position InEdgeOffset(u)+i in an array of length NumEdges indexed like the in-adjacency. The two indexings are unrelated; an edge's out slot and in slot differ. It panics if u is out of range.

func (*Digraph) InNeighbors added in v1.1.0 

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 added in v1.1.0 

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) InWeights added in v1.2.0 

func (g *Digraph) InWeights(u int) []float64

InWeights returns the weights of u's incoming edges, aligned index for index with Digraph.InNeighbors. The slice is zero-copy and MUST NOT be modified. It is nil when the graph is unweighted. It panics if u is out of range.

func (*Digraph) Nodes added in v1.1.0 

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

Nodes iterates over all node IDs in ascending order.

func (*Digraph) NumEdges added in v1.1.0 

func (g *Digraph) NumEdges() int

NumEdges reports the number of directed edges.

func (*Digraph) NumNodes added in v1.1.0 

func (g *Digraph) NumNodes() int

NumNodes reports the number of nodes.

func (*Digraph) OutDegree added in v1.1.0 

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) OutEdgeOffset added in v1.2.0 

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

OutEdgeOffset returns the index at which u's outgoing edges start in the graph's out-edge arrays: entry i of OutNeighbors(u), and of OutWeights(u), sits at position OutEdgeOffset(u)+i in an array of length NumEdges. See Graph.EdgeOffset for what this is for. It panics if u is out of range.

func (*Digraph) OutNeighbors added in v1.1.0 

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 added in v1.1.0 

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) OutWeights added in v1.2.0 

func (g *Digraph) OutWeights(u int) []float64

OutWeights returns the weights of u's outgoing edges, aligned index for index with Digraph.OutNeighbors. The slice is zero-copy and MUST NOT be modified. It is nil when the graph is unweighted. It panics if u is out of range.

func (*Digraph) RandomInNeighbor added in v1.1.0 

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 added in v1.1.0 

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 added in v1.1.0 

func (g *Digraph) ToBuilder() *DigraphBuilder

ToBuilder returns a mutable copy of the graph, weights included.

func (*Digraph) Weight added in v1.2.0 

func (g *Digraph) Weight(u, v int) (w float64, ok bool)

Weight returns the weight of the directed edge u->v. ok is false when the edge does not exist or an endpoint is out of range. On an unweighted graph every existing edge has weight 1. Like Digraph.HasEdge it binary-searches the shorter of u's out-list and v's in-list, so it runs in O(log deg).

func (*Digraph) Weighted added in v1.2.0 

func (g *Digraph) Weighted() bool

Weighted reports whether the graph carries edge weights. An unweighted Digraph stores no weight arrays: OutWeights and InWeights return nil for every node and Weight reports 1 for every edge.

type DigraphBuilder added in v1.1.0 

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.

A DigraphBuilder from NewDigraphBuilder starts unweighted, and the first successful DigraphBuilder.AddEdgeW call switches it to weighted for good; one from NewWeightedDigraphBuilder is weighted from the start. The rules are those of Builder.AddEdgeW.

func NewDigraphBuilder added in v1.1.0 

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 NewWeightedDigraphBuilder added in v1.2.0 

func NewWeightedDigraphBuilder(n int) *DigraphBuilder

NewWeightedDigraphBuilder returns a DigraphBuilder with n isolated nodes that is weighted from the start, the directed counterpart of NewWeightedBuilder. It panics if n exceeds 2^31-1.

func (*DigraphBuilder) AddEdge added in v1.1.0 

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. The duplicate check is DigraphBuilder.HasEdge, so adding many edges out of one node to targets that already have in-edges costs time quadratic in that node's out-degree; DigraphBuilder.AddEdgeUnchecked skips the check when the input is known to be simple.

func (*DigraphBuilder) AddEdgeUnchecked added in v1.1.0 

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) AddEdgeW added in v1.2.0 

func (b *DigraphBuilder) AddEdgeW(u, v int, w float64) bool

AddEdgeW inserts the directed edge u->v with weight w. It rejects everything AddEdge rejects, plus NaN and infinite weights, returning false in each case. The first successful call makes a NewDigraphBuilder weighted: edges already present then have weight 1, as do edges added later without an explicit weight, and an existing edge is never re-weighted. See Builder.AddEdgeW.

func (*DigraphBuilder) AddNode added in v1.1.0 

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 added in v1.1.0 

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. On a weighted Builder each weight travels with its edge into both directions. 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 added in v1.1.0 

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

HasEdge reports whether the directed edge u->v exists: O(1) when v has no in-edges, and otherwise O(outdeg(u)).

func (*DigraphBuilder) InDegree added in v1.1.0 

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 added in v1.1.0 

func (b *DigraphBuilder) NumEdges() int

NumEdges reports the number of directed edges.

func (*DigraphBuilder) NumNodes added in v1.1.0 

func (b *DigraphBuilder) NumNodes() int

NumNodes reports the number of nodes.

func (*DigraphBuilder) OutDegree added in v1.1.0 

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 added in v1.1.0 

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.

func (*DigraphBuilder) Weighted added in v1.2.0 

func (b *DigraphBuilder) Weighted() bool

Weighted reports whether the Builder carries edge weights: always for a NewWeightedDigraphBuilder, and from the first successful DigraphBuilder.AddEdgeW call on for a NewDigraphBuilder.

type Graph 

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

Graph is an immutable, undirected graph stored in Compressed Sparse Row form. The neighbors of node u occupy data[offsets[u]:offsets[u+1]] and are sorted ascending; on a weighted graph, weights uses the same indices. 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, Weights, EdgeOffset, NeighborsSeq, RandomNeighbor, and the Adjacency aliases) panic with a descriptive message when the ID is outside [0, N); HasEdge, Weight and EdgeIndex take an edge instead and report false for out-of-range endpoints. Slices returned by the accessors are views into the graph's storage with no spare capacity, so appending to one allocates rather than overwriting a neighbor's data.

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) EdgeIndex added in v1.2.0 

func (g *Graph) EdgeIndex(u, v int) (slot int, ok bool)

EdgeIndex returns the slot of the half-edge from u to v in the graph's edge-indexed arrays, that is EdgeOffset(u) plus the position of v in Neighbors(u). ok is false when the edge does not exist or an endpoint is out of range. It runs in O(log deg(u)).

func (*Graph) EdgeOffset added in v1.2.0 

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

EdgeOffset returns the index at which u's edges start in the graph's edge-indexed arrays: entry i of Neighbors(u), and of Weights(u), sits at slot EdgeOffset(u)+i in an array of length 2*NumEdges, one slot per half-edge. It exists so callers can keep per-edge data of their own in a plain slice laid out exactly like the adjacency and read it in the same loop that walks the neighbors. An undirected edge has a slot at each end; the convention in gonx is that both slots hold the same value. It panics if u is out of range.

Example 
package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
)

func main() {
	// Per-edge data of your own lives in a slice laid out like the adjacency:
	// slot EdgeOffset(u)+i belongs to the edge from u to Neighbors(u)[i].
	// Compute it once per half-edge, then read it in the hot loop with no map
	// lookup. Here the value is a resistance of 1/(deg(u)+deg(v)).
	b := gonx.NewBuilder(4)
	b.AddEdge(0, 1)
	b.AddEdge(1, 2)
	b.AddEdge(1, 3)
	g := b.Build()

	resistance := make([]float64, 2*g.NumEdges())
	for u := range g.Nodes() {
		off := g.EdgeOffset(u)
		for i, v := range g.Neighbors(u) {
			resistance[off+i] = 1 / float64(g.Degree(u)+g.Degree(int(v)))
		}
	}

	// Total resistance around node 1: three edges of 1/(3+1) each.
	var total float64
	off := g.EdgeOffset(1)
	for i := range g.Neighbors(1) {
		total += resistance[off+i]
	}
	fmt.Println(total)

	// EdgeIndex finds a single edge's slot without walking the row.
	slot, _ := g.EdgeIndex(2, 1)
	fmt.Println(resistance[slot])
}

Output:
0.75
0.25

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) HasNegativeWeight added in v1.2.0 

func (g *Graph) HasNegativeWeight() bool

HasNegativeWeight reports whether any edge weighs less than zero. It is always false on an unweighted graph. Build records the answer, so the call is O(1); algorithms that need non-negative weights check it once up front.

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) OutNeighbors added in v1.2.0 

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

OutNeighbors is Graph.Neighbors under the name Adjacency uses. An undirected edge can be walked from either end, so every neighbor is a successor.

func (*Graph) OutWeights added in v1.2.0 

func (g *Graph) OutWeights(u int) []float64

OutWeights is Graph.Weights under the name Adjacency uses.

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, weights included.

func (*Graph) Weight added in v1.2.0 

func (g *Graph) Weight(u, v int) (w float64, ok bool)

Weight returns the weight of the edge {u, v}. ok is false when the edge does not exist or an endpoint is out of range. On an unweighted graph every existing edge has weight 1. Like Graph.HasEdge it binary-searches the smaller-degree endpoint's list, so it runs in O(log deg).

func (*Graph) Weighted added in v1.2.0 

func (g *Graph) Weighted() bool

Weighted reports whether the graph carries edge weights. An unweighted graph stores no weight array at all: Weights returns nil for every node and Weight reports 1 for every edge.

func (*Graph) Weights added in v1.2.0 

func (g *Graph) Weights(u int) []float64

Weights returns the weights of u's edges, aligned index for index with Graph.Neighbors: Weights(u)[i] is the weight of the edge to Neighbors(u)[i]. The slice is zero-copy and MUST NOT be modified. It is nil when the graph is unweighted. It panics if u is out of range.

type Restricted added in v1.3.0 

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

Restricted is a read-only view of a graph with some nodes and edges hidden, made by RestrictedView. It implements Adjacency, so the traversals that take one, such as metrics.BreadthFirst, metrics.Dijkstra and metrics.ShortestPath, run on it unchanged and see only what is left.

A view shares the graph's storage and copies only the out-lists that lose an entry. Every other node's OutNeighbors and OutWeights are the graph's own slices, returned as they are. Telling the two apart takes one bit test for almost every node, and O(log t) when the test is inconclusive, where t is the number of nodes whose lists changed. A view is immutable and, like the graph, safe to read from several goroutines at once. The zero value is not a valid view.

func RestrictedView added in v1.3.0 

func RestrictedView(g Adjacency, nodes []int, edges [][2]int) *Restricted

RestrictedView returns a view of g with the given nodes and edges hidden, after networkx's restricted_view. Neither g nor the arguments are modified, and the view does not hold on to the argument slices.

Node IDs do not change. A hidden node stays in the view, since Adjacency numbers nodes densely from 0, but it has no edges in either direction: no traversal can enter it, and one that starts there goes nowhere. networkx drops the node instead; distances between the other nodes come out the same.

On an undirected Graph an edge is hidden as a whole, so {u, v} and {v, u} name the same edge and both of its directions disappear. On a Digraph, {u, v} hides only the edge from u to v. Edges between nodes in range that g does not have are ignored, as networkx ignores them; a node out of range, in either argument, panics.

The view keeps the weights of the edges it keeps. Weighted is the same as g's. HasNegativeWeight counts only the edges left, so hiding a graph's only negative edge makes the view usable for Dijkstra.

When g is itself a Restricted view, the result hides the union of both sets over the same underlying graph. g must be a *Graph, a *Digraph or a *Restricted, and any other Adjacency panics: a view is built from the graph's storage, not its methods, so a view of a type that wraps a graph would silently ignore every method the wrapper overrides. Pass the graph it wraps instead.

Building a view takes O(k log k + d) time, where k is the number of edges hidden, counting those taken out with hidden nodes, and d is the combined degree of the nodes whose lists change. A view of a view is built afresh from the union, so hiding edges one at a time through a chain of views costs O(k²) over k steps; pass them to one call instead.

Example 
package main

import (
	"fmt"

	"github.com/LuisLSousa/gonx"
	"github.com/LuisLSousa/gonx/metrics"
)

func main() {
	// A ring 0-1-2-3 with a short cut from 0 to 2. Hiding the short cut
	// answers "what is the best path if this edge were gone?" without
	// copying the graph, and without changing it for anyone else reading it.
	b := gonx.NewWeightedBuilder(4)
	b.AddEdgeW(0, 1, 2)
	b.AddEdgeW(1, 2, 2)
	b.AddEdgeW(2, 3, 1)
	b.AddEdgeW(3, 0, 1)
	b.AddEdgeW(0, 2, 1)
	g := b.Build()

	path, length, _ := metrics.ShortestPath(g, 0, 2)
	fmt.Println(path, length)
	view := gonx.RestrictedView(g, nil, [][2]int{{0, 2}})
	path, length, _ = metrics.ShortestPath(view, 0, 2)
	fmt.Println(path, length)
	// Hiding node 3 as well leaves the long way round.
	path, length, _ = metrics.ShortestPath(gonx.RestrictedView(view, []int{3}, nil), 0, 2)
	fmt.Println(path, length)
}

Output:
[0 2] 1
[0 3 2] 2
[0 1 2] 4

func (*Restricted) HasNegativeWeight added in v1.3.0 

func (r *Restricted) HasNegativeWeight() bool

HasNegativeWeight reports whether any edge left visible weighs less than zero. RestrictedView records the answer, so the call is O(1).

func (*Restricted) NumNodes added in v1.3.0 

func (r *Restricted) NumNodes() int

NumNodes reports the number of nodes, hidden ones included.

func (*Restricted) OutNeighbors added in v1.3.0 

func (r *Restricted) OutNeighbors(u int) []int32

OutNeighbors returns the targets of u's visible outgoing edges, ascending: the underlying graph's own slice when the view changes nothing at u, and otherwise a filtered copy the view holds. It is empty for a hidden node. Callers MUST NOT modify the returned slice. It panics if u is out of range.

func (*Restricted) OutWeights added in v1.3.0 

func (r *Restricted) OutWeights(u int) []float64

OutWeights returns the weights of u's visible outgoing edges, aligned with Restricted.OutNeighbors, or nil when the graph is unweighted. Callers MUST NOT modify the returned slice. It panics if u is out of range.

func (*Restricted) Weighted added in v1.3.0 

func (r *Restricted) Weighted() bool

Weighted reports whether the underlying graph carries edge weights.

Source Files

View all Source files

Directories

Path Synopsis
examples
communities command
Renders a planted-partition graph for the README gallery: four dense communities joined by sparse bridges, built directly with gonx.Builder and colored by community.
 Renders a planted-partition graph for the README gallery: four dense communities joined by sparse bridges, built directly with gonx.Builder and colored by community.
internal/render
Package render lays out gonx graphs and writes them as self-contained SVG images.
 Package render lays out gonx graphs and writes them as self-contained SVG images.
karate command
Renders Zachary's Karate Club — the classic 34-node social network from Zachary (1977) — for the README gallery.
 Renders Zachary's Karate Club — the classic 34-node social network from Zachary (1977) — for the README gallery.
scalefree command
Renders a Barabási–Albert scale-free network for the README gallery.
 Renders a Barabási–Albert scale-free network for the README gallery.
smallworld command
Renders a Watts–Strogatz small-world network for the README gallery.
 Renders a Watts–Strogatz small-world network for the README gallery.
Package generators builds graphs from classic random-graph models.
 Package generators builds graphs from classic random-graph models.
internal
pool
Package pool provides a minimal static work-partitioning helper used by the parallel graph metrics.
 Package pool provides a minimal static work-partitioning helper used by the parallel graph metrics.
Package metrics computes structural graph properties: clustering, connectivity, and shortest-path-based measures.
 Package metrics computes structural graph properties: clustering, connectivity, and shortest-path-based measures.
Package transform contains structure-preserving and structure-randomizing graph transformations: copying, relabeling, and degree-preserving edge swaps.
 Package transform contains structure-preserving and structure-randomizing graph transformations: copying, relabeling, and degree-preserving edge swaps.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.