Graph overview.

export type Step =
	/** edge: an edge was added; total is the merged weight from `from` to `to` afterwards. */
	| { kind: 'edge'; from: string; to: string; weight: number; total: number }
	/** visit: a walk reached a node, which belongs to the numbered group. */
	| { kind: 'visit'; node: string; group: number }
	/** look: a walk examined the connection from `from` to `to`. */
	| { kind: 'look'; from: string; to: string }
	/** enter: a depth-first walk started exploring a node. */
	| { kind: 'enter'; node: string }
	/** leave: every edge out of the node has been explored. */
	| { kind: 'leave'; node: string }
	/** cycle: the walk reached a node it was still exploring. */
	| { kind: 'cycle'; nodes: string[] }
	/** pay: one payment in a settle-up plan. */
	| { kind: 'pay'; from: string; to: string; amount: number };

export type Edge = { from: string; to: string; weight: number };

const MAX_WEIGHT = 1_000_000_000;

// A directed, weighted graph. It keeps every edge in the order added, which is an edge list,
// and merges edges between the same two nodes into one entry in each node's adjacency maps,
// so "how much from A to B" and "what leaves A" are direct lookups.
export class Graph {
	#edges: Edge[] = [];
	#out = new Map<string, Map<string, number>>();
	#in = new Map<string, Map<string, number>>();
	#outTotal = new Map<string, number>();
	#inTotal = new Map<string, number>();

	/** Adds a node with no edges; returns false if it was already there. */
	addNode(node: string): boolean {
		if (this.#out.has(node)) return false;
		this.#out.set(node, new Map());
		this.#in.set(node, new Map());
		this.#outTotal.set(node, 0);
		this.#inTotal.set(node, 0);
		return true;
	}

	/** Adds an edge, and its nodes if they are new. A second edge between the same nodes merges. */
	addEdge(from: string, to: string, weight: number, steps?: Step[]): void {
		if (from === to) throw new RangeError('an edge joins two different nodes');
		if (!Number.isInteger(weight) || weight < 1 || weight > MAX_WEIGHT)
			throw new RangeError('a weight is a whole number from 1 to 1000000000');
		this.addNode(from);
		this.addNode(to);
		this.#edges.push({ from, to, weight });
		const total = this.weight(from, to) + weight;
		this.#out.get(from)!.set(to, total);
		this.#in.get(to)!.set(from, total);
		this.#outTotal.set(from, this.#outTotal.get(from)! + weight);
		this.#inTotal.set(to, this.#inTotal.get(to)! + weight);
		steps?.push({ kind: 'edge', from, to, weight, total });
	}

	nodes(): string[] {
		return [...this.#out.keys()];
	}

	/** Every edge in the order added, before merging. */
	edges(): Edge[] {
		return this.#edges.map((edge) => ({ ...edge }));
	}

	/** How many merged entries the adjacency maps hold: one per ordered pair with an edge. */
	get pairs(): number {
		let pairs = 0;
		for (const targets of this.#out.values()) pairs += targets.size;
		return pairs;
	}

	/** The merged weight from `from` to `to`, or 0. */
	weight(from: string, to: string): number {
		return this.#out.get(from)?.get(to) ?? 0;
	}

	/** Nodes an edge leads to from `node`, with merged weights, in the order first connected. */
	successors(node: string): [string, number][] {
		return [...(this.#out.get(node) ?? [])];
	}

	/** Nodes with an edge into `node`, with merged weights, in the order first connected. */
	predecessors(node: string): [string, number][] {
		return [...(this.#in.get(node) ?? [])];
	}

	weightOut(node: string): number {
		return this.#outTotal.get(node) ?? 0;
	}

	weightIn(node: string): number {
		return this.#inTotal.get(node) ?? 0;
	}

	// Groups of nodes joined by edges in either direction. A breadth-first walk starts at each
	// node not yet reached, in node order, and looks along successors, then predecessors.
	components(steps?: Step[]): string[][] {
		const groups: string[][] = [];
		const reached = new Set<string>();
		for (const start of this.#out.keys()) {
			if (reached.has(start)) continue;
			const group = [start];
			reached.add(start);
			steps?.push({ kind: 'visit', node: start, group: groups.length });
			for (let i = 0; i < group.length; i++) {
				const node = group[i];
				for (const next of [...this.#out.get(node)!.keys(), ...this.#in.get(node)!.keys()]) {
					steps?.push({ kind: 'look', from: node, to: next });
					if (reached.has(next)) continue;
					reached.add(next);
					group.push(next);
					steps?.push({ kind: 'visit', node: next, group: groups.length });
				}
			}
			groups.push(group);
		}
		return groups;
	}

	// A cycle that follows edge directions, or null. A depth-first walk starts at each node not
	// yet explored, in node order; reaching a node still on the walk's path closes a cycle.
	// The walk keeps its own stack, so a long chain cannot overflow the call stack.
	findCycle(steps?: Step[]): string[] | null {
		const done = new Set<string>();
		const onPath = new Set<string>();
		for (const root of this.#out.keys()) {
			if (done.has(root)) continue;
			const path = [root];
			// Each frame holds a node's neighbors and a cursor, so taking the next one is O(1).
			const pending = [{ list: [...this.#out.get(root)!.keys()], at: 0 }];
			onPath.add(root);
			steps?.push({ kind: 'enter', node: root });
			while (path.length) {
				const node = path.at(-1)!;
				const frame = pending.at(-1)!;
				const next = frame.at < frame.list.length ? frame.list[frame.at++] : undefined;
				if (next === undefined) {
					done.add(node);
					onPath.delete(node);
					steps?.push({ kind: 'leave', node });
					path.pop();
					pending.pop();
					continue;
				}
				steps?.push({ kind: 'look', from: node, to: next });
				if (onPath.has(next)) {
					const cycle = path.slice(path.indexOf(next));
					steps?.push({ kind: 'cycle', nodes: [...cycle] });
					return cycle;
				}
				if (done.has(next)) continue;
				onPath.add(next);
				steps?.push({ kind: 'enter', node: next });
				path.push(next);
				pending.push({ list: [...this.#out.get(next)!.keys()], at: 0 });
			}
		}
		return null;
	}
}

// Step is one recorded event. Kind is edge, visit, look, enter, leave, cycle, or pay; the other
// fields that kind uses are set.
type Step struct {
	Kind   string
	From   string
	To     string
	Node   string
	Weight int
	Total  int
	Group  int
	Nodes  []string
	Amount int
}

type Edge struct {
	From, To string
	Weight   int
}

// Neighbor is a node at the other end of merged edges, with their total weight.
type Neighbor struct {
	Node   string
	Weight int
}

const maxWeight = 1_000_000_000

func record(steps *[]Step, step Step) {
	if steps != nil {
		*steps = append(*steps, step)
	}
}

// Graph is a directed, weighted graph. It keeps every edge in the order added, which is an edge
// list, and merges edges between the same two nodes into one entry in each node's adjacency
// maps, so "how much from A to B" and "what leaves A" are direct lookups. The order slices
// remember when each neighbor was first connected, because Go maps have no order.
type Graph struct {
	nodes             []string
	edges             []Edge
	out, in           map[string]map[string]int
	outOrder, inOrder map[string][]string
	outTotal, inTotal map[string]int
}

func NewGraph() *Graph {
	return &Graph{
		out:      map[string]map[string]int{},
		in:       map[string]map[string]int{},
		outOrder: map[string][]string{},
		inOrder:  map[string][]string{},
		outTotal: map[string]int{},
		inTotal:  map[string]int{},
	}
}

// AddNode adds a node with no edges and reports false if it was already there.
func (g *Graph) AddNode(node string) bool {
	if _, ok := g.out[node]; ok {
		return false
	}
	g.nodes = append(g.nodes, node)
	g.out[node] = map[string]int{}
	g.in[node] = map[string]int{}
	return true
}

// AddEdge adds an edge, and its nodes if they are new. A second edge between the same nodes merges.
func (g *Graph) AddEdge(from, to string, weight int, steps *[]Step) error {
	if from == to {
		return errors.New("an edge joins two different nodes")
	}
	if weight < 1 || weight > maxWeight {
		return errors.New("a weight is a whole number from 1 to 1000000000")
	}
	g.AddNode(from)
	g.AddNode(to)
	g.edges = append(g.edges, Edge{from, to, weight})
	if _, ok := g.out[from][to]; !ok {
		g.outOrder[from] = append(g.outOrder[from], to)
		g.inOrder[to] = append(g.inOrder[to], from)
	}
	total := g.out[from][to] + weight
	g.out[from][to] = total
	g.in[to][from] = total
	g.outTotal[from] += weight
	g.inTotal[to] += weight
	record(steps, Step{Kind: "edge", From: from, To: to, Weight: weight, Total: total})
	return nil
}

func (g *Graph) Nodes() []string { return slices.Clone(g.nodes) }

// Edges returns every edge in the order added, before merging.
func (g *Graph) Edges() []Edge { return slices.Clone(g.edges) }

// Pairs counts merged entries: one per ordered pair of nodes with an edge.
func (g *Graph) Pairs() int {
	pairs := 0
	for _, targets := range g.outOrder {
		pairs += len(targets)
	}
	return pairs
}

// Weight returns the merged weight from one node to another, or 0.
func (g *Graph) Weight(from, to string) int { return g.out[from][to] }

// Successors lists nodes an edge leads to, with merged weights, in the order first connected.
func (g *Graph) Successors(node string) []Neighbor {
	var list []Neighbor
	for _, to := range g.outOrder[node] {
		list = append(list, Neighbor{to, g.out[node][to]})
	}
	return list
}

// Predecessors lists nodes with an edge into this one, with merged weights, in the order first connected.
func (g *Graph) Predecessors(node string) []Neighbor {
	var list []Neighbor
	for _, from := range g.inOrder[node] {
		list = append(list, Neighbor{from, g.in[node][from]})
	}
	return list
}

func (g *Graph) WeightOut(node string) int { return g.outTotal[node] }

func (g *Graph) WeightIn(node string) int { return g.inTotal[node] }

// Components returns groups of nodes joined by edges in either direction. A breadth-first walk
// starts at each node not yet reached, in node order, and looks along successors, then predecessors.
func (g *Graph) Components(steps *[]Step) [][]string {
	var groups [][]string
	reached := map[string]bool{}
	for _, start := range g.nodes {
		if reached[start] {
			continue
		}
		group := []string{start}
		reached[start] = true
		record(steps, Step{Kind: "visit", Node: start, Group: len(groups)})
		for i := 0; i < len(group); i++ {
			node := group[i]
			for _, next := range slices.Concat(g.outOrder[node], g.inOrder[node]) {
				record(steps, Step{Kind: "look", From: node, To: next})
				if reached[next] {
					continue
				}
				reached[next] = true
				group = append(group, next)
				record(steps, Step{Kind: "visit", Node: next, Group: len(groups)})
			}
		}
		groups = append(groups, group)
	}
	return groups
}

// FindCycle returns a cycle that follows edge directions, or nil. A depth-first walk starts at
// each node not yet explored, in node order; reaching a node still on the walk's path closes a
// cycle. The walk keeps its own stack, so a long chain cannot overflow the call stack.
func (g *Graph) FindCycle(steps *[]Step) []string {
	done := map[string]bool{}
	onPath := map[string]bool{}
	for _, root := range g.nodes {
		if done[root] {
			continue
		}
		path := []string{root}
		next := []int{0}
		onPath[root] = true
		record(steps, Step{Kind: "enter", Node: root})
		for len(path) > 0 {
			top := len(path) - 1
			node := path[top]
			if next[top] == len(g.outOrder[node]) {
				done[node] = true
				delete(onPath, node)
				record(steps, Step{Kind: "leave", Node: node})
				path, next = path[:top], next[:top]
				continue
			}
			to := g.outOrder[node][next[top]]
			next[top]++
			record(steps, Step{Kind: "look", From: node, To: to})
			if onPath[to] {
				cycle := slices.Clone(path[slices.Index(path, to):])
				record(steps, Step{Kind: "cycle", Nodes: slices.Clone(cycle)})
				return cycle
			}
			if done[to] {
				continue
			}
			onPath[to] = true
			record(steps, Step{Kind: "enter", Node: to})
			path = append(path, to)
			next = append(next, 0)
		}
	}
	return nil
}