!build

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.Newstring)
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 returns one of them, and which one can change between runs. A deterministic order is planned in #114.

Table of contents

• Graphs

• Traversal
• Algorithms
• 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.

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

!directed-graph

g := gograph.Newint)
_, _ = 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

!acyclic-graph

g := gograph.Newint)
_, _ = 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

!undirected-graph

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

!weighted-edge

g := gograph.Newstring)
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:

!weighted-vertex

g := gograph.Newstring, 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.Newstring)
_, _ = 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).
• Shortest paths (path package):

• Transitive reduction (path package):

• Strongly connected components (connectivity package):

• Partitioning (partition package):

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.