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.
How it works
Split the network
-
Pick a situation
A storm, a marathon cordon, random damage – or pick two junctions and ask for the cheapest cut between them.
-
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.
-
Step through it
Watch junctions merge and phases pass; the two sides of the city colour in as the cut appears.
-
Try it yourself
Some situations ask you to close the streets yourself. Closing a min-cut street costs the city exactly its capacity.
What you learn
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
Keep exploring
More to try
-
Learn
Pathfinding Visualizer
Explore how classic graph algorithms navigate a real Procedity city.
-
Learn
Spanning Trees
Link every junction with the least street – Kruskal, Jarník, Borůvka and Edmonds step by step on a real neighbourhood.
-
Learn
Maximum Flow
How many cars an hour get across town? Watch Ford–Fulkerson, Edmonds–Karp, Dinic and MPM fill the streets.
-
Game
Find the car
One car in town has a colour no other car has. Spot it in traffic as fast as you can.