Pipette.Graph (Pipette v0.6.0)

Directed Acyclic Graph (DAG) for pipeline dependency management.

Builds a dependency graph from groups and steps, supports cycle detection, and computes transitive dependencies (ancestors).

Example

groups = [
  %Pipette.Group{name: :lint, steps: []},
  %Pipette.Group{name: :test, depends_on: :lint, steps: []},
  %Pipette.Group{name: :deploy, depends_on: :test, steps: []}
]

graph = Pipette.Graph.from_groups(groups)
Pipette.Graph.acyclic?(graph)          #=> true
Pipette.Graph.ancestors(graph, :deploy) #=> MapSet.new([:test, :lint])

Summary

Types

node_id()

t()

Functions

acyclic?(graph)

Return true if the graph has no cycles.

add_edge(graph, from, to)

Add a directed edge from from to to. Both nodes are added if not present.

add_node(graph, node)

Add a node to the graph. Returns the graph unchanged if the node already exists.

ancestors(graph, node)

Compute the transitive dependencies (ancestors) of a node.

edges(graph)

Return all edges as a list of {from, to} tuples.

find_cycle(graph)

Find a cycle in the graph, if one exists.

from_groups(groups)

Build a dependency graph from a list of groups.

has_edge?(graph, from, to)

Check if a directed edge exists from from to to.

has_node?(graph, node)

Check if a node exists in the graph.

new()

Create an empty graph.

Types

node_id()

@type node_id() :: atom() | {atom(), atom()}

t()

@type t() :: %Pipette.Graph{
  edges: %{required(node_id()) => MapSet.t(node_id())},
  nodes: MapSet.t(node_id())
}

Functions

acyclic?(graph)

@spec acyclic?(t()) :: boolean()

Return true if the graph has no cycles.

add_edge(graph, from, to)

@spec add_edge(t(), node_id(), node_id()) :: t()

Add a directed edge from from to to. Both nodes are added if not present.

add_node(graph, node)

@spec add_node(t(), node_id()) :: t()

Add a node to the graph. Returns the graph unchanged if the node already exists.

ancestors(graph, node)

@spec ancestors(t(), node_id()) :: MapSet.t(node_id())

Compute the transitive dependencies (ancestors) of a node.

Follows edges recursively to find all nodes that node depends on, directly or transitively.

Examples

graph = Pipette.Graph.from_groups([
  %Pipette.Group{name: :lint, steps: []},
  %Pipette.Group{name: :test, depends_on: :lint, steps: []},
  %Pipette.Group{name: :deploy, depends_on: :test, steps: []}
])

Pipette.Graph.ancestors(graph, :deploy)
#=> MapSet.new([:test, :lint])

edges(graph)

@spec edges(t()) :: [{node_id(), node_id()}]

Return all edges as a list of {from, to} tuples.

find_cycle(graph)

@spec find_cycle(t()) :: [node_id()] | nil

Find a cycle in the graph, if one exists.

Returns a list of nodes forming the cycle path, or nil if the graph is acyclic. Uses DFS with three-color marking.

from_groups(groups)

@spec from_groups([Pipette.Group.t()]) :: t()

Build a dependency graph from a list of groups.

Creates nodes for each group and step, with edges representing depends_on relationships at both the group and step level.

Examples

groups = [
  %Pipette.Group{name: :lint, steps: []},
  %Pipette.Group{name: :test, depends_on: :lint, steps: []}
]

graph = Pipette.Graph.from_groups(groups)
Pipette.Graph.has_edge?(graph, :test, :lint)  #=> true

has_edge?(graph, from, to)

@spec has_edge?(t(), node_id(), node_id()) :: boolean()

Check if a directed edge exists from from to to.

has_node?(graph, node)

@spec has_node?(t(), node_id()) :: boolean()

Check if a node exists in the graph.

new()

@spec new() :: t()

Create an empty graph.