gograph

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.

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

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:

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
}

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)

Dependencies (dag package)

Shortest paths (path package)

Connectivity (connectivity package, notes)

Partitioning (partition package)

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:

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.