Documentation
¶
Overview ¶
Package dag answers the everyday questions about dependency graphs: what a vertex depends on, what depends on it, what a change affects, and which vertices can run at the same time.
Edge direction ¶
The functions follow the convention of gograph.TopologySort: an edge A -> B means A comes before B, or "B depends on A". So:
- Descendants of A are the vertices reachable from A, which is everything that depends on A.
- Ancestors of B are the vertices that can reach B, which is everything B depends on.
- Affected by a change to A are A and its descendants, which is everything that has to be rebuilt, retested or redeployed.
For example, with the edges checkout -> build, build -> test and build -> lint:
- Descendants(g, "build") returns test and lint.
- Ancestors(g, "test") returns build and checkout.
- Affected(g, "build") returns build, test and lint.
If a graph stores "A requires B" as A -> B instead, the meanings swap: Ancestors returns the dependents and Descendants returns the dependencies.
Running in dependency order ¶
Levels and Tracker help to run the vertices with plain goroutines or any other executor, starting each one after everything it depends on:
- Levels groups the vertices into levels that can each run at the same time, one level after the other. In the example above, the levels are [checkout], [build] and [test lint].
- Tracker hands out each vertex as soon as its own dependencies are done, so a slow vertex doesn't hold up the ones that don't depend on it.
Critical path ¶
CriticalPath finds the chain of dependent vertices with the largest total cost, which is what sets the total time when everything else runs in parallel. It adds up vertex and edge weights, and CriticalPathFunc takes the costs from functions, for durations kept outside the graph. In the example above, with checkout, build, test and lint taking 1, 10, 20 and 2, the critical path is checkout, build, test.
Sources and sinks ¶
Sources and Sinks answer which vertices have no prerequisites (where to start) and which have no dependents (final outputs or leftovers):
- Sources returns the vertices with no incoming edges (InDegree == 0).
- Sinks returns the vertices with no outgoing edges (OutDegree == 0).
In the example above, Sources(g) returns checkout, and Sinks(g) returns test and lint.
Behavior ¶
Descendants, Ancestors, Affected, Sources and Sinks work on any directed graph, including graphs with cycles. Levels, NewTracker and CriticalPath return gograph.ErrDAGHasCycle for a graph with a cycle, since its vertices can't run in dependency order. All functions return gograph.ErrNotDirected for undirected graphs, and an error that matches gograph.ErrVertexDoesNotExist with errors.Is if a label is not in the graph.
Sources and Sinks follow the order of GetAllVertices. Vertices on a cycle are never sources or sinks, a self-loop counts as an incoming and an outgoing edge, and isolated vertices are both. An empty graph returns an empty slice and no error.
Every function returns each vertex once, as the graph's own vertex pointers. The results of Descendants, Ancestors and Affected are in breadth-first order, nearest first. The search visits the outgoing edges of each vertex in the order they were added (Descendants, Affected), or its incoming edges in AllEdges order (Ancestors), so vertices at the same distance are grouped by the vertex that reached them first.
All searches are iterative, so long chains don't grow the call stack.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func main() {
// An edge A -> B means B depends on A.
g := gograph.New[string](gograph.Acyclic())
checkout := g.AddVertexByLabel("checkout")
build := g.AddVertexByLabel("build")
test := g.AddVertexByLabel("test")
lint := g.AddVertexByLabel("lint")
_, _ = g.AddEdge(checkout, build)
_, _ = g.AddEdge(build, test)
_, _ = g.AddEdge(build, lint)
descendants, _ := dag.Descendants(g, "build")
fmt.Println("depends on build:", labels(descendants))
ancestors, _ := dag.Ancestors(g, "test")
fmt.Println("test depends on:", labels(ancestors))
affected, _ := dag.Affected(g, "build")
fmt.Println("rebuild after a build change:", labels(affected))
}
Output: depends on build: [test lint] test depends on: [build checkout] rebuild after a build change: [build test lint]
Index ¶
- Variables
- func Affected[T comparable](g gograph.Graph[T], changed ...T) ([]*gograph.Vertex[T], error)
- func Ancestors[T comparable](g gograph.Graph[T], label T) ([]*gograph.Vertex[T], error)
- func CriticalPath[T comparable](g gograph.Graph[T]) ([]*gograph.Vertex[T], float64, error)
- func CriticalPathFunc[T comparable](g gograph.Graph[T], vertexCost func(*gograph.Vertex[T]) float64, ...) ([]*gograph.Vertex[T], float64, error)
- func Descendants[T comparable](g gograph.Graph[T], label T) ([]*gograph.Vertex[T], error)
- func Levels[T comparable](g gograph.Graph[T]) ([][]*gograph.Vertex[T], error)
- func Sinks[T comparable](g gograph.Graph[T]) ([]*gograph.Vertex[T], error)
- func Sources[T comparable](g gograph.Graph[T]) ([]*gograph.Vertex[T], error)
- type Tracker
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrNotReady is returned by Tracker.Done for a vertex that Ready hasn't // returned yet. ErrNotReady = errors.New("vertex was not returned by Ready") // ErrAlreadyDone is returned by Tracker.Done for a vertex that is already // done. ErrAlreadyDone = errors.New("vertex is already done") )
Functions ¶
func Affected ¶
Affected returns the changed vertices and every vertex reachable from any of them. The changed vertices come first, in the order given, followed by the others, nearest first. A label that is given more than once, or that is reachable from another changed vertex, is returned once.
It runs in O(V + E) time for the part of the graph it reaches.
func Ancestors ¶
Ancestors returns the vertices that can reach the vertex with the given label, nearest first. The vertex itself is only included if it's on a cycle.
It reads all edges once to find the incoming ones, and runs in O(V + E) time.
func CriticalPath ¶ added in v0.9.0
CriticalPath returns the path through a directed acyclic graph with the largest total cost, and that cost. The cost of a path is the sum of the weights of its vertices and of its edges. When tasks run in parallel, this is the longest chain of dependent tasks, so it sets the total time.
Weights are read with Vertex.Weight and Edge.Weight, and unset weights are 0. The graph doesn't have to be created with Weighted(). Negative weights are allowed.
The path starts at a vertex with no incoming edges and ends at one with no outgoing edges, so a vertex without a weight, like a start or finish milestone, stays on it. An empty graph returns a nil path and a cost of 0. If several paths have the same cost, the one found first in topological order wins, so the same graph gives the same path on every run. The returned vertices are the graph's own pointers.
It runs in O(V + E) time.
It returns gograph.ErrNotDirected for undirected graphs, and gograph.ErrDAGHasCycle if the graph has a cycle.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func main() {
// the weight of a vertex is how long the task takes
g := gograph.New[string](gograph.Directed())
checkout := g.AddVertexByLabel("checkout", gograph.WithVertexWeight(1))
build := g.AddVertexByLabel("build", gograph.WithVertexWeight(10))
test := g.AddVertexByLabel("test", gograph.WithVertexWeight(20))
lint := g.AddVertexByLabel("lint", gograph.WithVertexWeight(2))
_, _ = g.AddEdge(checkout, build)
_, _ = g.AddEdge(build, test)
_, _ = g.AddEdge(build, lint)
path, cost, err := dag.CriticalPath(g)
if err != nil {
fmt.Println(err)
return
}
fmt.Println(labels(path), cost)
}
Output: [checkout build test] 31
func CriticalPathFunc ¶ added in v0.9.0
func CriticalPathFunc[T comparable]( g gograph.Graph[T], vertexCost func(*gograph.Vertex[T]) float64, edgeCost func(*gograph.Edge[T]) float64, ) ([]*gograph.Vertex[T], float64, error)
CriticalPathFunc works like CriticalPath, but takes the costs from vertexCost and edgeCost instead of the weights stored in the graph. That suits costs kept outside the graph, such as measured durations. A nil function means a cost of 0.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func pipeline() gograph.Graph[string] {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"checkout", "build"},
{"checkout", "docs"},
{"build", "test"},
{"build", "lint"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
return g
}
func main() {
// durations kept outside the graph
duration := map[string]float64{"checkout": 1, "build": 10, "test": 20, "lint": 2}
path, cost, err := dag.CriticalPathFunc(pipeline(),
func(v *gograph.Vertex[string]) float64 { return duration[v.Label()] },
nil,
)
if err != nil {
fmt.Println(err)
return
}
fmt.Println(labels(path), cost)
}
Output: [checkout build test] 31
func Descendants ¶
Descendants returns the vertices reachable from the vertex with the given label, nearest first. The vertex itself is only included if it's on a cycle.
It runs in O(V + E) time for the part of the graph it reaches.
func Levels ¶ added in v0.9.0
Levels groups the vertices of a directed acyclic graph so that every edge goes from a lower level to a higher one. Level 0 has the vertices with no incoming edges, and the level of any other vertex is the length of the longest path to it from one of those. Vertices in the same level have no edges between them, so they can run at the same time once every level before theirs is done.
The vertices of each level follow the order of GetAllVertices, as the graph's own vertex pointers. It runs in O(V + E) time.
It returns gograph.ErrNotDirected for undirected graphs, and gograph.ErrDAGHasCycle if the graph has a cycle.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func pipeline() gograph.Graph[string] {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"checkout", "build"},
{"checkout", "docs"},
{"build", "test"},
{"build", "lint"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
return g
}
func main() {
levels, err := dag.Levels(pipeline())
if err != nil {
fmt.Println(err)
return
}
// the vertices of a level can run at the same time
for i, level := range levels {
fmt.Println(i, labels(level))
}
}
Output: 0 [checkout] 1 [build docs] 2 [test lint]
func Sinks ¶ added in v0.9.0
Sinks returns the vertices of a directed graph with no outgoing edges, in the order of GetAllVertices, as the graph's own vertex pointers.
It works on any directed graph, with or without cycles. A vertex on a cycle is never a sink. Isolated vertices have no outgoing edges, so they are included. A self-loop counts as an outgoing edge, so a vertex whose only edge is a self-loop is not a sink. An empty graph returns an empty slice and no error.
It returns gograph.ErrNotDirected for undirected graphs. It runs in O(V) time.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func pipeline() gograph.Graph[string] {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"checkout", "build"},
{"checkout", "docs"},
{"build", "test"},
{"build", "lint"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
return g
}
func main() {
g := pipeline()
sinks, err := dag.Sinks(g)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("sinks:", labels(sinks))
}
Output: sinks: [docs test lint]
func Sources ¶ added in v0.9.0
Sources returns the vertices of a directed graph with no incoming edges, in the order of GetAllVertices, as the graph's own vertex pointers.
It works on any directed graph, with or without cycles. A vertex on a cycle is never a source. Isolated vertices have no incoming edges, so they are included. A self-loop counts as an incoming edge, so a vertex whose only edge is a self-loop is not a source. An empty graph returns an empty slice and no error.
It returns gograph.ErrNotDirected for undirected graphs. It runs in O(V) time.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func pipeline() gograph.Graph[string] {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"checkout", "build"},
{"checkout", "docs"},
{"build", "test"},
{"build", "lint"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
return g
}
func main() {
g := pipeline()
sources, err := dag.Sources(g)
if err != nil {
fmt.Println(err)
return
}
fmt.Println("sources:", labels(sources))
}
Output: sources: [checkout]
Types ¶
type Tracker ¶ added in v0.9.0
type Tracker[T comparable] struct { // contains filtered or unexported fields }
Tracker hands out the vertices of a directed acyclic graph as soon as every vertex they depend on is done. Unlike with Levels, a slow vertex only holds up the vertices that depend on it.
Ready returns the vertices that can start, and Done marks vertices as finished, which can make the vertices that depend on them ready. As in the rest of the package, an edge A -> B means B depends on A, so Ready returns B once A is done.
A Tracker isn't safe for concurrent use. The usual pattern is a single goroutine that starts a worker for each ready vertex, and calls Done as the results come back on a channel:
t, err := dag.NewTracker(g)
if err != nil {
return err
}
// buffered, so workers don't block if the loop returns early
results := make(chan result, g.Order())
for t.Remaining() > 0 {
for _, v := range t.Ready() {
go func() {
results <- result{label: v.Label(), err: run(ctx, v.Label())}
}()
}
r := <-results
if r.err != nil {
return r.err
}
if err := t.Done(r.label); err != nil {
return err
}
}
What to do when a vertex fails is up to the caller. To skip the vertices that depend on a failed one and keep going with the others, mark the failed vertex done and, when Ready returns any of its Descendants, mark them done without running them.
Example ¶
package main
import (
"fmt"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func labels(vertices []*gograph.Vertex[string]) []string {
out := make([]string, len(vertices))
for i, v := range vertices {
out[i] = v.Label()
}
return out
}
func pipeline() gograph.Graph[string] {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"checkout", "build"},
{"checkout", "docs"},
{"build", "test"},
{"build", "lint"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
return g
}
func main() {
t, err := dag.NewTracker(pipeline())
if err != nil {
fmt.Println(err)
return
}
fmt.Println("ready:", labels(t.Ready()))
_ = t.Done("checkout")
fmt.Println("ready:", labels(t.Ready()))
// test and lint start without waiting for docs
_ = t.Done("build")
fmt.Println("ready:", labels(t.Ready()))
fmt.Println("remaining:", t.Remaining())
}
Output: ready: [checkout] ready: [build docs] ready: [test lint] remaining: 3
Example (Workers) ¶
package main
import (
"fmt"
"sort"
"github.com/hmdsefi/gograph"
"github.com/hmdsefi/gograph/dag"
)
func pipeline() gograph.Graph[string] {
g := gograph.New[string](gograph.Directed())
for _, e := range [][2]string{
{"checkout", "build"},
{"checkout", "docs"},
{"build", "test"},
{"build", "lint"},
} {
_, _ = g.AddEdge(gograph.NewVertex(e[0]), gograph.NewVertex(e[1]))
}
return g
}
func main() {
g := pipeline()
t, err := dag.NewTracker(g)
if err != nil {
fmt.Println(err)
return
}
run := func(label string) error {
return nil // run the task here
}
type result struct {
label string
err error
}
// buffered, so workers don't block if the loop returns early
results := make(chan result, g.Order())
var finished []string
for t.Remaining() > 0 {
for _, v := range t.Ready() {
go func() {
results <- result{label: v.Label(), err: run(v.Label())}
}()
}
r := <-results
if r.err != nil {
fmt.Println(r.label, "failed:", r.err)
return
}
if err := t.Done(r.label); err != nil {
fmt.Println(err)
return
}
finished = append(finished, r.label)
}
sort.Strings(finished)
fmt.Println(finished)
}
Output: [build checkout docs lint test]
func NewTracker ¶ added in v0.9.0
func NewTracker[T comparable](g gograph.Graph[T]) (*Tracker[T], error)
NewTracker returns a Tracker for g. It copies what it needs from g, so changes to g afterwards don't affect the Tracker.
It returns gograph.ErrNotDirected for undirected graphs, and gograph.ErrDAGHasCycle if the graph has a cycle.
func (*Tracker[T]) Done ¶ added in v0.9.0
Done marks the vertices with the given labels as finished, so the vertices that depend on them can become ready. Each one must have been returned by Ready.
It returns an error that matches gograph.ErrVertexDoesNotExist with errors.Is if a label isn't in the graph, ErrNotReady if Ready hasn't returned the vertex, and ErrAlreadyDone if the vertex is already done or its label is given more than once. If it returns an error, none of the vertices are marked done.
func (*Tracker[T]) Ready ¶ added in v0.9.0
Ready returns the vertices whose dependencies are all done and that Ready hasn't returned before, as the graph's own vertex pointers. It returns nil if there are none.
The first call returns the vertices with no dependencies, in the order of GetAllVertices. After that, vertices come in the order they became ready: following the order of the Done calls, and for each vertex marked done, the order its edges were added.
Source Files