GitHub - hmdsefi/gograph: Generic graph data structures and algorithms for Go (Golang): dependency graphs (DAGs) with cycle checks and topological sort, BFS and DFS traversal, Dijkstra and other shortest paths, connectivity and partitioning. No dependencies.

Dependency graphs and graph algorithms for Go, with no dependencies outside the standard library.

Documentation · Interactive demos · Examples · Changelog · Roadmap

_{path.Dijkstra finding the quickest drive from Canal St in Manhattan to Court St in Brooklyn on gograph.dev, where every algorithm runs step by step on example graphs.}

gograph is a generic graph library for Go (Golang) with first-class support for dependency graphs. Acyclic graphs refuse edges that would create a cycle, and TopologySort gives you an order to run things in. It also covers traversal, shortest paths, strongly connected components and graph partitioning.

Generic: vertex labels can be any comparable type, such as strings, integers or your own structs.
Graph data structures: directed, undirected, acyclic (DAG) and weighted graphs, with weights on vertices and edges.
Dependency graphs: Acyclic() graphs reject cycles, TopologySort returns a valid order, and the dag package finds what depends on what and what can run in parallel.
Traversal: BFS (breadth-first search), DFS (depth-first search), topological sort, closest-first and random-walk iterators, and depth-first search events that label each edge as a tree, back, forward or cross edge.
Shortest paths: Dijkstra, Bellman-Ford, Floyd-Warshall, multi-source Dijkstra, k-center and transitive reduction.
Connectivity: connected components and cycle detection that can return the cycle, strongly connected components with Tarjan, Kosaraju and Gabow, and condensation into a DAG.
Partitioning: maximal cliques (Bron-Kerbosch), Girvan-Newman communities and randomized k-cut.
Diagrams: encoding/mermaid writes a graph as a Mermaid flowchart that GitHub renders in Markdown, and encoding/dot writes it in the Graphviz DOT language for larger graphs.
Diffs: Diff lists the vertices, edges, weights and edge labels that changed between two graphs, one per line or as JSON, and Apply makes the same changes to a copy.
Deterministic: a graph built the same way gives the same topological order, components and cliques on every run.
Testing: gographtest checks topological orders, groups of vertices and whole graphs in tests, and builds paths, cycles, grids and seeded random graphs.

Imported by 20+ public Go modules, including the Cilium project's ariane, BoostSecurity's smokedmeat, simplecontainer and faultline, deterministic simulation testing for Go by the same author.

⭐ If gograph is useful to you, a star on GitHub helps other Go developers find it.

Installation

go get github.com/hmdsefi/gograph

gograph requires Go 1.26 or later and uses only the standard library.

Quick start

package main

import (
	"errors"
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	// An edge A -> B means A has to happen before B.
	g := gograph.New[string](gograph.Acyclic())

	checkout := g.AddVertexByLabel("checkout")
	build := g.AddVertexByLabel("build")
	test := g.AddVertexByLabel("test")
	release := g.AddVertexByLabel("release")

	_, _ = g.AddEdge(checkout, build)
	_, _ = g.AddEdge(build, test)
	_, _ = g.AddEdge(test, release)

	// Acyclic graphs reject any edge that would create a cycle.
	_, err := g.AddEdge(release, checkout)
	fmt.Println(errors.Is(err, gograph.ErrDAGCycle)) // true

	order, _ := gograph.TopologySort(g)
	for _, v := range order {
		fmt.Println(v.Label()) // checkout, build, test, release
	}
}

Use cases

Build and CI pipelines: order the steps with TopologySort, run independent steps together with dag.Levels or dag.Tracker, and find the chain of steps that sets the total time with dag.CriticalPath.
Task schedulers and workflow engines: dag.Tracker hands out tasks as their dependencies finish.
Incremental builds and spreadsheets: dag.Affected lists everything a change reaches, so you recompute only that.
Module and package dependencies: find requirement cycles with connectivity.Tarjan and collapse them with connectivity.Condense. The gomodgraph example does this for go mod graph output.
Routing and placement: shortest routes with path.Dijkstra, the nearest depot for every address with path.DijkstraMultiSource, and where to put k facilities with path.KCenter.
Networks and communities: loops in service calls with strongly connected components, and groups in a social graph with partition.MaximalCliques and partition.GirvanNewman.

Graphs

gograph.New[T] creates a graph. T is the vertex label type and must be comparable, so slices, maps and functions can't be labels. Options choose the kind of graph:

gograph.Directed() creates a directed graph. Without it, graphs are undirected.
gograph.Acyclic() creates a directed graph that rejects edges that would create a cycle.
gograph.Weighted() marks the graph as weighted. This flag is separate from weights supplied with WithEdgeWeight: Dijkstra uses those weights even without it. BellmanFord and FloydWarshall require the flag or return ErrNotWeighted; random walks use edge weights only when the flag is set.

Every graph implements the Graph[T] interface. See the package documentation for the full list of methods.

AddEdge creates missing vertices, so gograph.NewVertex is enough for quick examples. To keep a reference to a vertex, use AddVertexByLabel, which adds the vertex and returns it.

The diagrams in this section are the output of encoding/mermaid for each example graph.

Directed

flowchart LR
    n0["1"]
    n1["2"]
    n2["3"]
    n3["4"]
    n4["5"]
    n5["6"]
    n0 --> n1
    n0 --> n2
    n1 --> n3
    n2 --> n3
    n3 --> n4
    n4 --> n5

g := gograph.New[int](gograph.Directed())

_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(3))
_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(4))
_, _ = g.AddEdge(gograph.NewVertex(3), gograph.NewVertex(4))
_, _ = g.AddEdge(gograph.NewVertex(4), gograph.NewVertex(5))
_, _ = g.AddEdge(gograph.NewVertex(5), gograph.NewVertex(6))

Acyclic

flowchart LR
    n0["1"]
    n1["2"]
    n2["3"]
    n0 --> n1
    n1 --> n2

g := gograph.New[int](gograph.Acyclic())

_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(3))

_, err := g.AddEdge(gograph.NewVertex(3), gograph.NewVertex(1))
fmt.Println(err) // edges would create cycle

Undirected

flowchart LR
    n0["A"]
    n1["B"]
    n2["C"]
    n3["D"]
    n0 --- n1
    n0 --- n3
    n1 --- n2
    n1 --- n3

// Graphs are undirected by default.
g := gograph.New[string]()

a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
c := g.AddVertexByLabel("C")
d := g.AddVertexByLabel("D")

_, _ = g.AddEdge(a, b)
_, _ = g.AddEdge(a, d)
_, _ = g.AddEdge(b, c)
_, _ = g.AddEdge(b, d)

// Every undirected edge can be followed both ways.
fmt.Println(g.ContainsEdge(a, b), g.ContainsEdge(b, a)) // true true

An undirected edge between distinct vertices is stored in both directions. For two undirected edges A - B and A - C:

Call	Result
`g.Size()` / `len(g.AllEdges())`	4
`a.Degree()`	4
`a.InDegree()` / `a.OutDegree()`	2
`len(g.EdgesOf(a))`	4
`len(g.GetAllEdges(a, b))`	2

Use OutDegree() to count neighbors in an undirected graph. A self-loop has the same source and destination, so it has only one stored direction.

Weighted

flowchart LR
    n0["A"]
    n1["B"]
    n2["C"]
    n3["D"]
    n0 ---|"4"| n1
    n0 ---|"3"| n3
    n1 ---|"3"| n2
    n1 ---|"1"| n3
    n2 ---|"2"| n3

g := gograph.New[string](gograph.Weighted())

a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
c := g.AddVertexByLabel("C")
d := g.AddVertexByLabel("D")

_, _ = g.AddEdge(a, b, gograph.WithEdgeWeight(4))
_, _ = g.AddEdge(a, d, gograph.WithEdgeWeight(3))
_, _ = g.AddEdge(b, c, gograph.WithEdgeWeight(3))
_, _ = g.AddEdge(b, d, gograph.WithEdgeWeight(1))
_, _ = g.AddEdge(c, d, gograph.WithEdgeWeight(2))

dist := path.Dijkstra(g, "A")
fmt.Println(dist["C"]) // 5

Vertices can have weights too:

flowchart LR
    n0["A, weight 3"]
    n1["B, weight 2"]
    n2["C, weight 4"]
    n0 --> n1
    n1 --> n2

g := gograph.New[string](gograph.Directed(), gograph.Weighted())

a := g.AddVertexByLabel("A", gograph.WithVertexWeight(3))
b := g.AddVertexByLabel("B", gograph.WithVertexWeight(2))
c := g.AddVertexByLabel("C", gograph.WithVertexWeight(4))

_, _ = g.AddEdge(a, b)
_, _ = g.AddEdge(b, c)

fmt.Println(a.Weight(), b.Weight(), c.Weight()) // 3 2 4

Traversal

The traverse package provides iterators that all implement the same interface:

type Iterator[T comparable] interface {
	HasNext() bool
	Next() *gograph.Vertex[T]
	Iterate(func(v *gograph.Vertex[T]) error) error
	Reset()
}

g := gograph.New[string](gograph.Directed())

_, _ = g.AddEdge(gograph.NewVertex("A"), gograph.NewVertex("B"))
_, _ = g.AddEdge(gograph.NewVertex("A"), gograph.NewVertex("C"))
_, _ = g.AddEdge(gograph.NewVertex("B"), gograph.NewVertex("D"))

it, err := traverse.NewBreadthFirstIterator(g, "A")
if err != nil {
	fmt.Println(err)
	return
}

for it.HasNext() {
	fmt.Println(it.Next().Label()) // A, B, C, D
}

Iterator	Order	Demo
`NewBreadthFirstIterator`	Nearest vertices first, level by level	watch
`NewDepthFirstIterator`	Each branch as deep as it goes before the next	watch
`NewTopologicalIterator`	Topological order, one vertex at a time	watch
`NewClosestFirstIterator`	By shortest weighted distance from the start	watch
`NewRandomWalkIterator`	A random walk that picks each edge in proportion to its weight in a weighted graph	watch

The breadth-first, depth-first, closest-first and topological traversals also come as sequences for a range loop, so break stops one early and slices.Collect gathers it:

for v, depth := range traverse.BFSWithDepth(g, "A") {
	fmt.Println(v.Label(), depth) // A 0, B 1, C 1, D 2
}

traverse.BFS, DFS, BFSWithDepth, ClosestFirst and Topological follow the iterators above, and gograph.Vertices and gograph.Edges range over a whole graph. See Range over a traversal for details. traverse.DFSEvents and DFSEventsAll yield each step of a depth-first search, with the kind of each edge, as described in Depth-first search events.

Algorithms

V is the number of vertices and E the number of edges. Every link in the Demo column runs the algorithm step by step on example graphs at gograph.dev.

Ordering and subgraphs (gograph package)

Function	Answers	Time	Demo
`TopologySort`	An order where every edge points forward (Kahn's algorithm)	O(V+E)	watch
`StableTopologySort`	The same, picking the smallest ready vertex by your compare function	O((V+E) log V)	watch
`InducedSubgraph`	A chosen set of vertices and the edges between them	O(k+D) for k labels with D outgoing edges
`Clone`	A copy of the graph you can change without changing the original	O(V+E)
`Diff`	The vertices, edges, weights and edge labels that changed between two graphs	O(V+E)

Dependencies (dag package)

Function	Answers	Time	Demo
`Descendants`	What depends on a vertex	O(V+E)	watch
`Ancestors`	What a vertex depends on	O(V+E)	watch
`Affected`	Everything a change to some vertices reaches	O(V+E)	watch
`Sources`	Which vertices have no incoming edges	O(V)
`Sinks`	Which vertices have no outgoing edges	O(V)
`Levels`	Which vertices can run at the same time	O(V+E)
`NewTracker`	Which vertices are ready as others finish	O(V+E) in total
`CriticalPath`	The most expensive chain of dependent vertices	O(V+E)

Shortest paths (path package)

Shortest-path algorithm	Unreachable distance	Requirement
`path.Dijkstra` / `path.DijkstraSimple`	`math.MaxFloat64`	Non-negative weights; not checked
`path.BellmanFord`	`math.Inf(1)`	Directed and `Weighted()`; negative weights allowed, reachable negative cycles rejected
`path.FloydWarshall`	`math.Inf(1)`	Directed and `Weighted()`; negative weights allowed, negative cycles anywhere in the graph rejected

Function	Answers	Time	Demo
`Dijkstra`	Distances from one vertex, no negative weights	O((V+E) log V)	watch
`BellmanFord`	Distances from one vertex, negative weights allowed	O(V·E)	watch
`FloydWarshall`	Distances between every pair of vertices	O(V³)	watch
`DijkstraMultiSource`	Each vertex's nearest source, in one search	O((V+E) log V)
`KCenter`	k centers that keep every vertex close to one, within twice the best radius on undirected graphs	O(k (V+E) log V)
`TransitiveReduction`	The fewest edges that keep every path	O(V·(V+E))	watch

Connectivity (connectivity package, notes)

Function	Answers	Time	Demo
`ConnectedComponents`	Connected components. A directed graph is treated as undirected	O(V+E)
`HasCycle`	Whether the graph has a cycle, including a self-loop	O(V+E)
`FindCycle`	The vertices of one cycle, in order	O(V+E)
`Tarjan`	Strongly connected components	O(V+E)	watch
`Kosaraju`	Strongly connected components	O(V+E)	watch
`Gabow`	Strongly connected components	O(V+E)	watch
`Condense`	The DAG of components, one vertex per component	O(V+E)

Partitioning (partition package)

Function	Answers	Time	Demo
`MaximalCliques`	Every group where all vertices connect to each other (Bron-Kerbosch)	O(V·3^(V/3)) worst case, including the output	watch
`GirvanNewman`	Communities, by removing the most central edges	O(E·V·(V+E))	watch
`RandomizedKCut`	A split into k groups with few edges between them	O(V·E) per run	watch

Diagrams

encoding/mermaid writes a graph as a Mermaid flowchart, which GitHub and GitLab render in Markdown. Options set the direction, the vertex and edge text, and classes for highlighting:

g := gograph.New[string](gograph.Directed())

_, _ = g.AddEdge(gograph.NewVertex("checkout"), gograph.NewVertex("build"))
_, _ = g.AddEdge(g.GetVertexByID("build"), gograph.NewVertex("test"))

// highlight the vertices that failed
failed := map[string]bool{"test": true}

err := mermaid.Write(os.Stdout, g,
	mermaid.WithVertexClass(func(v *gograph.Vertex[string]) string {
		if failed[v.Label()] {
			return "failed"
		}
		return ""
	}),
	mermaid.WithClassDef[string]("failed", "fill:#f96"),
)

flowchart TD
    n0["build"]
    n1["checkout"]
    n2["test"]
    n0 --> n2
    n1 --> n0
    classDef failed fill:#f96
    class n2 failed

For graphs too large for a Mermaid diagram, encoding/dot writes the Graphviz DOT language, which dot -Tsvg turns into an image.

Determinism

When several orders are valid, TopologySort follows the order the vertices and edges were added, so the same graph gives the same result on every run. To choose the order yourself, StableTopologySort takes a compare function such as cmp.Compare and always picks the smallest vertex that is ready.

GetAllVertices returns vertices in the order they were added, and AllEdges and EdgesOf follow the same order. Tarjan, Kosaraju, Gabow, MaximalCliques, GirvanNewman and TransitiveReduction give the same result on every run for a graph built the same way.

Testing

gographtest helps test code that uses gograph. IsTopologicalOrder accepts any valid topological order, and SameGroups compares components, cliques or communities in any order, so a test keeps passing when an algorithm returns another valid answer. Equal compares two graphs whatever order they were built in, and lists the vertices and edges that differ. Its generators build paths, cycles, complete graphs, grids and seeded random graphs with the labels 0 to n-1:

func TestBuildOrder(t *testing.T) {
	g := gographtest.RandomDAG(500, 0.02, rand.New(rand.NewPCG(1, 2)))

	order, err := gograph.TopologySort(g)
	if err != nil {
		t.Fatal(err)
	}
	gographtest.IsTopologicalOrder(t, g, order)
}

Performance

Measured with go test -run '^$' -bench . -benchmem ./... on an Apple M4 Max with Go 1.27:

Benchmark	Graph	Time per run
`TopologySort`	Binary tree, 100,000 vertices	7.0 ms
`StableTopologySort`	Binary tree, 100,000 vertices	15.9 ms
`dag.CriticalPath`	Binary tree, 100,000 vertices	10.8 ms
`path.DijkstraMultiSource`	Path of 2,000 vertices, 32 sources	0.19 ms
`path.KCenter`	Path of 2,000 vertices, k = 32	0.31 ms
`InducedSubgraph`	256 vertices out of 4,000	0.05 ms

Each algorithm page on gograph.dev also has a performance card that times the algorithm on that page's example graphs.

Examples

gomodgraph: loads go mod graph output and finds requirement cycles, the modules that depend on a module, why a module is needed, which version of each module builds, what changed between two versions of go.mod, and a diagram of a module with its direct dependencies and dependents.

Stability

gograph follows semantic versioning and is used by other projects, so changes keep existing code working: exported interfaces keep their method sets, exported functions keep their signatures, and sentinel errors stay comparable with ==. The rules are in CONTRIBUTING.md, and every release is listed in the changelog.

Roadmap

Planned work, in the order it's likely to land, is tracked in #136. Issues labeled good first issue are a good place to start.

Contributing

Contributions are welcome. Please read CONTRIBUTING.md before opening a pull request. The README examples are also Go examples in example_test.go, so go test ./... checks that they still compile and print what they claim.

To report a security problem, follow SECURITY.md.

Sponsoring

If gograph saves you time, you can support its development through GitHub Sponsors.

License

Apache License 2.0, see LICENSE for details.

Name		Name	Last commit message	Last commit date
.agents/skills/gograph		.agents/skills/gograph
.github		.github
connectivity		connectivity
dag		dag
encoding		encoding
examples/gomodgraph		examples/gomodgraph
gographtest		gographtest
partition		partition
path		path
traverse		traverse
util		util
.coderabbit.yaml		.coderabbit.yaml
.gitignore		.gitignore
.golangci.yml		.golangci.yml
.testcoverage.yml		.testcoverage.yml
CHANGELOG.md		CHANGELOG.md
CODE_OF_CONDUCT.md		CODE_OF_CONDUCT.md
CONTRIBUTING.md		CONTRIBUTING.md
LICENSE		LICENSE
Makefile		Makefile
README.md		README.md
SECURITY.md		SECURITY.md
acyclic.go		acyclic.go
acyclic_order.go		acyclic_order.go
acyclic_order_test.go		acyclic_order_test.go
acyclic_test.go		acyclic_test.go
base.go		base.go
base_test.go		base_test.go
clone.go		clone.go
clone_test.go		clone_test.go
components.go		components.go
components_test.go		components_test.go
cycle.go		cycle.go
cycle_test.go		cycle_test.go
diff.go		diff.go
diff_test.go		diff_test.go
example_contracts_test.go		example_contracts_test.go
example_order_test.go		example_order_test.go
example_seq_test.go		example_seq_test.go
example_test.go		example_test.go
go.mod		go.mod
go.sum		go.sum
graph.go		graph.go
graph_test.go		graph_test.go
graph_types.go		graph_types.go
incoming_test.go		incoming_test.go
induced.go		induced.go
induced_test.go		induced_test.go
order_test.go		order_test.go
properties.go		properties.go
seq.go		seq.go
seq_test.go		seq_test.go
skill_test.go		skill_test.go
stable_topology_test.go		stable_topology_test.go

Navigation Menu

Repository navigation

About

Repository files navigation

⭐ If gograph is useful to you, a star on GitHub helps other Go developers find it.

Table of contents

Installation

Quick start

Use cases

Graphs

Directed

Acyclic

Undirected

Weighted

Traversal

Algorithms

Diagrams

Determinism

Testing

Performance

Examples

Stability

Roadmap

Contributing

Sponsoring

License

About

Releases

Sponsor this project

Used by

Contributors

Languages

Latest commit

History

Folders and files

Repository files navigation

⭐ If gograph is useful to you, a star on GitHub helps other Go developers find it.

Table of contents

Installation

Quick start

Use cases

Graphs

Directed

Acyclic

Undirected

Weighted

Traversal

Algorithms

Diagrams

Determinism

Testing

Performance

Examples

Stability

Roadmap

Contributing

Sponsoring

License

About

Topics

Resources

Code of conduct

Contributing

Security policy

Stars

Watchers

Forks

Releases

Sponsor this project

Used by

Contributors

Languages