Project: Package Dependency Resolver & Parallel Build Runner

Mix.install([
  {:yog_ex, path: "../.."},
  {:jason, "~> 1.4"},
  {:kino_vizjs, "~> 0.9.0"}
])

Introduction

Every modern language toolchain — including Mix (Elixir), Cargo (Rust), Go, and npm (Node.js) — relies on graph algorithms to compile code, resolve package versions, and coordinate parallel builds.

When you run mix compile, the build tool must answer several critical questions:

1. Validity: Does the project contain circular dependencies that make compilation impossible?
2. Redundancy: Which direct dependency declarations are transitively redundant?
3. Concurrency: Which packages can compile simultaneously in parallel without race conditions?
4. Bottlenecks: What is the Critical Path (the longest sequential chain) that dictates total build duration?
5. Incremental Compilation: If a low-level dependency changes, what is the exact blast radius of downstream packages that must be invalidated and recompiled?

In this project, we will construct a production-style package dependency resolver and parallel build scheduler using Yog.DAG, Yog.Transform, and Yog.Render.

Yog Concepts Covered

By the end, you will know how to:

• Model prerequisite relationships as a directed graph.
• Validate a graph as a DAG with Yog.DAG.from_graph/1.
• Detect dependency cycles before scheduling work.
• Remove redundant direct dependencies with transitive reduction.
• Group packages into parallel build waves with topological generations.
• Use DAG reachability for critical-path and incremental-build analysis.
• Render dependency graphs with DOT and Mermaid.

Why Yog Fits This Problem

Dependency resolution is a natural graph problem: packages are nodes, dependency constraints are directed edges, and build scheduling is topological ordering. Yog gives you both a general graph model for construction and a dedicated Yog.DAG layer once acyclicity has been validated.

Section 1: Ingesting the Package Manifest

We start with a realistic package ecosystem modeled after an Elixir web application stack (my_app, phoenix, ecto_sql, postgrex, jason, telemetry, db_connection, plug, etc.).

In compiler dependency graphs, edges are directed from prerequisite $\to$ consumer (dependency -> consumer). This means that a dependency must finish compiling before its consumers can start.

# Load from external JSON or fall back to an embedded manifest
manifest_path = Path.expand("data/package_deps.json", __DIR__)

raw_manifest =
  if File.exists?(manifest_path) do
    File.read!(manifest_path)
  else
    """
    {
      "packages": [
        { "name": "my_app", "version": "0.1.0", "deps": ["phoenix", "ecto_sql", "postgrex", "jason"] },
        { "name": "phoenix", "version": "1.7.14", "deps": ["plug", "plug_crypto", "telemetry", "phoenix_pubsub", "jason"] },
        { "name": "ecto_sql", "version": "3.11.3", "deps": ["ecto", "telemetry", "db_connection"] },
        { "name": "postgrex", "version": "0.18.0", "deps": ["db_connection", "decimal", "telemetry"] },
        { "name": "phoenix_pubsub", "version": "2.1.3", "deps": [] },
        { "name": "ecto", "version": "3.11.2", "deps": ["decimal", "telemetry"] },
        { "name": "db_connection", "version": "2.6.0", "deps": ["telemetry"] },
        { "name": "plug", "version": "1.16.1", "deps": ["plug_crypto", "telemetry"] },
        { "name": "plug_crypto", "version": "2.1.0", "deps": [] },
        { "name": "decimal", "version": "2.1.1", "deps": [] },
        { "name": "telemetry", "version": "1.2.1", "deps": [] },
        { "name": "jason", "version": "1.4.4", "deps": [] }
      ]
    }
    """
  end

data = Jason.decode!(raw_manifest)
packages = data["packages"]
IO.puts("Loaded #{length(packages)} package definitions.")

Now we convert the manifest into a Yog.Graph. Each edge {dep, pkg, compile_cost} indicates that dep must precede pkg. We'll also attach estimated compilation costs (in seconds) to each package.

# Compilation costs per package in estimated seconds
compile_times = %{
  "telemetry" => 2,
  "decimal" => 3,
  "jason" => 4,
  "plug_crypto" => 2,
  "phoenix_pubsub" => 3,
  "db_connection" => 5,
  "plug" => 6,
  "ecto" => 8,
  "postgrex" => 7,
  "ecto_sql" => 10,
  "phoenix" => 14,
  "my_app" => 12
}

# Build directed graph: prerequisite -> consumer
# Edge weight = compile time of the prerequisite
edges =
  for pkg <- packages,
      dep <- pkg["deps"] do
    weight = Map.get(compile_times, dep, 1)
    {dep, pkg["name"], weight}
  end

graph = Yog.from_edges(:directed, edges)

# Ensure isolated packages with 0 dependencies are also in the graph
graph =
  Enum.reduce(packages, graph, fn pkg, g ->
    Yog.add_node(g, pkg["name"], %{version: pkg["version"], cost: Map.get(compile_times, pkg["name"], 1)})
  end)

IO.puts("Graph constructed: #{Yog.node_count(graph)} packages, #{Yog.edge_count(graph)} dependency links.")

Expected result: the graph should contain all packages from the manifest, including packages with no dependencies, and one directed edge for every declared prerequisite relationship.

# Visualizing the raw dependency network
dot_opts = %{
  Yog.Render.DOT.default_options()
  | node_attributes: fn id, _ ->
      [shape: "box", style: "filled", fillcolor: "#f1f5f9", fontname: "Helvetica", fontsize: 11]
    end
}

Kino.Layout.tabs(
  "GraphViz DOT": Kino.VizJS.render(Yog.Render.DOT.to_dot(graph, dot_opts)),
  "Mermaid Flowchart": Kino.Mermaid.new(Yog.Render.Mermaid.to_mermaid(graph))
)

Section 2: Cycle Detection & Acyclicity Validation

Package dependency graphs must be acyclic (DAGs). A circular dependency ($A \to B \to A$) represents an unresolvable compiler deadlock.

Yog.DAG.from_graph/1 validates this property at the type level:

case Yog.DAG.from_graph(graph) do
  {:ok, dag} ->
    IO.puts("✅ Graph is a valid Directed Acyclic Graph (DAG)!")
    dag

  {:error, :cycle_detected} ->
    IO.puts("❌ Error: Circular dependency detected!")
end

Expected result: the original manifest should validate as a DAG. The next cell intentionally introduces a bad edge to show how Yog catches dependency cycles.

Let's test what happens when an invalid circular dependency is introduced (e.g. phoenix mistakenly depending on my_app):

broken_graph = Yog.add_edge_ensure(graph, "my_app", "telemetry", 1)

case Yog.DAG.from_graph(broken_graph) do
  {:ok, _dag} ->
    IO.puts("Valid DAG")

  {:error, :cycle_detected} ->
    IO.puts("🚨 Build aborted: Circular dependency detected between packages!")
    IO.puts("Is cyclic according to Yog.cyclic?: #{Yog.cyclic?(broken_graph)}")
end

Section 3: Transitive Reduction (Pruning Redundant Edges)

Often, manifests declare redundant dependencies. For instance, my_app directly declares jason and telemetry, but phoenix already depends on both.

Yog.Transform.transitive_reduction/1 removes these bypass shortcuts without altering the reachability or build constraints:

{:ok, reduced_graph} = Yog.Transform.transitive_reduction(graph)

IO.puts("Original dependency count: #{Yog.edge_count(graph)}")
IO.puts("Reduced dependency count:  #{Yog.edge_count(reduced_graph)}")
IO.puts("Pruned #{Yog.edge_count(graph) - Yog.edge_count(reduced_graph)} redundant transitive edges!")

Expected result: the reduced graph should have fewer or equal dependency links while preserving reachability. That means the build constraints are unchanged, but the visual and scheduling graph is simpler.

# Visualizing the streamlined dependency graph
reduced_dot =
  Yog.Render.DOT.to_dot(reduced_graph, %{
    dot_opts
    | node_attributes: fn id, _ ->
        [shape: "box", style: "filled,rounded", fillcolor: "#e2e8f0", fontname: "Helvetica"]
      end
  })

Kino.VizJS.render(reduced_dot)

Section 4: Topological Generations (Scheduling Maximum Concurrency)

A classic sequential topological sort (Yog.DAG.topological_sort/1) produces a single sequential sequence of packages to build. However, modern multicore CPUs can compile multiple packages in parallel.

Yog.DAG.topological_generations/1 organizes the packages into concurrency waves (generations):

• Generation 0: Leaf packages with no prerequisites (they can all compile immediately in parallel).
• Generation $i+1$: Packages whose prerequisites are all satisfied by Generation $\le i$.

{:ok, dag} = Yog.DAG.from_graph(reduced_graph)

generations = Yog.DAG.topological_generations(dag)

IO.puts("=== BUILD SCHEDULE (#{length(generations)} Sequential Stages) ===")

generations
|> Enum.with_index()
|> Enum.each(fn {stage_pkgs, stage_num} ->
  parallel_count = length(stage_pkgs)
  IO.puts("Stage #{stage_num} [#{parallel_count} workers]: #{Enum.join(stage_pkgs, ", ")}")
end)

max_parallelism = generations |> Enum.map(&length/1) |> Enum.max()
IO.puts("\nPeak Concurrency Width: #{max_parallelism} parallel jobs")

Expected result: packages in the same stage can be compiled concurrently; only the transition between stages is sequential.

Now let's create a beautiful visualization where each build stage is assigned a distinct color:

# Assign colors to each generation
stage_colors = [
  "#93c5fd", # Stage 0: Blue
  "#86efac", # Stage 1: Green
  "#fde047", # Stage 2: Yellow
  "#fdba74", # Stage 3: Orange
  "#f472b6"  # Stage 4: Pink
]

pkg_to_stage =
  generations
  |> Enum.with_index()
  |> Enum.flat_map(fn {pkgs, idx} -> Enum.map(pkgs, &{&1, idx}) end)
  |> Map.new()

stage_dot_opts = %{
  Yog.Render.DOT.default_options()
  | node_attributes: fn id, _ ->
      stage = Map.get(pkg_to_stage, id, 0)
      color = Enum.at(stage_colors, stage, "#ffffff")

      [
        shape: "box",
        style: "filled,rounded",
        fillcolor: color,
        fontname: "Helvetica-Bold",
        fontsize: 11,
        label: "#{id}\\n(Stage #{stage})"
      ]
    end
}

Kino.VizJS.render(Yog.Render.DOT.to_dot(reduced_graph, stage_dot_opts))

Section 5: Critical Path Analysis (Longest Path)

In project scheduling (PERT/CPM), the Critical Path is the longest sequence of dependent tasks through the network.

No matter how many CPU cores you have, your build can never finish faster than the total time taken by the packages along the critical path!

critical_path = Yog.DAG.longest_path(dag)

IO.puts("Critical Path: #{Enum.join(critical_path, " -> ")}")

critical_time =
  critical_path
  |> Enum.map(&Map.get(compile_times, &1, 0))
  |> Enum.sum()

IO.puts("Minimum theoretical build time: #{critical_time} seconds")

Expected result: the critical path is the lower bound for build time even with unlimited workers, because every package on that path depends on the previous one.

Let's highlight the critical path edges in bold red on the diagram:

critical_pairs = Enum.zip(critical_path, tl(critical_path)) |> MapSet.new()

critical_dot_opts = %{
  stage_dot_opts
  | edge_attributes: fn from, to, _weight ->
      if MapSet.member?(critical_pairs, {from, to}) do
        [color: "#dc2626", penwidth: 3.0]
      else
        [color: "#94a3b8", style: "solid"]
      end
    end
}

Kino.VizJS.render(Yog.Render.DOT.to_dot(reduced_graph, critical_dot_opts))

Section 6: Simulating a Concurrent Build Runner

Now we can write an asynchronous build engine using Task.async_stream to execute packages stage by stage:

defmodule BuildRunner do
  def run(generations, compile_times) do
    total_start = System.monotonic_time(:millisecond)

    Enum.each(generations, fn stage_pkgs ->
      IO.puts("\n🚀 Starting Stage: [#{Enum.join(stage_pkgs, ", ")}]")

      # Compile all packages in current stage concurrently
      stage_pkgs
      |> Task.async_stream(
        fn pkg ->
          duration_ms = Map.get(compile_times, pkg, 1) * 30
          Process.sleep(duration_ms)
          IO.puts("   ✔ Finished #{pkg} (#{duration_ms}ms)")
          pkg
        end,
        max_concurrency: System.schedulers_online()
      )
      |> Stream.run()
    end)

    total_duration = System.monotonic_time(:millisecond) - total_start
    IO.puts("\n🎉 Entire workspace built in #{total_duration}ms!")
  end
end

BuildRunner.run(generations, compile_times)

Section 7: Incremental Compilation & Blast Radius

When a developer edits code in a low-level dependency like telemetry, which packages need to be recompiled?

In a DAG where edges are dependency -> consumer:

• The blast radius of a package is its set of descendants (Yog.DAG.descendants/2).
• Unaffected packages can be retrieved directly from the compilation cache.

changed_package = "telemetry"

# Calculate all affected downstream packages
blast_radius = Yog.DAG.descendants(dag, changed_package) |> MapSet.new()

all_pkgs = Yog.DAG.to_graph(dag) |> Yog.all_nodes() |> MapSet.new()
cached_pkgs = MapSet.difference(all_pkgs, blast_radius)

IO.puts("Editing package: :#{changed_package}")
IO.puts("Packages requiring recompilation (#{MapSet.size(blast_radius)}): #{Enum.join(blast_radius, ", ")}")
IO.puts("Packages safely cached (#{MapSet.size(cached_pkgs)}): #{Enum.join(cached_pkgs, ", ")}")

Let's visualize the cache invalidation map: Red for recompiled packages, Green for cached packages:

cache_dot_opts = %{
  Yog.Render.DOT.default_options()
  | node_attributes: fn id, _ ->
      if MapSet.member?(blast_radius, id) do
        [shape: "box", style: "filled", fillcolor: "#fecaca", color: "#b91c1c", fontname: "Helvetica-Bold", label: "#{id}\\n(RECOMPILE)"]
      else
        [shape: "box", style: "filled", fillcolor: "#bbf7d0", color: "#15803d", fontname: "Helvetica", label: "#{id}\\n(CACHED)"]
      end
    end
}

Kino.VizJS.render(Yog.Render.DOT.to_dot(reduced_graph, cache_dot_opts))

Try Changing This

• Add a new dependency from "phoenix" to "my_app" and confirm Yog.DAG.from_graph/1 rejects the cycle.
• Increase the compile time for "phoenix" or "ecto_sql" and rerun the critical-path section.
• Change changed_package from "telemetry" to "jason" or "plug_crypto" and compare the blast radius.
• Remove a redundant dependency from the JSON manifest and see whether transitive reduction still prunes anything.

Summary

In this project, we built an end-to-end package dependency resolver using core graph algorithms:

• Cycle Detection (Yog.DAG.from_graph/1, Yog.cyclic?/1) to prevent compiler deadlocks.
• Transitive Reduction (Yog.Transform.transitive_reduction/1) to prune redundant direct declarations.
• Topological Generations (Yog.DAG.topological_generations/1) to schedule maximum multicore compilation parallelism.
• Critical Path Analysis (Yog.DAG.longest_path/1) to identify project build bottlenecks.
• Reachability & Blast Radius (Yog.DAG.descendants/2) to power smart, minimal incremental builds.