GoGraph

GoGraph is a generic graph library for Go 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, with no dependencies outside the standard library.

• Generic: vertex labels can be any comparable type, such as strings, integers or your own structs.
• Dependency graphs: Acyclic() graphs reject cycles, TopologySort returns a valid order, and the dag package finds what depends on what.
• Traversal: BFS, DFS, topological, closest-first and random-walk iterators.
• Paths: Dijkstra, Bellman-Ford, Floyd-Warshall and transitive reduction.
• Connectivity: strongly connected components with Tarjan, Kosaraju and Gabow.
• 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.

Imported by 20+ public Go modules.

Quick start

go get github.com/hmdsefi/gograph

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

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.

Table of contents

• Graphs
  • Directed
  • Acyclic
  • Undirected
  • Weighted
• Traversal
• Algorithms
• Examples
• Roadmap
• Contributing
• License

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.

Directed

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(2))
_, _ = 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

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

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

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:

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
}

Available iterators:

• Breadth-first
• Depth-first
• Topological
• Closest-first
• Random walk

Algorithms

• Ordering: gograph.TopologySort (Kahn's algorithm) and gograph.StableTopologySort (smallest ready vertex first).
• Shortest paths (path package): Dijkstra, Bellman-Ford, Floyd-Warshall.
• Transitive reduction (path package): TransitiveReduction.
• Dependencies (dag package): Descendants (what depends on a vertex), Ancestors (what it depends on) and Affected (what a change reaches).
• Strongly connected components (connectivity package): Tarjan, Kosaraju and Gabow.
• Partitioning (partition package): maximal cliques (Bron-Kerbosch), Girvan-Newman, randomized k-cut.

Examples

• gomodgraph: loads go mod graph output and finds requirement cycles, the modules that depend on a module, why a module is needed, and what changed between two versions of go.mod.

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.

License

Apache License 2.0, see LICENSE for details.