# Project: Package Dependency Resolver & Parallel Build Runner

```elixir
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.

```elixir
# 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.

```elixir
# 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.

```elixir
# 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:

```elixir
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`):

```elixir
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:

```elixir
{: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.

```elixir
# 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$.

```elixir
{: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**:

```elixir
# 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!

```elixir
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:

```elixir
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:

```elixir
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.

```elixir
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:

```elixir
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.