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.
• Shortest paths: Dijkstra, Bellman-Ford, Floyd-Warshall, multi-source Dijkstra, k-center and transitive reduction.
• Connectivity: 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.
• Deterministic: a graph built the same way gives the same topological order, components and cliques on every run.

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.

Table of contents

• Installation
• Quick start
• Use cases
• Graphs
  • Directed
  • Acyclic
  • Undirected
  • Weighted
• Traversal
• Algorithms
• Diagrams
• Determinism
• Performance
• Examples
• Stability
• Roadmap
• Contributing
• Sponsoring
• License

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. BellmanFord and FloydWarshall require it.

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

Loading

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

Loading

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

Loading

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

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

Loading

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

Loading

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

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

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)

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

Loading

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.

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