Graphs (Adjacency Lists, Matrices, and DAGs): Modeling Dependencies, Social Networks, and Workflows

*From git commit to npm install, from Webpack module bundlers to Airflow and GitHub Actions CI/CD pipelines: modern software engineering isn't just built on source code—it is built on Graphs and Directed Acyclic Graphs (DAGs).*

---

In the final third of a university Data Structures and Algorithms course, we lift the single-parent restriction of Trees and enter the most general structure in mathematics and computer science: the Graph $G = (V, E)$.

A Graph consists of a set of Vertices (Nodes) $V$ connected by a set of Edges (Links) $E$:

• In an Undirected Graph, edges are symmetric two-way relationships: {Alice, Bob} in a mutual friendship network or a physical fiber-optic cable between two data centers.
• In a Directed Graph (Digraph), edges are one-way arrows $(u \rightarrow v)$: Module A imports Module B, Task B depends on Task A, or Webpage X links to Webpage Y.
• When a Directed Graph contains zero directed cycles, we call it a DAG (Directed Acyclic Graph)—the mathematical backbone of every build system, package manager, version control system, and workflow orchestrator in existence.

---

1. The Academic Foundation: Adjacency Matrix vs. Adjacency List

Before running a single graph algorithm, every systems architect must answer a foundational memory layout question: How do we represent $G = (V, E)$ in RAM?

Representation 1: Adjacency Matrix ($|V| \times |V|$ 2D Grid)

We allocate a $|V| \times |V|$ table where matrix[u][v] = weight (or 1 if an edge exists, 0 otherwise).

• Pros: Checking if an edge $(u, v)$ exists takes $O(1)$ constant time; matrix operations map directly onto GPU tensor hardware.
• Cons: Consumes $\Theta(|V|^2)$ memory regardless of how few edges actually exist! If a social network has $|V| = 10,000,000$ users and each user has $200$ friends (a Sparse Graph where $|E| \ll |V|^2$), a 10M $\times$ 10M matrix requires $100\text{ Terabytes}$ of RAM just to store mostly zeros!

Representation 2: Adjacency List (Map<Vertex, Edge[]>)

Each vertex $u \in V$ stores a compact dynamic array of only its outgoing edges.

• Pros: Consumes $\Theta(|V| + |E|)$ memory; iterating over all neighbors of $u$ takes $O(\text{degree}(u))$ time instead of scanning $|V|$ columns.
• Cons: Checking if a specific edge $(u, v)$ exists takes $O(\text{degree}(u))$ (or $O(1)$ if each vertex's neighbor list is backed by a hash set).

flowchart LR
    subgraph DAG["Directed Acyclic Graph (Build Pipeline DAG)"]
        direction LR
        Schema["db-schema"] --> API["api-server"]
        Auth["auth-lib"] --> API
        Auth --> UI["web-client"]
        API --> E2E["e2e-tests"]
        UI --> E2E
    end

Complexity Comparison Table

Operation	Adjacency Matrix	Adjacency List	Winner for Sparse Production Graphs
Storage Space	$\Theta(	V	^2)$
Add Vertex	$O(	V	^2)$
Add Edge $(u, v)$	$O(1)$	$O(1)$	Tie
Check Edge $(u, v)$ Exists	$O(1)$	$O(\text{deg}(u))$	Adjacency Matrix
Iterate Neighbors of $u$	$O(	V	)$
Full BFS / DFS Traversal	$O(	V	^2)$

---

2. Two Indispensable Graph Algorithms in Software Engineering

Algorithm 1: Kahn's Topological Sort & Parallel Execution Waves ($O(|V| + |E|)$)

Suppose your monorepo has 50 packages with inter-package dependencies, or your CI/CD pipeline (like the ones discussed in our CI/CD Deep Dive) has 30 build/test stages. In what order can we build them so no package is built before its dependencies—and which packages can be built in parallel at the exact same time?

Kahn's Algorithm computes the in-degree (number of unmet incoming prerequisites) for every node:

1. Enqueue all nodes with inDegree === 0 into Wave 0 (they have zero dependencies and can run in parallel immediately!).
2. Dequeue nodes in the current wave, decrement the inDegree of their dependents, and any dependent whose inDegree hits 0 enters the next parallel execution wave.
3. Automatic Cycle Detection: If the queue empties before all $|V|$ vertices are visited, the remaining vertices contain a Circular Dependency (Cycle)!

flowchart TD
    Init["1. Compute inDegree[v] for all vertices<br/>Enqueue all vertices with inDegree == 0 into Queue"] --> Loop{"2. Is Queue Empty?"}
    Loop -- "No" --> PopWave["Dequeue current parallel wave<br/>Append to topological order"]
    PopWave --> Decrement["For each outgoing edge (u -> v):<br/>Decrement inDegree[v]--<br/>If inDegree[v] == 0, enqueue(v) for next wave"]
    Decrement --> Loop
    Loop -- "Yes" --> CheckCount{"3. Did visitedCount == |V|?"}
    CheckCount -- "Yes" --> Success["Return Valid Topological Order & Parallel Waves"]
    CheckCount -- "No" --> CycleError["Throw Circular Dependency Error!<br/>(Nodes with inDegree > 0 are in/blocked by a cycle)"]

Algorithm 2: Dijkstra's Shortest Path with Path Reconstruction ($O((|V| + |E|) \log |V|)$)

When edges have non-negative weights (network latency in milliseconds, road distance, or cloud routing cost), Dijkstra's Algorithm expands outward from the source vertex greedily by shortest cumulative distance dist[u], relaxing edges via the triangle inequality:

$$\text{if } \text{dist}[u] + w(u, v) < \text{dist}[v] \implies \text{dist}[v] \leftarrow \text{dist}[u] + w(u, v)$$

---

3. Under the Hood: Testable DAG Topological Scheduler & Dijkstra Router

Below is a complete, zero-dependency TypeScript implementation of a Weighted Directed Graph featuring Kahn's Parallel-Wave Topological Sort (with circular dependency detection) and Dijkstra's Shortest Path Router.

Copy and execute this code directly in the JS/TS Playground:

export interface WeightedEdge {
  to: string;
  weight: number;
}

export interface TopologicalPlan {
  hasCycle: boolean;
  orderedNodes: string[];
  parallelWaves: string[][];
  cycleBlockedNodes: string[];
}

export interface ShortestPathResult {
  distance: number;
  path: string[];
}

/**
 * Production Adjacency-List Graph supporting DAG Dependency Scheduling & Shortest Path Routing
 */
class DirectedGraph {
  private readonly adj = new Map<string, WeightedEdge[]>();

  public addVertex(v: string): void {
    if (!this.adj.has(v)) {
      this.adj.set(v, []);
    }
  }

  /**
   * Adds a directed edge u -> v (In dependency terms: u must complete before v)
   */
  public addEdge(from: string, to: string, weight: number = 1): void {
    this.addVertex(from);
    this.addVertex(to);
    this.adj.get(from)!.push({ to, weight });
  }

  /**
   * Kahn's O(V + E) Topological Sort + Parallel Execution Wave Planner + Cycle Detector
   */
  public buildExecutionPlan(): TopologicalPlan {
    const inDegree = new Map<string, number>();
    for (const v of this.adj.keys()) {
      inDegree.set(v, 0);
    }

    for (const edges of this.adj.values()) {
      for (const edge of edges) {
        inDegree.set(edge.to, (inDegree.get(edge.to) ?? 0) + 1);
      }
    }

    let currentWave: string[] = [];
    for (const [v, deg] of inDegree.entries()) {
      if (deg === 0) {
        currentWave.push(v);
      }
    }

    const orderedNodes: string[] = [];
    const parallelWaves: string[][] = [];

    while (currentWave.length > 0) {
      currentWave.sort(); // Deterministic wave ordering
      parallelWaves.push(currentWave);
      const nextWave: string[] = [];

      for (const u of currentWave) {
        orderedNodes.push(u);
        for (const edge of this.adj.get(u) ?? []) {
          const newDeg = inDegree.get(edge.to)! - 1;
          inDegree.set(edge.to, newDeg);
          if (newDeg === 0) {
            nextWave.push(edge.to);
          }
        }
      }
      currentWave = nextWave;
    }

    const hasCycle = orderedNodes.length !== this.adj.size;
    const cycleBlockedNodes: string[] = [];
    if (hasCycle) {
      for (const [v, deg] of inDegree.entries()) {
        if (deg > 0) cycleBlockedNodes.push(v);
      }
    }

    return { hasCycle, orderedNodes, parallelWaves, cycleBlockedNodes };
  }

  /**
   * Dijkstra's Shortest Path Algorithm with Full Route Reconstruction
   */
  public shortestPath(start: string, target: string): ShortestPathResult | null {
    if (!this.adj.has(start) || !this.adj.has(target)) return null;

    const dist = new Map<string, number>();
    const prev = new Map<string, string | null>();
    const visited = new Set<string>();

    for (const v of this.adj.keys()) {
      dist.set(v, Infinity);
      prev.set(v, null);
    }
    dist.set(start, 0);

    // Priority frontier sorted by shortest cumulative distance
    const frontier: Array<{ node: string; cost: number }> = [{ node: start, cost: 0 }];

    while (frontier.length > 0) {
      frontier.sort((a, b) => a.cost - b.cost);
      const { node: u, cost: d } = frontier.shift()!;

      if (visited.has(u)) continue;
      visited.add(u);

      if (u === target) break;

      for (const edge of this.adj.get(u) ?? []) {
        if (edge.weight < 0) {
          throw new Error("Dijkstra requires non-negative edge weights.");
        }
        const alt = d + edge.weight;
        if (alt < dist.get(edge.to)!) {
          dist.set(edge.to, alt);
          prev.set(edge.to, u);
          frontier.push({ node: edge.to, cost: alt });
        }
      }
    }

    const finalDist = dist.get(target)!;
    if (finalDist === Infinity) return null;

    const path: string[] = [];
    let curr: string | null = target;
    while (curr !== null) {
      path.push(curr);
      curr = prev.get(curr) ?? null;
    }
    path.reverse();

    return { distance: finalDist, path };
  }
}

// ============================================================================
// Verification & Execution
// ============================================================================
// 1. Test Monorepo / CI Build DAG Parallel Wave Planner
const buildDag = new DirectedGraph();
buildDag.addEdge("core-types", "auth-sdk");
buildDag.addEdge("core-types", "db-client");
buildDag.addEdge("auth-sdk", "api-gateway");
buildDag.addEdge("db-client", "api-gateway");
buildDag.addEdge("auth-sdk", "web-dashboard");
buildDag.addEdge("api-gateway", "e2e-suite");
buildDag.addEdge("web-dashboard", "e2e-suite");

const plan = buildDag.buildExecutionPlan();
console.log("DAG Has Cycle?:", plan.hasCycle); // false
console.log("Parallel Build Waves:", JSON.stringify(plan.parallelWaves));
// Wave 0: ["core-types"]
// Wave 1: ["auth-sdk", "db-client"] (Can compile concurrently!)
// Wave 2: ["api-gateway", "web-dashboard"] (Can compile concurrently!)
// Wave 3: ["e2e-suite"]

// 2. Test Dijkstra Lowest-Latency Cloud Region Routing (ms)
const network = new DirectedGraph();
network.addEdge("us-west", "us-central", 28);
network.addEdge("us-west", "us-east", 72);
network.addEdge("us-central", "us-east", 31);
network.addEdge("us-central", "eu-west", 110);
network.addEdge("us-east", "eu-west", 64);

const route = network.shortestPath("us-west", "eu-west");
console.log("Optimal Cloud Route (us-west -> eu-west):", JSON.stringify(route));
// Expected: distance = 123ms via ["us-west", "us-central", "us-east", "eu-west"] (28 + 31 + 64 = 123ms)

---

4. Where Graphs & DAGs Live in Modern Production Systems

1. Git Version Control: A Content-Addressable Merkle DAG

As we explore in our Git Workflow Guide, Git is not a sequence of file diffs—it is a Directed Acyclic Graph (DAG) of commit objects identified by SHA-1 / SHA-256 cryptographic hashes (which you can compute in our Hash Generator). Every commit points backward to one parent commit (or two+ parents in a merge commit). Because history never cycles, operations like git merge-base find the Lowest Common Ancestor (LCA) of two branches in milliseconds using graph traversal.

2. Build Systems, Module Bundlers (Vite, Webpack, Turborepo), and Spreadsheet Formulas

When you change a single cell A1 in Excel or Google Sheets, or edit a TypeScript file in Vite, how does the engine know which downstream cells or modules to recompute—and immediately flag #REF! / Circular Dependency Detected if A1 depends on B1 and B1 depends on A1?

It maintains a live Dependency DAG and runs topological sorting and cycle detection (Kahn's algorithm or Tarjan's Strongly Connected Components) on every edit.

3. Garbage Collectors (V8 Mark-and-Sweep Reachability Graph)

How does JavaScript or Java know when an object in heap memory can be safely freed? Modern garbage collectors do not rely solely on reference counting (which leaks memory whenever two objects reference each other in a cycle!). Instead, V8 treats the entire heap as a Directed Graph, starts at the GC Roots (global variables and active call stack frames), and runs a Graph Traversal (Tri-Color Marking BFS/DFS). Any heap object not reachable from the root set is swept away—automatically reclaiming cyclic islands of objects!

---

5. The Professor's Architecture Cheat Sheet

When to Choose Graph / DAG Representations:

• Dependency & Workflow Orchestration: Task schedulers, CI/CD pipelines, database migration runners, and formula evaluation engines.
• Network & Routing Topologies: Finding lowest-latency routes, bottlenecks (Max-Flow Min-Cut), or single points of failure (articulation points/bridges).
• Authorization & Knowledge Graphs (ReBAC): Google Zanzibar-style Relationship-Based Access Control (User -> MemberOf -> Team -> CanEdit -> Document).

When NOT to Choose an Adjacency Matrix:

• Whenever $|V| > 5,000$ and the graph is sparse: Always default to an Adjacency List (Map<NodeId, Edge[]>) so memory scales linearly with $|V| + |E|$ rather than quadratically with $|V|^2$.