depgraph

A dependency resolution engine in Go, built as an tutorial example project for graph algorithms in data structures and algorithms.

The core problem: given a set of packages where each one may depend on others, determine a valid installation order, and detect when no such order exists because of circular dependencies.

This is not a toy problem. Every package manager you use daily — go mod, npm, apt, cargo, solves exactly this.

---

The Problem

Imagine three packages:

app   depends on → http, db
http  depends on → logger
db    depends on → logger

You cannot install app before http and db are ready. You cannot install http before logger is ready. The question is: what is a valid install order?

The answer is a classic graph problem. Model each package as a node and each dependency as a directed edge. A valid install order exists if and only if the graph is a Directed Acyclic Graph (DAG), a directed graph with no cycles. Finding that order is called a topological sort.

---

Algorithms

1. Kahn's Algorithm — kahn.go

Kahn's algorithm is a BFS-based approach to topological sorting. It works by repeatedly removing nodes that have no remaining dependencies.

Key concept — in-degree: The in-degree of a node is the number of edges pointing into it. A node with in-degree 0 has no unresolved dependencies and is safe to install immediately.

Steps:

1. Compute the in-degree of every node.
2. Collect all nodes with in-degree 0 into a queue.
3. Dequeue a node, add it to the result, and decrement the in-degree of every node it depends on.
4. If a neighbour's in-degree drops to 0, enqueue it.
5. Repeat until the queue is empty.

If the result contains fewer nodes than the graph, some nodes were unreachable from the zero-in-degree frontier — they form a cycle.

Initial in-degrees:
  logger: 0   config: 0   http: 1   db: 2   app: 3

Queue: [config, logger]
Process logger → decrement http(→0), db(→1)  →  Queue: [config, http]
Process config → decrement db(→0), app(→2)   →  Queue: [http, db]
Process http   → decrement app(→1)            →  Queue: [db]
Process db     → decrement app(→0)            →  Queue: [app]
Process app    → done

Result: logger → config → http → db → app

Complexity: O(V + E) time, O(V) space.

Real-world use: npm install, go mod download, GNU Make, task schedulers.

---

2. DFS Topological Sort — dfs.go

The DFS approach discovers the install order as a side effect of depth-first traversal. The key insight: a node can only be considered "done" after all of its dependencies are fully resolved.

Three-color marking:

Each node is in one of three states:

Color	Meaning
white	Not yet visited
gray	Currently on the DFS call stack (being explored)
black	Fully processed; all descendants resolved

When we visit a node's dependency and find it is gray, we have followed a back-edge — an edge that points back to an ancestor in the current path. This is precisely what a cycle looks like in a directed graph.

Steps:

1. For each unvisited node, call dfsVisit.
2. Mark the node gray (in progress).
3. Recurse into each unvisited dependency.
4. If a dependency is gray → cycle detected; return an error.
5. After all dependencies are resolved, mark the node black and push it onto a stack.
6. Reversing the stack gives the install order.

dfsVisit(app)
  gray: app
  dfsVisit(http)
    gray: http
    dfsVisit(logger)
      gray: logger  →  no deps  →  black: logger  →  push logger
    back in http: logger is black, skip
    black: http  →  push http
  dfsVisit(db)
    gray: db
    logger is black → skip
    dfsVisit(config)
      gray: config  →  no deps  →  black: config  →  push config
    black: db  →  push db
  black: app  →  push app

Stack (bottom → top): logger, http, config, db, app
Reversed: logger → config → db → http → app

Cycle detection example:

dfsVisit(A)
  gray: A
  dfsVisit(B)
    gray: B
    dfsVisit(C)
      gray: C
      visit A → A is gray → CYCLE: C → A

Complexity: O(V + E) time, O(V) space.

Real-world use: apt dependency resolution, linker symbol resolution, spreadsheet formula evaluation.

---

3. Parallel Install Layers — layers.go

A topological sort gives one valid sequential order. But it leaves a question unanswered: which packages have no dependency on each other and could therefore be installed at the same time?

Parallel layers answer this. Each layer is a set of packages whose dependencies were all resolved in previous layers — meaning every package in a layer is safe to install concurrently.

Steps:

1. Compute in-degrees (same as Kahn).
2. Collect all nodes with in-degree 0 → this is layer 1.
3. Remove those nodes from the graph (decrement their neighbours' in-degrees).
4. Repeat until all nodes are processed.

Graph: app → moduleB, moduleC    moduleB → core    moduleC → core

Round 1 — in-degree 0: [core]           →  layer 1: [core]
Round 2 — in-degree 0: [moduleB, moduleC]  →  layer 2: [moduleB, moduleC]
Round 3 — in-degree 0: [app]             →  layer 3: [app]

moduleB and moduleC can be downloaded in parallel.

Complexity: O(V + E) time, O(V) space.

Real-world use: go mod download parallelises fetches this way. CI/CD pipelines (GitHub Actions, Buildkite) use the same idea to run independent jobs concurrently.

---

Project Structure

depgraph/
├── graph.go    — Graph struct, AddPackage, AddDependency
├── kahn.go     — Kahn's BFS topological sort + cycle detection
├── dfs.go      — DFS topological sort + three-color cycle detection
├── layers.go   — Parallel install layers
├── util.go     — Shared helpers (sort, reverse)
└── main.go     — Three teaching scenarios

---

Getting Started

git clone <repo>
cd depgraph
go mod init depgraph
go run .

Expected output:

Scenario 1: multi-layer project
  Kahn  → logger → config → db → http → app
  DFS   → logger → config → db → http → app
  Parallel layers:
    [1] config, logger
    [2] db, http
    [3] app

Scenario 2: circular dependency (A → B → C → A)
  Kahn  → error: circular dependency detected (Kahn)
  DFS   → error: circular dependency: C → A

Scenario 3: diamond dependency
  Kahn  → core → moduleB → moduleC → app
  Parallel layers:
    [1] core
    [2] moduleB, moduleC
    [3] app

---

Scenarios Explained

Scenario 1, Multi-layer project

A realistic Go project where app depends on http and db, both of which share logger as a transitive dependency. The key point: logger appears only once in the install order despite being needed by two packages.

Scenario 2, Circular dependency

A → B → C → A forms a cycle. No valid install order exists. Kahn detects this by noticing not all nodes were processed. DFS detects it by finding a back-edge (C → A while A is still gray). Both approaches agree on the outcome; DFS additionally identifies where the cycle closes.

Scenario 3, Diamond dependency

Two packages share a common base:

app → moduleB → core
app → moduleC → core

core is installed once (layer 1). moduleB and moduleC have no dependency on each other, so they occupy the same layer and can be fetched in parallel.

---

Comparison: Kahn vs DFS

	Kahn's Algorithm	DFS Sort
Approach	BFS, iterative	DFS, recursive
Cycle detection	Implicit — leftover nodes	Explicit — back-edge (gray node)
Cycle location	Not reported	Reports the exact edge
Basis for	Parallel layers	Symbol resolution, scheduling
Intuition	"Process what's ready"	"Finish dependencies before the dependent"

Both algorithms produce a valid topological order. Neither is strictly better — the right choice depends on what additional information you need from the traversal.