Max flow and min cut.

// Edmonds–Karp max flow over a small directed capacity network.
export const MAX_NODES = 32;
export const MAX_EDGES = 128;
export const MAX_CAPACITY = 1_000;

export type Edge = { from: string; to: string; capacity: number };
export type Network = { nodes: string[]; edges: Edge[] };
export type FlowErrorCode =
	| 'too-big'
	| 'bad-node'
	| 'duplicate-node'
	| 'unknown-node'
	| 'self-edge'
	| 'duplicate-edge'
	| 'opposite-edge'
	| 'bad-capacity'
	| 'bad-terminal';

export class FlowError extends Error {
	readonly code: FlowErrorCode;
	constructor(code: FlowErrorCode, message: string) {
		super(message);
		this.name = 'FlowError';
		this.code = code;
	}
}

export type Pair = { from: string; to: string };
// cancels lists original edges this path runs backwards along, undoing earlier flow.
export type Augmentation = { path: string[]; bottleneck: number; total: number; cancels: Pair[] };
export type Residual = Map<string, Map<string, number>>;
export type Augmented = {
	value: number;
	paths: Augmentation[];
	adjacency: Map<string, string[]>;
	residual: Residual;
};

function validate(network: Network, source: string, sink: string) {
	if (network.nodes.length > MAX_NODES || network.edges.length > MAX_EDGES)
		throw new FlowError('too-big', `up to ${MAX_NODES} nodes and ${MAX_EDGES} edges`);
	const nodes = new Set<string>();
	for (const node of network.nodes) {
		if (!/^[a-z][a-z0-9-]{0,23}$/.test(node))
			throw new FlowError('bad-node', `node ids are lowercase slugs: ${node}`);
		if (nodes.has(node)) throw new FlowError('duplicate-node', `node appears twice: ${node}`);
		nodes.add(node);
	}
	if (!nodes.has(source) || !nodes.has(sink))
		throw new FlowError('unknown-node', 'source and sink must be known nodes');
	if (source === sink) throw new FlowError('bad-terminal', 'source and sink must differ');
	const pairs = new Set<string>();
	for (const edge of network.edges) {
		if (!nodes.has(edge.from) || !nodes.has(edge.to))
			throw new FlowError(
				'unknown-node',
				`edge has an unknown endpoint: ${edge.from} → ${edge.to}`
			);
		if (edge.from === edge.to) throw new FlowError('self-edge', `edge loops at ${edge.from}`);
		if (!Number.isInteger(edge.capacity) || edge.capacity < 0 || edge.capacity > MAX_CAPACITY)
			throw new FlowError('bad-capacity', `capacities are whole numbers from 0 to ${MAX_CAPACITY}`);
		const pair = `${edge.from}\0${edge.to}`;
		const reverse = `${edge.to}\0${edge.from}`;
		if (pairs.has(pair))
			throw new FlowError('duplicate-edge', `edge appears twice: ${edge.from} → ${edge.to}`);
		if (pairs.has(reverse))
			throw new FlowError(
				'opposite-edge',
				`use one directed edge per pair: ${edge.from} → ${edge.to}`
			);
		pairs.add(pair);
	}
}

function neighbours(network: Network) {
	const result = new Map<string, string[]>();
	for (const node of network.nodes) result.set(node, []);
	for (const edge of network.edges) {
		result.get(edge.from)!.push(edge.to);
		result.get(edge.to)!.push(edge.from);
	}
	return result;
}

// Every original edge starts with its full capacity forward and 0 backward.
function residualMap(network: Network): Residual {
	const residual: Residual = new Map();
	for (const node of network.nodes) residual.set(node, new Map());
	for (const edge of network.edges) {
		residual.get(edge.from)!.set(edge.to, edge.capacity);
		residual.get(edge.to)!.set(edge.from, 0);
	}
	return residual;
}

// Breadth-first search over edges that still have residual capacity: the shortest route.
function findPath(
	adjacency: Map<string, string[]>,
	residual: Residual,
	source: string,
	sink: string
) {
	const parent = new Map<string, string | null>([[source, null]]);
	const queue = [source];
	for (let head = 0; head < queue.length && !parent.has(sink); head++) {
		const from = queue[head];
		for (const to of adjacency.get(from)!) {
			if (residual.get(from)!.get(to)! <= 0 || parent.has(to)) continue;
			parent.set(to, from);
			queue.push(to);
			if (to === sink) break;
		}
	}
	if (!parent.has(sink)) return null;
	const path: string[] = [];
	for (let at: string | null = sink; at !== null; at = parent.get(at)!) path.push(at);
	path.reverse();
	return path;
}

// Edmonds–Karp: send each shortest path's bottleneck until the sink is unreachable.
export function augment(network: Network, source: string, sink: string): Augmented {
	validate(network, source, sink);
	const adjacency = neighbours(network);
	const residual = residualMap(network);
	const original = new Set(network.edges.map((edge) => `${edge.from}\0${edge.to}`));
	const paths: Augmentation[] = [];
	let value = 0;
	while (true) {
		const path = findPath(adjacency, residual, source, sink);
		if (!path) break;
		let bottleneck = Infinity;
		for (let i = 0; i < path.length - 1; i++)
			bottleneck = Math.min(bottleneck, residual.get(path[i])!.get(path[i + 1])!);
		const cancels: Pair[] = [];
		for (let i = 0; i < path.length - 1; i++) {
			const from = path[i];
			const to = path[i + 1];
			// Sending forward uses up capacity and leaves the same amount to take back later.
			residual.get(from)!.set(to, residual.get(from)!.get(to)! - bottleneck);
			residual.get(to)!.set(from, residual.get(to)!.get(from)! + bottleneck);
			if (!original.has(`${from}\0${to}`)) cancels.push({ from: to, to: from });
		}
		value += bottleneck;
		paths.push({ path, bottleneck, total: value, cancels });
	}
	return { value, paths, adjacency, residual };
}

// Edmonds–Karp max flow over a small directed capacity network.
const (
	MaxNodes    = 32
	MaxEdges    = 128
	MaxCapacity = 1000
)

type Edge struct {
	From, To string
	Capacity int
}
type Network struct {
	Nodes []string
	Edges []Edge
}
type FlowError struct{ Code, Message string }

func (e *FlowError) Error() string { return e.Message }

type Pair struct{ From, To string }

// Cancels lists original edges this path runs backwards along, undoing earlier flow.
type Augmentation struct {
	Path              []string
	Bottleneck, Total int
	Cancels           []Pair
}
type Residual map[string]map[string]int
type Augmented struct {
	Value     int
	Paths     []Augmentation
	Adjacency map[string][]string
	Residual  Residual
}

var nodePattern = regexp.MustCompile(`^[a-z][a-z0-9-]{0,23}$`)

func validate(network Network, source, sink string) error {
	if len(network.Nodes) > MaxNodes || len(network.Edges) > MaxEdges {
		return &FlowError{"too-big", fmt.Sprintf("up to %d nodes and %d edges", MaxNodes, MaxEdges)}
	}
	nodes := map[string]bool{}
	for _, node := range network.Nodes {
		if !nodePattern.MatchString(node) {
			return &FlowError{"bad-node", "node ids are lowercase slugs: " + node}
		}
		if nodes[node] {
			return &FlowError{"duplicate-node", "node appears twice: " + node}
		}
		nodes[node] = true
	}
	if !nodes[source] || !nodes[sink] {
		return &FlowError{"unknown-node", "source and sink must be known nodes"}
	}
	if source == sink {
		return &FlowError{"bad-terminal", "source and sink must differ"}
	}
	pairs := map[string]bool{}
	for _, edge := range network.Edges {
		if !nodes[edge.From] || !nodes[edge.To] {
			return &FlowError{"unknown-node", fmt.Sprintf("edge has an unknown endpoint: %s → %s", edge.From, edge.To)}
		}
		if edge.From == edge.To {
			return &FlowError{"self-edge", "edge loops at " + edge.From}
		}
		if edge.Capacity < 0 || edge.Capacity > MaxCapacity {
			return &FlowError{"bad-capacity", fmt.Sprintf("capacities are whole numbers from 0 to %d", MaxCapacity)}
		}
		pair, reverse := edge.From+"\x00"+edge.To, edge.To+"\x00"+edge.From
		if pairs[pair] {
			return &FlowError{"duplicate-edge", fmt.Sprintf("edge appears twice: %s → %s", edge.From, edge.To)}
		}
		if pairs[reverse] {
			return &FlowError{"opposite-edge", fmt.Sprintf("use one directed edge per pair: %s → %s", edge.From, edge.To)}
		}
		pairs[pair] = true
	}
	return nil
}

func neighbours(network Network) map[string][]string {
	result := map[string][]string{}
	for _, node := range network.Nodes {
		result[node] = []string{}
	}
	for _, edge := range network.Edges {
		result[edge.From] = append(result[edge.From], edge.To)
		result[edge.To] = append(result[edge.To], edge.From)
	}
	return result
}

// Every original edge starts with its full capacity forward and 0 backward.
func residualMap(network Network) Residual {
	residual := Residual{}
	for _, node := range network.Nodes {
		residual[node] = map[string]int{}
	}
	for _, edge := range network.Edges {
		residual[edge.From][edge.To] = edge.Capacity
		residual[edge.To][edge.From] = 0
	}
	return residual
}

// Breadth-first search over edges that still have residual capacity: the shortest route.
func findPath(adjacency map[string][]string, residual Residual, source, sink string) []string {
	parent := map[string]string{source: ""}
	queue := []string{source}
	reached := func(node string) bool { _, ok := parent[node]; return ok }
	for head := 0; head < len(queue) && !reached(sink); head++ {
		from := queue[head]
		for _, to := range adjacency[from] {
			if residual[from][to] <= 0 || reached(to) {
				continue
			}
			parent[to] = from
			queue = append(queue, to)
			if to == sink {
				break
			}
		}
	}
	if !reached(sink) {
		return nil
	}
	path := []string{}
	for at := sink; at != ""; at = parent[at] {
		path = append(path, at)
	}
	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}
	return path
}

// Augment is Edmonds–Karp: send each shortest path's bottleneck until the sink is unreachable.
func Augment(network Network, source, sink string) (Augmented, error) {
	if err := validate(network, source, sink); err != nil {
		return Augmented{}, err
	}
	adjacency := neighbours(network)
	residual := residualMap(network)
	original := map[Pair]bool{}
	for _, edge := range network.Edges {
		original[Pair{edge.From, edge.To}] = true
	}
	paths := []Augmentation{}
	value := 0
	for {
		path := findPath(adjacency, residual, source, sink)
		if path == nil {
			break
		}
		bottleneck := MaxCapacity
		for i := 0; i < len(path)-1; i++ {
			bottleneck = min(bottleneck, residual[path[i]][path[i+1]])
		}
		cancels := []Pair{}
		for i := 0; i < len(path)-1; i++ {
			from, to := path[i], path[i+1]
			// Sending forward uses up capacity and leaves the same amount to take back later.
			residual[from][to] -= bottleneck
			residual[to][from] += bottleneck
			if !original[Pair{from, to}] {
				cancels = append(cancels, Pair{to, from})
			}
		}
		value += bottleneck
		paths = append(paths, Augmentation{path, bottleneck, value, cancels})
	}
	return Augmented{value, paths, adjacency, residual}, nil
}