Shortest paths: relaxation and DAGs

# A rider's map (made up): one-way roads between five places, weighted by minutes. Breadth-first search finds the
# route with the fewest roads; the route with the fewest minutes can use more roads.
from collections import deque
from itertools import count

roads = [
    ("depot", "market", 9),
    ("depot", "school", 2),
    ("school", "bank", 3),
    ("bank", "market", 2),
    ("school", "park", 4),
    ("park", "market", 4),
]
graph = {}
for u, v, minutes in roads:
    graph.setdefault(u, []).append((v, minutes))
    graph.setdefault(v, [])


def every_route(u, target, route):
    """All routes from u to target that repeat no place (fine for five places, hopeless for five thousand)."""
    if u == target:
        yield route
        return
    for v, _ in graph[u]:
        if v not in route:
            yield from every_route(v, target, route + [v])


def minutes_of(route):
    weight = {(u, v): m for u, v, m in roads}
    return sum(weight[step] for step in zip(route, route[1:]))


def bfs_route(graph, source, target):
    """Breadth-first search with parent pointers: the route with the fewest edges."""
    parent = {source: None}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v, _ in graph[u]:
            if v not in parent:
                parent[v] = u
                queue.append(v)
    route = [target]
    while parent[route[-1]] is not None:
        route.append(parent[route[-1]])
    return route[::-1]


print("every route from the depot to the market:")
routes = list(every_route("depot", "market", ["depot"]))
for route in routes:
    print(f"  {' -> '.join(route):34} {len(route) - 1} road{'s' if len(route) > 2 else ' '}  {minutes_of(route):2} min")
fewest = bfs_route(graph, "depot", "market")
best = min(routes, key=minutes_of)
print(f"BFS, fewest roads: {' -> '.join(fewest)}, {minutes_of(fewest)} min")
print(f"fewest minutes:    {' -> '.join(best)}, {minutes_of(best)} min")

# The repair that works only for small whole-number weights: cut every road into 1-minute pieces, then run BFS.
fresh = count()
pieces = {place: [] for place in graph}
for u, v, minutes in roads:
    previous = u
    for _ in range(minutes - 1):
        stop = f"piece {next(fresh)}"
        pieces[stop] = []
        pieces[previous].append((stop, 1))
        previous = stop
    pieces[previous].append((v, 1))
cut = bfs_route(pieces, "depot", "market")
edges = sum(len(out) for out in pieces.values())
print(f"cut into 1-minute pieces: {len(pieces)} vertices and {edges} edges instead of {len(graph)} and {len(roads)};"
      f" BFS now needs {len(cut) - 1} steps, the {minutes_of(best)} minutes")

every route from the depot to the market:
  depot -> market                    1 road    9 min
  depot -> school -> bank -> market  3 roads   7 min
  depot -> school -> park -> market  3 roads  10 min
BFS, fewest roads: depot -> market, 9 min
fewest minutes:    depot -> school -> bank -> market, 7 min
cut into 1-minute pieces: 23 vertices and 24 edges instead of 5 and 6; BFS now needs 7 steps, the 7 minutes

# Relaxation, one edge at a time, on a small directed graph. Every shortest-path algorithm of this module is this
# step repeated; they differ only in the order in which they pick the edges.
import math

edges = [("s", "a", 4), ("s", "b", 1), ("b", "a", 2), ("a", "c", 1), ("b", "c", 5), ("c", "d", 3)]


def show(x):
    return "inf" if x == math.inf else str(x)


def relax(dist, parent, u, v, w, log):
    """If going through u makes v cheaper, remember the cheaper distance and the edge that gave it."""
    if dist[u] + w < dist[v]:
        log.append(f"  relax {u} -> {v} ({w}): {show(dist[u])} + {w} = {dist[u] + w} < {show(dist[v])}, so dist[{v}] = {dist[u] + w}")
        dist[v] = dist[u] + w
        parent[v] = u
        return True
    log.append(f"  relax {u} -> {v} ({w}): {show(dist[u])} + {w} is not below {show(dist[v])}, no change")
    return False


def run(order, passes):
    dist = {v: math.inf for v in "sabcd"}
    parent = {v: None for v in "sabcd"}
    dist["s"] = 0
    relaxations = 0
    for p in range(1, passes + 1):
        log = []
        changed = False
        for u, v, w in order:
            changed |= relax(dist, parent, u, v, w, log)
            relaxations += 1
        if not changed:
            print(f" pass {p}: none of the {len(order)} edges changes anything, so the distances are final")
            break
        print(f" pass {p}:", *log, sep="\n")
    print(f" {relaxations} relaxations; dist: " + ", ".join(f"{v} {show(d)}" for v, d in dist.items()))
    route = ["d"]
    while parent[route[-1]] is not None:
        route.append(parent[route[-1]])
    print(f" shortest path to d, read back through the parents: {' -> '.join(reversed(route))}")


print("Order 1: the edges in an unlucky order, repeated until a pass changes nothing")
unlucky = [edges[i] for i in (3, 5, 0, 1, 2, 4)]
run(unlucky, passes=10)
print()
print("Order 2: the edges leaving s, then b, a, c (a topological order), one pass")
by_vertex = sorted(edges, key=lambda e: "sbacd".index(e[0]))
run(by_vertex, passes=1)

Order 1: the edges in an unlucky order, repeated until a pass changes nothing
 pass 1:
  relax a -> c (1): inf + 1 is not below inf, no change
  relax c -> d (3): inf + 3 is not below inf, no change
  relax s -> a (4): 0 + 4 = 4 < inf, so dist[a] = 4
  relax s -> b (1): 0 + 1 = 1 < inf, so dist[b] = 1
  relax b -> a (2): 1 + 2 = 3 < 4, so dist[a] = 3
  relax b -> c (5): 1 + 5 = 6 < inf, so dist[c] = 6
 pass 2:
  relax a -> c (1): 3 + 1 = 4 < 6, so dist[c] = 4
  relax c -> d (3): 4 + 3 = 7 < inf, so dist[d] = 7
  relax s -> a (4): 0 + 4 is not below 3, no change
  relax s -> b (1): 0 + 1 is not below 1, no change
  relax b -> a (2): 1 + 2 is not below 3, no change
  relax b -> c (5): 1 + 5 is not below 4, no change
 pass 3: none of the 6 edges changes anything, so the distances are final
 18 relaxations; dist: s 0, a 3, b 1, c 4, d 7
 shortest path to d, read back through the parents: s -> b -> a -> c -> d

Order 2: the edges leaving s, then b, a, c (a topological order), one pass
 pass 1:
  relax s -> a (4): 0 + 4 = 4 < inf, so dist[a] = 4
  relax s -> b (1): 0 + 1 = 1 < inf, so dist[b] = 1
  relax b -> a (2): 1 + 2 = 3 < 4, so dist[a] = 3
  relax b -> c (5): 1 + 5 = 6 < inf, so dist[c] = 6
  relax a -> c (1): 3 + 1 = 4 < 6, so dist[c] = 4
  relax c -> d (3): 4 + 3 = 7 < inf, so dist[d] = 7
 6 relaxations; dist: s 0, a 3, b 1, c 4, d 7
 shortest path to d, read back through the parents: s -> b -> a -> c -> d

# What a negative cycle does to "shortest". The cycle a -> b -> c -> a weighs 2 + (-4) + 1 = -1, so every lap
# around it lowers the cost of reaching a, b, c and t by 1, and relaxation never settles.
import math


def rounds(vertices, edges, source, count):
    """Relaxes every edge `count` times and prints the distances after each round."""
    dist = {v: math.inf for v in vertices}
    dist[source] = 0
    print("round " + "".join(f"{v:>6}" for v in vertices))
    for r in range(1, count + 1):
        changed = 0
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed += 1
        row = "".join(f"{'inf' if d == math.inf else d:>6}" for d in dist.values())
        print(f"{r:>5} {row}   ({changed} changed)")


vertices = ["s", "a", "b", "c", "t"]
cycle = [("a", "b", 2), ("b", "c", -4), ("c", "a", 1)]
print("1. The cycle can be reached from s (edge s -> a):")
rounds(vertices, [("s", "a", 1), *cycle, ("c", "t", 3)], "s", 8)
print()
print("2. The same cycle, but s has no edge into it (s -> t only, and c -> t):")
rounds(vertices, [("s", "t", 5), *cycle, ("c", "t", 3)], "s", 3)

1. The cycle can be reached from s (edge s -> a):
round      s     a     b     c     t
    1      0     0     3    -1     2   (5 changed)
    2      0    -1     2    -2     1   (4 changed)
    3      0    -2     1    -3     0   (4 changed)
    4      0    -3     0    -4    -1   (4 changed)
    5      0    -4    -1    -5    -2   (4 changed)
    6      0    -5    -2    -6    -3   (4 changed)
    7      0    -6    -3    -7    -4   (4 changed)
    8      0    -7    -4    -8    -5   (4 changed)

2. The same cycle, but s has no edge into it (s -> t only, and c -> t):
round      s     a     b     c     t
    1      0   inf   inf   inf     5   (1 changed)
    2      0   inf   inf   inf     5   (0 changed)
    3      0   inf   inf   inf     5   (0 changed)

# One random DAG, three orders of relaxing its edges. Each order ends with the same distances; the work differs.
import math
import random
from collections import deque

rng = random.Random(12)
V, E = 1_000, 6_000
rank = list(range(V))
rng.shuffle(rank)  # rank[v]: v's place in a hidden order; every edge goes from a lower rank to a higher one
by_rank = sorted(range(V), key=rank.__getitem__)
source = by_rank[0]
pairs = set()
for r in range(1, V):  # one edge into every vertex from an earlier one, so all of them can be reached
    pairs.add((by_rank[rng.randrange(r)], by_rank[r]))
while len(pairs) < E:
    a, b = sorted(rng.sample(range(V), 2))
    pairs.add((by_rank[a], by_rank[b]))
edges = [(u, v, rng.randint(-10, 100)) for u, v in sorted(pairs)]  # sorted: a set's order differs between builds
rng.shuffle(edges)


def topological_order():
    out = [[] for _ in range(V)]
    indegree = [0] * V
    for u, v, _ in edges:
        out[u].append(v)
        indegree[v] += 1
    ready = deque(v for v in range(V) if indegree[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in out[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)
    return order


def relax_in_passes(edge_order, max_passes):
    """Relaxes the edges in this order, pass after pass, until a pass lowers nothing (or max_passes)."""
    dist = [math.inf] * V
    dist[source] = 0
    passes = relaxed = 0
    while passes < max_passes:
        passes += 1
        changed = False
        for u, v, w in edge_order:
            relaxed += 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    return dist, passes, relaxed


order = topological_order()
position = {v: i for i, v in enumerate(order)}
by_tail = sorted(edges, key=lambda e: position[e[0]])
runs = {
    "topological order, one pass": relax_in_passes(by_tail, 1),
    "input order, until a pass is quiet": relax_in_passes(edges, V),
    "reverse topological order, likewise": relax_in_passes(by_tail[::-1], V),
}
print(f"a random DAG: {V:,} vertices, {E:,} edges, weights from -10 to 100")
print(f"{'order of the relaxations':37} {'passes':>6} {'relaxations':>12}")
for name, (_, passes, relaxed) in runs.items():
    print(f"{name:37} {passes:>6} {relaxed:>12,}")
answers = [run[0] for run in runs.values()]
print(f"all three agree on every distance: {answers[0] == answers[1] == answers[2]}")

# Why the last order needs so many passes: each pass carries a distance only one edge further along a path.
# hops[v]: the fewest edges on any shortest path to v, filled in topological order.
dist = answers[0]
hops = [math.inf] * V
hops[source] = 0
for u, v, w in by_tail:
    if dist[u] + w == dist[v]:
        hops[v] = min(hops[v], hops[u] + 1)
print(f"some vertex needs {max(hops)} edges on its shortest path: {max(hops)} passes, then one quiet pass")

a random DAG: 1,000 vertices, 6,000 edges, weights from -10 to 100
order of the relaxations              passes  relaxations
topological order, one pass                1        6,000
input order, until a pass is quiet         7       42,000
reverse topological order, likewise       10       60,000
all three agree on every distance: True
some vertex needs 9 edges on its shortest path: 9 passes, then one quiet pass

# The critical path of a wedding plan (tasks and durations made up). Each task can start only when its prerequisites
# are done, so the earliest start of a task is the LONGEST path to it: relaxation with max instead of min, in
# topological order. graphlib.TopologicalSorter (standard library) supplies the order and refuses a cycle.
from graphlib import TopologicalSorter

tasks = {  # task: (days, prerequisites)
    "fix the date": (2, []),
    "book the venue": (7, ["fix the date"]),
    "draw up the guest list": (5, ["fix the date"]),
    "book the caterer": (4, ["book the venue"]),
    "print the invitations": (6, ["book the venue", "draw up the guest list"]),
    "send the invitations": (3, ["print the invitations"]),
    "choose the outfits": (4, ["fix the date"]),
    "tailoring and fittings": (15, ["choose the outfits"]),
    "decorate the venue": (2, ["book the venue"]),
    "mehendi and sangeet": (2, ["tailoring and fittings", "send the invitations"]),
    "wedding day": (1, ["mehendi and sangeet", "book the caterer", "decorate the venue"]),
}
days = {t: d for t, (d, _) in tasks.items()}
after = {t: [] for t in tasks}
for t, (_, before) in tasks.items():
    for p in before:
        after[p].append(t)
order = list(TopologicalSorter({t: before for t, (_, before) in tasks.items()}).static_order())

# Forward pass: relax each edge t -> s with "can s start later?", the longest-path version of relaxation.
start = {t: 0 for t in tasks}
waits_for = {t: None for t in tasks}
for t in order:
    for s in after[t]:
        if start[t] + days[t] > start[s]:
            start[s] = start[t] + days[t]
            waits_for[s] = t
finish = max(start[t] + days[t] for t in tasks)

# Backward pass, in reverse topological order: the latest start that still finishes everything on time.
latest = {}
for t in reversed(order):
    latest[t] = min([latest[s] for s in after[t]], default=finish) - days[t]

print(f"{'task':24} {'days':>4} {'earliest':>9} {'latest':>7} {'slack':>6}")
for t in order:
    slack = latest[t] - start[t]
    print(f"{t:24} {days[t]:>4} {start[t]:>9} {latest[t]:>7} {slack:>6}{'  critical' if slack == 0 else ''}")
path = ["wedding day"]
while waits_for[path[-1]] is not None:
    path.append(waits_for[path[-1]])
print(f"everything is done after {finish} days, the length of the longest path")
print("critical path:", " -> ".join(reversed(path)))

task                     days  earliest  latest  slack
fix the date                2         0       0      0  critical
book the venue              7         2       5      3
draw up the guest list      5         2       7      5
choose the outfits          4         2       2      0  critical
book the caterer            4         9      19     10
decorate the venue          2         9      21     12
print the invitations       6         9      12      3
tailoring and fittings     15         6       6      0  critical
send the invitations        3        15      18      3
mehendi and sangeet         2        21      21      0  critical
wedding day                 1        23      23      0  critical
everything is done after 24 days, the length of the longest path
critical path: fix the date -> choose the outfits -> tailoring and fittings -> mehendi and sangeet -> wedding day