Strongly connected components.

export const MAX_NODES = 64;
export const MAX_EDGES = 256;
export type Edge = { from: string; to: string };
export type Graph = { nodes: string[]; edges: Edge[] };
export type ComponentErrorCode =
	'too-big' | 'bad-node' | 'duplicate-node' | 'unknown-node' | 'duplicate-edge';

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

function adjacency(graph: Graph) {
	if (graph.nodes.length > MAX_NODES || graph.edges.length > MAX_EDGES)
		throw new ComponentError('too-big', `up to ${MAX_NODES} nodes and ${MAX_EDGES} edges`);
	const nodes = new Set<string>();
	for (const node of graph.nodes) {
		if (!/^[a-z][a-z0-9-]{0,23}$/.test(node))
			throw new ComponentError('bad-node', `node ids are lowercase slugs: ${node}`);
		if (nodes.has(node)) throw new ComponentError('duplicate-node', `node appears twice: ${node}`);
		nodes.add(node);
	}
	const next = new Map<string, string[]>();
	const reverse = new Map<string, string[]>();
	for (const node of graph.nodes) {
		next.set(node, []);
		reverse.set(node, []);
	}
	const edges = new Set<string>();
	for (const edge of graph.edges) {
		if (!nodes.has(edge.from) || !nodes.has(edge.to))
			throw new ComponentError(
				'unknown-node',
				`edge has an unknown endpoint: ${edge.from} → ${edge.to}`
			);
		const key = `${edge.from}\0${edge.to}`;
		if (edges.has(key))
			throw new ComponentError('duplicate-edge', `edge appears twice: ${edge.from} → ${edge.to}`);
		edges.add(key);
		next.get(edge.from)!.push(edge.to);
		reverse.get(edge.to)!.push(edge.from);
	}
	return { next, reverse };
}

// Byte order, the same in every language, so the output never depends on a locale.
const byName = (a: string, b: string) => (a < b ? -1 : a > b ? 1 : 0);

export type SccTrace = { finishOrder: string[]; collected: string[][] };

// Kosaraju: finish order on the graph, then one reverse-graph search per component.
export function kosaraju(graph: Graph): SccTrace {
	const { next, reverse } = adjacency(graph);
	const visited = new Set<string>();
	const finishOrder: string[] = [];
	function finish(node: string) {
		visited.add(node);
		for (const to of next.get(node)!) if (!visited.has(to)) finish(to);
		finishOrder.push(node);
	}
	for (const node of graph.nodes) if (!visited.has(node)) finish(node);
	// A fresh start for the second pass: leftover marks would hide every node.
	visited.clear();
	const collected: string[][] = [];
	function collect(node: string, component: string[]) {
		visited.add(node);
		component.push(node);
		for (const from of reverse.get(node)!) if (!visited.has(from)) collect(from, component);
	}
	for (const node of [...finishOrder].reverse()) {
		if (visited.has(node)) continue;
		const component: string[] = [];
		collect(node, component);
		collected.push(component.sort(byName));
	}
	return { finishOrder, collected };
}

const MaxNodes, MaxEdges = 64, 256

type Edge struct{ From, To string }
type Graph struct {
	Nodes []string
	Edges []Edge
}
type ComponentError struct{ Code, Message string }

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

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

func adjacency(graph Graph) (map[string][]string, map[string][]string, error) {
	if len(graph.Nodes) > MaxNodes || len(graph.Edges) > MaxEdges {
		return nil, nil, &ComponentError{"too-big", fmt.Sprintf("up to %d nodes and %d edges", MaxNodes, MaxEdges)}
	}
	nodes := map[string]bool{}
	for _, node := range graph.Nodes {
		if !nodePattern.MatchString(node) {
			return nil, nil, &ComponentError{"bad-node", "node ids are lowercase slugs: " + node}
		}
		if nodes[node] {
			return nil, nil, &ComponentError{"duplicate-node", "node appears twice: " + node}
		}
		nodes[node] = true
	}
	next, reverse := map[string][]string{}, map[string][]string{}
	for _, node := range graph.Nodes {
		next[node] = []string{}
		reverse[node] = []string{}
	}
	seen := map[Edge]bool{}
	for _, edge := range graph.Edges {
		if !nodes[edge.From] || !nodes[edge.To] {
			return nil, nil, &ComponentError{"unknown-node", fmt.Sprintf("edge has an unknown endpoint: %s → %s", edge.From, edge.To)}
		}
		if seen[edge] {
			return nil, nil, &ComponentError{"duplicate-edge", fmt.Sprintf("edge appears twice: %s → %s", edge.From, edge.To)}
		}
		seen[edge] = true
		next[edge.From] = append(next[edge.From], edge.To)
		reverse[edge.To] = append(reverse[edge.To], edge.From)
	}
	return next, reverse, nil
}

type SccTrace struct {
	FinishOrder []string
	Collected   [][]string
}

// Kosaraju: finish order on the graph, then one reverse-graph search per component.
func Kosaraju(graph Graph) (SccTrace, error) {
	next, reverse, err := adjacency(graph)
	if err != nil {
		return SccTrace{}, err
	}
	visited, finishOrder := map[string]bool{}, []string{}
	var finish func(string)
	finish = func(node string) {
		visited[node] = true
		for _, to := range next[node] {
			if !visited[to] {
				finish(to)
			}
		}
		finishOrder = append(finishOrder, node)
	}
	for _, node := range graph.Nodes {
		if !visited[node] {
			finish(node)
		}
	}
	// A fresh start for the second pass: leftover marks would hide every node.
	visited = map[string]bool{}
	collected := [][]string{}
	var collect func(string, *[]string)
	collect = func(node string, component *[]string) {
		visited[node] = true
		*component = append(*component, node)
		for _, from := range reverse[node] {
			if !visited[from] {
				collect(from, component)
			}
		}
	}
	for i := len(finishOrder) - 1; i >= 0; i-- {
		node := finishOrder[i]
		if visited[node] {
			continue
		}
		component := []string{}
		collect(node, &component)
		sort.Strings(component)
		collected = append(collected, component)
	}
	return SccTrace{finishOrder, collected}, nil
}