Topological sort

You cannot place beams before the columns are up, and you cannot fabricate steel before it is ordered. Given a list of “X before Y” rules, a topological order is a sequence of all tasks where every task comes after everything it depends on. The same problem appears in build systems (which project to compile first), package managers, course prerequisites and spreadsheet recalculation.

A topological order exists only if there is no cycle. The graph must be a DAG (directed acyclic graph). There are usually several valid orders.

Kahn’s algorithm

1. Count each vertex’s in-degree: how many prerequisites it has.
2. Put every vertex with in-degree 0 in a queue: they can start now.
3. Take one from the queue and add it to the order. For each vertex that depended on it, subtract 1 from its in-degree; if that reaches 0, put it in the queue.
4. When the queue is empty: if every vertex is in the order, done. Otherwise the leftovers are stuck in a cycle.

1string[] tasks = { "Survey", "Excavate", "Footings", "Order steel", "Fabricate", "Columns", "Beams", "Deck", "Roof" };2(string Before, string After)[] deps =3{4    ("Survey", "Excavate"), ("Excavate", "Footings"), ("Footings", "Columns"),5    ("Order steel", "Fabricate"), ("Fabricate", "Columns"), ("Fabricate", "Beams"),6    ("Columns", "Beams"), ("Beams", "Deck"), ("Deck", "Roof")7};8 9var plan = TopoSort(tasks, deps);10Console.WriteLine(plan is null ? "Cycle: no valid order" : string.Join(" → ", plan));11 12static List<string>? TopoSort(string[] nodes, (string Before, string After)[] edges)13{14    var next = nodes.ToDictionary(n => n, _ => new List<string>());15    var inDegree = nodes.ToDictionary(n => n, _ => 0);16    foreach (var (a, b) in edges) { next[a].Add(b); inDegree[b]++; }17 18    var ready = new Queue<string>(nodes.Where(n => inDegree[n] == 0));19    var order = new List<string>();20    while (ready.Count > 0)21    {22        var u = ready.Dequeue();23        order.Add(u);24        foreach (var v in next[u])25            if (--inDegree[v] == 0) ready.Enqueue(v);   // its last prerequisite is done26    }27    return order.Count == nodes.Length ? order : null;  // leftovers mean a cycle28}

Survey → Order steel → Excavate → Fabricate → Footings → Columns → Beams → Deck → Roof

Every vertex is queued once and every edge decreases one counter once: O(V + E). Using a PriorityQueue instead of a Queue gives a specific order among tasks that are ready at the same time (for example alphabetical, or by priority), at O(log V) extra per step.

The DFS method

Run DFS; when a vertex finishes (all its dependants explored), add it to a list. Every task finishes after all tasks that depend on it, so the reversed finish order is a topological order. Combined with the “on the current path” check from the last lesson, it reports cycles too.

1var next = new Dictionary<string, string[]>2{3    ["Underwear"] = new[] { "Trousers" },4    ["Socks"] = new[] { "Boots" },5    ["Trousers"] = new[] { "Boots", "Belt" },6    ["Shirt"] = new[] { "Belt" },7    ["Belt"] = Array.Empty<string>(),8    ["Boots"] = Array.Empty<string>()9};10 11var done = new HashSet<string>();12var finished = new List<string>();13foreach (var task in next.Keys) Visit(task);14finished.Reverse();15Console.WriteLine(string.Join(", ", finished));16 17void Visit(string u)18{19    if (!done.Add(u)) return;20    foreach (var v in next[u]) Visit(v);21    finished.Add(u);                       // u finishes after everything that needs it22}

Shirt, Socks, Underwear, Trousers, Belt, Boots

Scheduling: the critical path

With durations, a topological order also tells you how long the whole project takes. Process tasks in order; each task can start when its latest prerequisite finishes. The longest chain of dependent tasks is the critical path: any delay on it delays the whole project. This is the CPM method used in construction planning, and it is just “longest path in a DAG”, which is easy once the vertices are in topological order (on a general graph, longest path is a very hard problem).

1string[] tasks = { "Survey", "Excavate", "Footings", "Order steel", "Fabricate", "Columns", "Beams", "Deck", "Roof" };2int[] days = { 2, 5, 4, 10, 6, 3, 4, 3, 2 };3(string Before, string After)[] deps =4{5    ("Survey", "Excavate"), ("Excavate", "Footings"), ("Footings", "Columns"),6    ("Order steel", "Fabricate"), ("Fabricate", "Columns"), ("Fabricate", "Beams"),7    ("Columns", "Beams"), ("Beams", "Deck"), ("Deck", "Roof")8};9 10var duration = tasks.Zip(days).ToDictionary(p => p.First, p => p.Second);11var inDegree = tasks.ToDictionary(t => t, _ => 0);12var next = tasks.ToDictionary(t => t, _ => new List<string>());13foreach (var (a, b) in deps) { next[a].Add(b); inDegree[b]++; }14 15var finish = tasks.ToDictionary(t => t, _ => 0);16var start = tasks.ToDictionary(t => t, _ => 0);        // earliest start17var ready = new Queue<string>(tasks.Where(t => inDegree[t] == 0));18while (ready.Count > 0)19{20    var u = ready.Dequeue();21    finish[u] = start[u] + duration[u];22    foreach (var v in next[u])23    {24        start[v] = Math.Max(start[v], finish[u]);      // wait for the latest prerequisite25        if (--inDegree[v] == 0) ready.Enqueue(v);26    }27}28 29Console.WriteLine($"Project: {finish.Values.Max()} days");30Console.WriteLine($"Columns can start on day {start["Columns"]}");

Project: 28 days
Columns can start on day 16