Practice: Finding Weak Links in a Delivery Network

One-way streets between depots and two-way roads between towns: find which depots reach each other, and which closure cuts the region.

Choosing a connectivity tool and running it are practised here on a delivery network you have not seen: two questions, each needing a different tool. A courier runs vans between seven depots in a city, along one-way streets, and between seven towns in the region around it, along two-way roads.

The one-way streets run Quay->Mill, Mill->Rail, Rail->Quay, Rail->Park, Park->Yard, Yard->Park, Yard->Dock, Dock->Hill and Hill->Dock.

The two-way roads are Lowick-Morton, Morton-Nesby, Nesby-Lowick, Nesby-Oakham, Oakham-Pitton, Pitton-Rudby, Rudby-Oakham and Rudby-Stow.

Vans swap parcels only between depots that can each reach the other. Which tool finds the groups of depots that can swap, and what are the groups?
The council may close one road, or one town's junction, for repairs. Which tool finds a closure that would cut the region in two, and which roads and towns are they?

Name the tool for each part and find the answers, then compare with the run.

The streets are one-way and the question is about reaching each other, so the tool is strongly connected components. There are three groups: Mill, Quay and Rail, which form a cycle; Park and Yard; and Dock and Hill. Rail->Park leads from the first group to the second, but nothing leads back, so a van at Park can never return to Rail. Union-find would have put all seven depots in one group.
The roads are two-way and the question is about one failure, so the tool is bridges and articulation points. The roads Nesby-Oakham and Rudby-Stow are bridges: Lowick, Morton and Nesby form one triangle, Oakham, Pitton and Rudby another, and only Nesby-Oakham joins them, while Stow hangs off Rudby alone. The junctions at Nesby, Oakham and Rudby are articulation points. Stow is not, since closing it strands nobody else, and neither are Lowick, Morton or Pitton, each of which sits on a triangle with a way round.

The listing below runs both: Kosaraju's two passes on the streets, then one search for low values from Lowick on the roads. It prints Rudby-Stow before Nesby-Oakham because bridges are found as the search backs out, deepest first. A brute-force check that tried every pair of depots and every closure gave the same answers.

weak_links.pypy

STREETS = {
    "Quay": ["Mill"], "Mill": ["Rail"], "Rail": ["Quay", "Park"], "Park": ["Yard"],
    "Yard": ["Park", "Dock"], "Dock": ["Hill"], "Hill": ["Dock"],
}
ROADS = [
    ("Lowick", "Morton"), ("Morton", "Nesby"), ("Nesby", "Lowick"), ("Nesby", "Oakham"),
    ("Oakham", "Pitton"), ("Pitton", "Rudby"), ("Rudby", "Oakham"), ("Rudby", "Stow"),
]


def components(graph):
    visited, order = set(), []

    def finish(vertex):
        visited.add(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                finish(neighbour)
        order.append(vertex)

    for vertex in graph:
        if vertex not in visited:
            finish(vertex)
    flipped = {vertex: [] for vertex in graph}
    for vertex, neighbours in graph.items():
        for neighbour in neighbours:
            flipped[neighbour].append(vertex)
    assigned, groups = set(), []

    def gather(vertex, group):
        assigned.add(vertex)
        group.append(vertex)
        for neighbour in flipped[vertex]:
            if neighbour not in assigned:
                gather(neighbour, group)

    for vertex in reversed(order):
        if vertex not in assigned:
            group = []
            gather(vertex, group)
            groups.append(group)
    return groups


def weak_links(edges):
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)
    discovery, low, bridges, articulation = {}, {}, [], set()

    def visit(vertex, parent):
        discovery[vertex] = low[vertex] = len(discovery)
        children = 0
        for neighbour in graph[vertex]:
            if neighbour == parent:
                continue
            if neighbour in discovery:
                low[vertex] = min(low[vertex], discovery[neighbour])
                continue
            children += 1
            visit(neighbour, vertex)
            low[vertex] = min(low[vertex], low[neighbour])
            if low[neighbour] > discovery[vertex]:
                bridges.append(f"{vertex}-{neighbour}")
            if parent is not None and low[neighbour] >= discovery[vertex]:
                articulation.add(vertex)
        if parent is None and children > 1:
            articulation.add(vertex)

    visit(next(iter(graph)), None)
    return bridges, sorted(articulation)


for group in components(STREETS):
    print("depots that reach each other:", ", ".join(sorted(group)))
bridges, articulation = weak_links(ROADS)
print("roads whose closure cuts the region:", ", ".join(bridges))
print("towns whose closure cuts the region:", ", ".join(articulation))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

depots that reach each other: Mill, Quay, Rail
depots that reach each other: Park, Yard
depots that reach each other: Dock, Hill
roads whose closure cuts the region: Rudby-Stow, Nesby-Oakham
towns whose closure cuts the region: Nesby, Oakham, Rudby

← → move through sections and cards