Baton.DAG (Baton v0.1.0)

Copy Markdown View Source

Directed Acyclic Graph validation for workflow step definitions.

Performs cycle detection via Kahn's algorithm (topological sort) at workflow build time — before any jobs are inserted into the database. This gives you a fast, clear error if you accidentally create a circular dependency.

Example

alias Baton.DAG

steps = [
  %{name: "a", deps: []},
  %{name: "b", deps: ["a"]},
  %{name: "c", deps: ["b"]},
  %{name: "d", deps: ["b"]},
  %{name: "e", deps: ["c", "d"]}
]

{:ok, order} = DAG.validate(steps)
# => {:ok, ["a", "b", "c", "d", "e"]}  (one valid topological order)

If a cycle exists:

steps = [
  %{name: "a", deps: ["c"]},
  %{name: "b", deps: ["a"]},
  %{name: "c", deps: ["b"]}
]

{:error, reason} = DAG.validate(steps)
# => {:error, {:cycle_detected, ["a", "b", "c"]}}

Summary

Types

step()
validation_error()

Functions

format_error(arg)

Returns a human-readable description of a validation error.

validate(steps)

Validate a list of workflow steps for DAG correctness.

Types

step()

@type step() :: %{name: String.t(), deps: [String.t()]}

validation_error()

@type validation_error() ::
  {:cycle_detected, [String.t()]}
  | {:unknown_deps, [{step_name :: String.t(), unknown :: [String.t()]}]}
  | {:duplicate_names, [String.t()]}

Functions

format_error(arg)

@spec format_error(validation_error()) :: String.t()

Returns a human-readable description of a validation error.

validate(steps)

@spec validate([step()]) :: {:ok, [String.t()]} | {:error, validation_error()}

Validate a list of workflow steps for DAG correctness.

Checks:

  1. No duplicate step names
  2. All referenced deps exist as named steps
  3. No cycles (via Kahn's topological sort)

Returns {:ok, topological_order} or {:error, reason}.