README
¶
dag
Generic graph algorithms that work with any data structure, and the renderers that draw a workflow's jobs as a graph.
Installation
import "github.com/mozership/probe/dag"
Algorithms
Cycle Detection
Detects cycles in a graph using Depth-First Search (DFS) with a recursion stack.
| Function | Description | Complexity |
|---|---|---|
DetectCycleFn |
Detect cycle and return the cycle path | O(V + E) |
Usage
Pass a list of IDs and a dependency getter function. Works with any data structure.
// Dependencies: A → B → C → A
getDeps := func(id string) []string {
switch id {
case "A":
return []string{"B"}
case "B":
return []string{"C"}
case "C":
return []string{"A"}
default:
return nil
}
}
allIDs := []string{"A", "B", "C"}
if cycle := dag.DetectCycleFn(allIDs, getDeps); cycle != nil {
fmt.Println("Cycle found:", cycle) // [A B C]
}
Rendering
A Graph holds what a drawing needs: the jobs in declaration order, the
steps of each, and the jobs each one needs. A Renderer draws it as text.
| Renderer | Output |
|---|---|
ASCII |
Boxes of jobs and their steps, joined by lines to the jobs that need them |
Mermaid |
A Mermaid flowchart with a subgraph for each job, its steps linked in run order |
g := dag.Graph{Jobs: []dag.Job{
{ID: "build", Name: "Build", Steps: []dag.Step{{Name: "Compile"}}},
{ID: "test", Name: "Test", Needs: []string{"build"}, Steps: []dag.Step{{Name: "Run tests"}}},
}}
fmt.Print(dag.ASCII{}.Render(g))
fmt.Print(dag.Mermaid{}.Render(g))
A workflow builds its graph with Workflow.Graph, which also reads the steps
of the jobs that embedded steps run.
Documentation
¶
Overview ¶
Package dag provides generic graph algorithms that work with any data structure, and the renderers that draw a workflow's jobs as a graph.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DetectCycleFn ¶
func DetectCycleFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID
DetectCycleFn detects a cycle in a graph using a higher-order function. Returns the cycle path if found, nil otherwise.
Parameters:
- allIDs: All node identifiers in the graph
- getDeps: Function that returns dependencies (children) for a given node
Example:
getDeps := func(id string) []string {
switch id {
case "A": return []string{"B", "C"}
case "B": return []string{"C"}
default: return nil
}
}
cycle := DetectCycleFn([]string{"A", "B", "C"}, getDeps)
Types ¶
type ASCII ¶
type ASCII struct{}
ASCII draws a Graph as boxes of jobs and their steps, joined by lines from each job to the jobs that need it.
type Graph ¶
type Graph struct {
Jobs []Job
}
Graph is what a workflow's DAG is drawn from: its jobs in declaration order, the steps of each, and the jobs each one needs.
type Job ¶
type Job struct {
// ID identifies the job in other jobs' Needs. It is the job's id, or its
// name when it has none.
ID string
Name string
Needs []string
Steps []Step
}
Job is one node of a Graph.
type Mermaid ¶
type Mermaid struct{}
Mermaid draws a Graph as a Mermaid flowchart: a subgraph for each job with its steps linked in run order, and an edge from each job to the jobs that need it.
type Step ¶
type Step struct {
// Name is the step's name, or the action it uses when it has none.
Name string
// Embedded is set for a step that runs a job from another file.
Embedded bool
// EmbeddedFile is the base name of that file, and EmbeddedSteps the names
// of its steps. Both are empty when the file could not be read or has no
// steps.
EmbeddedFile string
EmbeddedSteps []string
}
Step is one step of a Job.
Source Files