Breadth-first and depth-first search.

export type GraphNode = { id: string; next: readonly string[] };
export type Step = {
	/** discover: joined the queue. visit: taken from the queue, or pushed onto the stack. skip: already seen. finish: nothing left below it. */
	kind: 'discover' | 'visit' | 'skip' | 'finish';
	node: string;
	depth: number;
	/** The node it was reached from, or null for the start. */
	from: string | null;
};
export type Options = {
	steps?: Step[];
	/** Stop as soon as a visited node passes this test. */
	until?: (node: string) => boolean;
};
export type Search = {
	/** Nodes in the order they were visited. */
	order: string[];
	/** Depth first only: nodes in the order everything reachable from them was done. */
	finished: string[];
	/** Steps from the start along the way the search reached each node. */
	depth: Map<string, number>;
	parent: Map<string, string | null>;
	/** The node `until` accepted, or null when the search ran out of nodes. */
	stopped: string | null;
};

function index(nodes: readonly GraphNode[], start: string): Map<string, readonly string[]> {
	const next = new Map<string, readonly string[]>();
	nodes.forEach((node, i) => {
		if (next.has(node.id)) throw new RangeError(`node ${i} repeats the id ${node.id}`);
		next.set(node.id, node.next);
	});
	for (const node of nodes)
		for (const id of node.next)
			if (!next.has(id)) throw new RangeError(`${node.id} leads to unknown node ${id}`);
	if (!next.has(start)) throw new RangeError(`unknown start node ${start}`);
	return next;
}

function emptySearch(start: string): Search {
	return {
		order: [],
		finished: [],
		depth: new Map([[start, 0]]),
		parent: new Map([[start, null]]),
		stopped: null
	};
}

// Breadth first: visit the start, then everything one step away, then everything two steps
// away, using a first-in, first-out queue. A node is marked seen when it joins the queue, so
// it joins once, and its depth is the fewest steps from the start.
export function breadthFirst(
	nodes: readonly GraphNode[],
	start: string,
	{ steps, until }: Options = {}
): Search {
	const next = index(nodes, start);
	const search = emptySearch(start);
	steps?.push({ kind: 'discover', node: start, depth: 0, from: null });
	const queue = [start];
	for (let head = 0; head < queue.length; head++) {
		const node = queue[head];
		const depth = search.depth.get(node)!;
		search.order.push(node);
		steps?.push({ kind: 'visit', node, depth, from: search.parent.get(node) ?? null });
		if (until?.(node)) {
			search.stopped = node;
			break;
		}
		for (const neighbor of next.get(node)!) {
			if (search.depth.has(neighbor)) {
				steps?.push({ kind: 'skip', node: neighbor, depth: depth + 1, from: node });
				continue;
			}
			search.depth.set(neighbor, depth + 1);
			search.parent.set(neighbor, node);
			steps?.push({ kind: 'discover', node: neighbor, depth: depth + 1, from: node });
			queue.push(neighbor);
		}
	}
	return search;
}

// Depth first: follow the first unseen neighbor as far as it goes, and back up only when a
// node has nothing left. A stack of (node, next neighbor) replaces recursion, so a deep graph
// cannot overflow the call stack, and the order is the same as the recursive version's.
export function depthFirst(
	nodes: readonly GraphNode[],
	start: string,
	{ steps, until }: Options = {}
): Search {
	const next = index(nodes, start);
	const search = emptySearch(start);
	search.order.push(start);
	steps?.push({ kind: 'visit', node: start, depth: 0, from: null });
	if (until?.(start)) {
		search.stopped = start;
		return search;
	}
	const stack = [{ node: start, at: 0 }];
	while (stack.length > 0) {
		const top = stack[stack.length - 1];
		const neighbors = next.get(top.node)!;
		const depth = stack.length;
		if (top.at === neighbors.length) {
			stack.pop();
			search.finished.push(top.node);
			const from = search.parent.get(top.node) ?? null;
			steps?.push({ kind: 'finish', node: top.node, depth: depth - 1, from });
			continue;
		}
		const neighbor = neighbors[top.at++];
		if (search.depth.has(neighbor)) {
			steps?.push({ kind: 'skip', node: neighbor, depth, from: top.node });
			continue;
		}
		search.depth.set(neighbor, depth);
		search.parent.set(neighbor, top.node);
		search.order.push(neighbor);
		steps?.push({ kind: 'visit', node: neighbor, depth, from: top.node });
		if (until?.(neighbor)) {
			search.stopped = neighbor;
			break;
		}
		stack.push({ node: neighbor, at: 0 });
	}
	return search;
}

/** The way a search reached `target`, from the start, or null if it never reached it. */
export function pathTo(search: Search, target: string): string[] | null {
	if (!search.parent.has(target)) return null;
	const path = [target];
	for (let node = search.parent.get(target); node != null; node = search.parent.get(node))
		path.push(node);
	return path.reverse();
}

// Node is a graph node and the nodes it leads to, in order.
type Node struct {
	ID   string   `json:"id"`
	Next []string `json:"next"`
}

// Step is one move of a search. Kind is "discover" (joined the queue), "visit" (taken
// from the queue, or pushed onto the stack), "skip" (already seen), or "finish" (nothing left below it).
// From is the node it was reached from, empty for the start.
type Step struct {
	Kind  string `json:"kind"`
	Node  string `json:"node"`
	Depth int    `json:"depth"`
	From  string `json:"from"`
}

// Options records steps when Steps is not nil, and stops as soon as a visited node
// passes Until when Until is not nil.
type Options struct {
	Steps *[]Step
	Until func(node string) bool
}

// Search is what a search found. Order lists nodes as they were visited; Finished, for
// depth first only, as everything reachable from them was done. Depth and Parent describe
// the way the search reached each node. Stopped is the node Until accepted, if Found.
type Search struct {
	Start    string
	Order    []string
	Finished []string
	Depth    map[string]int
	Parent   map[string]string
	Stopped  string
	Found    bool
}

func index(nodes []Node, start string) (map[string][]string, error) {
	next := map[string][]string{}
	for i, node := range nodes {
		if _, taken := next[node.ID]; taken {
			return nil, fmt.Errorf("node %d repeats the id %s", i, node.ID)
		}
		next[node.ID] = node.Next
	}
	for _, node := range nodes {
		for _, id := range node.Next {
			if _, known := next[id]; !known {
				return nil, fmt.Errorf("%s leads to unknown node %s", node.ID, id)
			}
		}
	}
	if _, known := next[start]; !known {
		return nil, fmt.Errorf("unknown start node %s", start)
	}
	return next, nil
}

func newSearch(start string) *Search {
	return &Search{Start: start, Order: []string{}, Finished: []string{},
		Depth: map[string]int{start: 0}, Parent: map[string]string{}}
}

func record(options Options, kind, node string, depth int, from string) {
	if options.Steps != nil {
		*options.Steps = append(*options.Steps, Step{kind, node, depth, from})
	}
}

// BreadthFirst visits the start, then everything one step away, then everything two
// steps away, using a first-in, first-out queue. A node is marked seen when it joins the
// queue, so it joins once, and its depth is the fewest steps from the start.
func BreadthFirst(nodes []Node, start string, options Options) (*Search, error) {
	next, err := index(nodes, start)
	if err != nil {
		return nil, err
	}
	search := newSearch(start)
	record(options, "discover", start, 0, "")
	queue := []string{start}
	for head := 0; head < len(queue); head++ {
		node := queue[head]
		depth := search.Depth[node]
		search.Order = append(search.Order, node)
		record(options, "visit", node, depth, search.Parent[node])
		if options.Until != nil && options.Until(node) {
			search.Stopped, search.Found = node, true
			break
		}
		for _, neighbor := range next[node] {
			if _, seen := search.Depth[neighbor]; seen {
				record(options, "skip", neighbor, depth+1, node)
				continue
			}
			search.Depth[neighbor] = depth + 1
			search.Parent[neighbor] = node
			record(options, "discover", neighbor, depth+1, node)
			queue = append(queue, neighbor)
		}
	}
	return search, nil
}

// DepthFirst follows the first unseen neighbor as far as it goes, and backs up only when
// a node has nothing left. A stack of (node, next neighbor) replaces recursion, so a deep
// graph cannot overflow the call stack, and the order is the same as the recursive version's.
func DepthFirst(nodes []Node, start string, options Options) (*Search, error) {
	next, err := index(nodes, start)
	if err != nil {
		return nil, err
	}
	search := newSearch(start)
	search.Order = append(search.Order, start)
	record(options, "visit", start, 0, "")
	if options.Until != nil && options.Until(start) {
		search.Stopped, search.Found = start, true
		return search, nil
	}
	type frame struct {
		node string
		at   int
	}
	stack := []frame{{start, 0}}
	for len(stack) > 0 {
		top := &stack[len(stack)-1]
		neighbors := next[top.node]
		depth := len(stack)
		if top.at == len(neighbors) {
			node := top.node
			stack = stack[:len(stack)-1]
			search.Finished = append(search.Finished, node)
			record(options, "finish", node, depth-1, search.Parent[node])
			continue
		}
		neighbor := neighbors[top.at]
		top.at++
		if _, seen := search.Depth[neighbor]; seen {
			record(options, "skip", neighbor, depth, top.node)
			continue
		}
		search.Depth[neighbor] = depth
		search.Parent[neighbor] = top.node
		search.Order = append(search.Order, neighbor)
		record(options, "visit", neighbor, depth, top.node)
		if options.Until != nil && options.Until(neighbor) {
			search.Stopped, search.Found = neighbor, true
			break
		}
		stack = append(stack, frame{neighbor, 0})
	}
	return search, nil
}

// PathTo returns the way a search reached target, from the start, or nil if it never did.
func PathTo(search *Search, target string) []string {
	if _, reached := search.Depth[target]; !reached {
		return nil
	}
	path := []string{target}
	for node := target; node != search.Start; {
		node = search.Parent[node]
		path = append(path, node)
	}
	slices.Reverse(path)
	return path
}