In-degree & DAG ordering

Overview

A directed acyclic graph (DAG) encodes 'must come before' relationships. The in-degree of a vertex — how many edges point into it, i.e. its matrix column sum — is the key quantity: a vertex with in-degree 0 has no unmet prerequisites. Removing such vertices repeatedly yields a topological order, and dynamic programming over that order gives things like the longest dependency chain.

Why it matters

Topological sorting schedules tasks with dependencies: build systems, course prerequisites, spreadsheet recalculation, package installation. The longest path in the DAG is the critical path — the minimum time to finish everything if independent tasks run in parallel.

Core concepts

In-degree = column sum of the adjacency matrix.

Kahn's algorithm. Repeatedly output a zero-in-degree vertex and 'remove' it (decrement its successors' in-degrees).

Longest path DP. lp(v) = max over edges v→u of 1 + lp(u); memoise so each vertex is solved once. Valid only because a DAG has no cycles to loop the recursion.

Why the ordering makes the DP valid. In topological order every edge points forward, so when a vertex is processed all of its successors are already solved. That is what lets the longest-path recurrence read lp(u) as a finished value rather than a work in progress — and it is why the same DP is meaningless on a cyclic graph.

Syntax notes

/* in-degree = column sum */
int in_degree(const int *adj, int n, int v) {
    int d = 0;
    for (int i = 0; i < n; i++) d += adj[i*n + v];   /* COLUMN v, not row v */
    return d;
}

/* longest path in a DAG, memoised: lp(v) = max over v->u of 1 + lp(u) */
static int lp(const int *adj, int n, int v, int *memo) {
    if (memo[v] >= 0) return memo[v];
    int best = 0;
    for (int u = 0; u < n; u++)
        if (adj[v*n + u]) {
            int cand = 1 + lp(adj, n, u, memo);
            if (cand > best) best = cand;
        }
    return memo[v] = best;
}

Key points:

• In-degree sweeps the column; out-degree sweeps the row. This is the distinction the whole lesson rests on.
• memo must be seeded to -1 (a valid answer is 0, so calloc would be ambiguous).
• lp terminates only because the graph is acyclic — on a cyclic graph it recurses forever.

Lesson

Directed acyclic graphs (DAGs) model dependencies. The in-degree — column sum of the matrix — drives Kahn's topological sort (repeatedly remove a zero-in-degree vertex). Once a DAG is ordered, dynamic programming over it is easy: the longest path from a vertex is 1 plus the best of its successors, memoized so the whole graph is linear.

Code examples

#include <stdio.h> static int n=5, adj[25]={ 0,1,1,0,0, 0,0,0,1,0, 0,0,0,1,0, 0,0,0,0,1, 0,0,0,0,0 }; static int memo[5]; static int lp(int v){ if(memo[v]>=0) return memo[v]; int best=0; for(int u=0;u<n;u++) if(adj[vn+u]){ int c=1+lp(u); if(c>best)best=c; } return memo[v]=best; } int main(void){ for(int v=0;v<n;v++){ int in=0; for(int i=0;i<n;i++) in+=adj[in+v]; printf("vertex %d in-degree=%d\n", v, in); } for(int i=0;i<n;i++) memo[i]=-1; int longest=0; for(int v=0;v<n;v++){ int c=lp(v); if(c>longest)longest=c; } printf("longest path (edges) = %d\n", longest); return 0; }

Line by line

Common mistakes

Summing row v (out-degree) when in-degree (column v) was needed. Running the longest-path DP on a graph with cycles (it never terminates / is undefined). Recomputing sub-results instead of memoising.

Debugging tips

Compiler errors and warnings:

• No warning for summing the wrong direction — in-degree and out-degree are both valid code.
• -Wmaybe-uninitialized if memo is malloced without the -1 fill.

Runtime symptoms:

• In-degree looks like out-degree. You summed adj[v*n + i] (row) instead of adj[i*n + v] (column).
• lp never returns / stack overflow. The graph has a cycle. Longest path is only well defined on a DAG — run cycle detection first.
• All longest paths are 0. The memo was zero-initialised and every lookup hits a phantom cached 0. Seed with -1.
• The answer is the path from vertex 0 only. The result is the maximum of lp(v) over all vertices, since the longest path need not start at 0.
• Kahn's sort emits fewer vertices than n. That is the cycle signal — a correct topological sort of a DAG emits every vertex.

Technique: verify in-degrees sum to the same total as out-degrees (both equal the edge count). If they differ, one of your loops is reading the wrong direction.

Memory safety

• Memo sentinel. 0 is a legitimate longest-path value, so calloc produces silently wrong results. Use malloc plus an explicit -1 fill, or a separate computed[] flag.
• Acyclicity is an unchecked precondition. lp on a cyclic graph recurses until the stack is exhausted — an unrecoverable crash driven purely by input data. Detect cycles first if the graph is untrusted.
• Recursion depth equals the longest path, so deep DAGs need an iterative formulation (process in topological order and relax forward).
• Column sweeps are cache-unfriendly on a row-major matrix: computing all in-degrees with a column loop per vertex touches memory with stride n. Accumulate them in one row-major pass instead when performance matters.
• Validate v before indexing, and free the memo on every path.

Real-world uses

Concrete uses: Build systems order compilation steps; package managers order installs; spreadsheet engines order cell recalculation; task schedulers order jobs with prerequisites. The longest path in a DAG is the critical path — the minimum possible completion time when independent tasks run in parallel — which is the core of project scheduling (PERT/CPM) and of static timing analysis in hardware design.

Professional best practices:

Beginner:

• Write a comment stating whether you need the row or the column before writing the loop.
• Seed memo arrays with a sentinel that cannot be a real answer.

Intermediate:

• Run cycle detection before any DAG algorithm on untrusted input; "longest path" is undefined otherwise (and NP-hard on general graphs).
• Compute all in-degrees in a single pass over the matrix rather than a column sweep per vertex.
• Prefer processing in topological order iteratively over recursive memoisation when depth could be large.

Practice tasks

1. (Beginner) In-degree. Implement int in_degree(const int *adj, int n, int v) by summing the column. Example: vertex 3 in the demo DAG -> 2. Concepts: row vs column.

2. (Beginner) Find the sources. List every vertex with in-degree 0 — the valid starting points for a topological order. Concepts: Kahn's first step.

3. (Intermediate) Longest path. Implement the memoised lp and return the maximum over all vertices. Example: 3 edges in the demo DAG. Concepts: DAG DP, sentinel seeding.

4. (Intermediate) Kahn's topological sort. Emit a full ordering, and detect a cycle by checking that the number of emitted vertices equals n. Concepts: topological ordering, cycle detection as a by-product.

Summary

In-degree is the column sum of the adjacency matrix (out-degree is the row sum), and it is what drives Kahn's topological sort: repeatedly emit a vertex with no unmet prerequisites. Once a DAG is ordered, dynamic programming over it is straightforward — the longest path from a vertex is one plus the best of its successors, memoised so each vertex is solved once. Two preconditions matter: the memo sentinel must not be 0 (a valid answer), and the graph must genuinely be acyclic, since longest-path recursion on a cycle never terminates and the problem is NP-hard on general graphs. If a topological sort emits fewer than n vertices, you have found a cycle.

Practice with these exercises

• In-degree of a vertex
• Longest path in a DAG