Learn · Minimum Cut

Find where the city is easiest to split.

A storm brings down trees, a marathon needs a cordon, roadworks close a bridge. Which few streets, once closed, cut the city in two? This lab finds the minimum cut of a real street network and shows how.

Minimum Cut on a procedurally generated 3D city (seed 256)
Free · in your browser AlgorithmsMin cutStoer–WagnerKargerInteractive

Split the network

  1. Pick a situation

    A storm, a marathon cordon, random damage – or pick two junctions and ask for the cheapest cut between them.

  2. Pick an algorithm

    An s–t cut through maximum flow, Stoer–Wagner for the global cut, Karger's random contractions, or the full Gomory–Hu tree.

  3. Step through it

    Watch junctions merge and phases pass; the two sides of the city colour in as the cut appears.

  4. Try it yourself

    Some situations ask you to close the streets yourself. Closing a min-cut street costs the city exactly its capacity.

Deterministic, randomized and all at once

Stoer–Wagner finds the global minimum cut without any flow, by repeatedly merging the most tightly connected junctions. Karger contracts random streets – usually wrong, but run it enough times and it is right with high probability, which you can watch happen.

The Gomory–Hu tree answers every pair at once: one small tree whose edges hold the minimum cut between any two junctions in the city.

Minimum Cut at a glance

Algorithms
s–t cut, Stoer–Wagner, Karger, Gomory–Hu
Graph
Real streets, weighted by lane capacity both ways
Task mode
Close the cut yourself and compare with the optimum