Unit 10: One Way Only

Some things have to happen before others

Socks before shoes. Flour before cake. Each rule is a one-way arrow, and what you want is an order that breaks none of them — a topological order.

It only exists if the arrows never lead back to where they started. A graph with no way back is a DAG.

Count how many arrows point at each job

A job with nothing pointing at it can be done now. Do it, and take one arrow away from everything it pointed at — anything that drops to zero can be done next.

That is Kahn's algorithm: a queue of jobs that are ready.

Python

from collections import deque

n = 6
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (2, 5)]

adj = [[] for i in range(n)]
indeg = [0] * n
for a, b in edges:
    adj[a].append(b)
    indeg[b] += 1

print(indeg)

queue = deque([i for i in range(n) if indeg[i] == 0])
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for nxt in adj[node]:
        indeg[nxt] -= 1
        if indeg[nxt] == 0:
            queue.append(nxt)

print(order)

It prints

[0, 1, 1, 2, 1, 1]
[0, 1, 2, 3, 5, 4]

There is usually more than one right order

Here 5 came out before 4, and swapping them would have been just as correct — nothing points from one to the other.

A problem that wants a specific one usually says "the alphabetically first", which means a heap instead of a queue. Read the question.

And it finds a loop for free

If the order comes out with fewer than n jobs in it, the ones missing are stuck waiting for each other — a cycle, and no order exists.

Add one arrow back from 3 to 0 and only two jobs ever become ready.

Python

from collections import deque

n = 6
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (2, 5), (3, 0)]

adj = [[] for i in range(n)]
indeg = [0] * n
for a, b in edges:
    adj[a].append(b)
    indeg[b] += 1

queue = deque([i for i in range(n) if indeg[i] == 0])
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for nxt in adj[node]:
        indeg[nxt] -= 1
        if indeg[nxt] == 0:
            queue.append(nxt)

print(order, len(order) == n)

It prints

[] False

A DAG is a dynamic programming problem in disguise

In topological order, every arrow points from a node you have already finished to one you have not. So you can fill in an answer for each node in that order and never look back.

That is exactly what unit 7 did with amounts of money. The order is the only new part.

How many routes are there from 0 to 4?

One route reaches node 0. Every node then hands its count on to everything it points at.

Node 3 collects 1 from node 1 and 1 from node 2, so it has 2 — and node 4 inherits both.

Python

n = 6
adj = [[1, 2], [3], [3, 5], [4], [], []]
order = [0, 1, 2, 3, 5, 4]

ways = [0] * n
ways[0] = 1
for node in order:
    for nxt in adj[node]:
        ways[nxt] += ways[node]

print(ways)

It prints

[1, 1, 1, 2, 2, 1]

The longest route is the same loop with a max

Swap the += for a max and you get the longest chain of arrows ending at each node. Node 4 is 3 arrows deep.

Longest path is hopeless in a general graph — a cycle makes it infinite — but on a DAG it is four lines.

Python

n = 6
adj = [[1, 2], [3], [3, 5], [4], [], []]
order = [0, 1, 2, 3, 5, 4]

longest = [0] * n
for node in order:
    for nxt in adj[node]:
        longest[nxt] = max(longest[nxt], longest[node] + 1)

print(longest)
print(max(longest))

It prints

[0, 1, 1, 2, 3, 2]
3

Why the order is doing all the work

Take the nodes in any other order and a node may be handed a number after it has already passed its own on. The answer is then quietly too small, on some graphs only.

So: topological sort first, always, and never for node in range(n).

Every node points at exactly one other

A successor graph: each node has one way out. A game where each square sends you to another square, a function applied over and over, a chain of "who do you report to".

Walking a million steps one at a time costs a million. There is a way to do it in twenty.

Store the answer for 1, 2, 4, 8… steps

If you know where two steps take you, then four steps is "two steps, then two steps again". Each table is built from the one before it by looking itself up.

This is binary lifting, and it is worth recognising anywhere: doubling turns walking into jumping.

Python

succ = [1, 2, 3, 4, 5, 3]
n = 6
levels = 4

up = [succ[:]]
for k in range(1, levels):
    prev = up[-1]
    up.append([prev[prev[i]] for i in range(n)])

for k in range(levels):
    print(2 ** k, up[k])

It prints

1 [1, 2, 3, 4, 5, 3]
2 [2, 3, 4, 5, 3, 4]
4 [4, 5, 3, 4, 5, 3]
8 [5, 3, 4, 5, 3, 4]

Any number of steps is a handful of jumps

Write the number of steps in binary — unit 3 again. 11 is 8 + 2 + 1, so take the 8-jump, then the 2-jump, then the 1-jump.

A million steps is at most twenty jumps, because a million has twenty bits.

Python

succ = [1, 2, 3, 4, 5, 3]
n = 6
up = [succ[:]]
for k in range(1, 6):
    prev = up[-1]
    up.append([prev[prev[i]] for i in range(n)])

def jump(node, steps):
    k = 0
    while steps > 0:
        if steps & 1:
            node = up[k][node]
        steps >>= 1
        k += 1
    return node

print(jump(0, 1), jump(0, 5), jump(0, 8), jump(0, 11))

It prints

1 5 5 5

Why the answers stop changing

This graph ends in a loop: 3 to 4 to 5 to 3. Once you are on it you go round for ever, so the answer for lots of different step counts is the same handful of nodes.

That loop is what the next unit is about — finding it, and finding where it starts.

Six jobs, each taking time, some waiting on others

Job 0 takes 3 hours, job 1 takes 2, job 2 takes 4, job 3 takes 1, job 4 takes 2, job 5 takes 5. The same arrows as before say what must finish first.

With unlimited workers, when is everything done? Not the sum of the times — jobs that do not wait for each other run together.

Each job starts when its last dependency ends

Walk the topological order. When a job finishes, push its finishing time onto everything waiting on it, keeping the latest — a job cannot start until all of them are done.

The answer is the biggest finishing time of all.

Python

n = 6
adj = [[1, 2], [3], [3, 5], [4], [], []]
order = [0, 1, 2, 3, 5, 4]
dur = [3, 2, 4, 1, 2, 5]

start = [0] * n
for node in order:
    for nxt in adj[node]:
        start[nxt] = max(start[nxt], start[node] + dur[node])

print(start)
print(max(start[i] + dur[i] for i in range(n)))

It prints

[0, 3, 3, 7, 8, 7]
12

Twelve hours, and seventeen hours of work

The jobs add up to 17 hours, and it is all over in 12, because jobs 1 and 2 happen at the same time and so do 4 and 5.

The chain that decides the 12 — job 0, job 2, job 5 — is the critical path. Speeding up anything else changes nothing at all.

This is the longest path with weights

Lesson 2 counted arrows; this counts hours, and it is the same loop with + 1 replaced by + dur[node].

One recipe, three questions — how many routes, how many arrows, how many hours — and the whole difference is the operator in the middle.