Determine if an adjacency list represents a single graph

traversal.ts

interface ReadOnlyMapNoGetter<K, V> {
	has(key: K): boolean;
	entries(): IterableIterator<[K, V]>;
	forEach(cb: (value: V, key: K, map: ReadOnlyMapNoGetter<K, V>) => void): void;
	keys(): IterableIterator<K>;
	values(): IterableIterator<V>;
	readonly size: number;
}

interface ReadOnlyMap<K, V> extends ReadOnlyMapNoGetter<K, V> {
	get(key: K): V | undefined;
	[Symbol.iterator](): IterableIterator<[K, V]>;
}

interface ReadOnlySet<V> extends ReadOnlyMapNoGetter<V, V> {
	[Symbol.iterator](): IterableIterator<V>;
}

type AdjacencyList<K, V> = ReadOnlyMap<K, { value: V; links: K[] }>;

function dfs<K>(
	list: AdjacencyList<K, unknown>,
	startingKey: K,
	visited: ReadOnlySet<K>
): ReadOnlySet<K> {
	const v = new Set<K>([startingKey, ...visited]);

	const node = list.get(startingKey);
	if (!node) {
		return v;
	}

	v.add(startingKey);

	for (const link of node.links) {
		if (!v.has(link)) {
			const visits = dfs(list, link, v);
			for (const visit of visits) {
				v.add(visit);
			}
		}
	}

	return v;
}

function reverse<K, V>(list: AdjacencyList<K, V>): AdjacencyList<K, V> {
	// New empty adjacency list
	const newList = new Map<K, { value: V; links: K[] }>();

	for (const [key, { value, links }] of list) {
		let node = newList.get(key);
		if (!node) {
			node = { value, links: [] };
			newList.set(key, node);
		}
		for (const link of links) {
			let node = newList.get(link);
			if (!node) {
				node = { value, links: [] };
				newList.set(link, node);
			}

			node.links.push(key);
		}
	}

	return newList;
}

function intersection<V>(
	s1: ReadOnlySet<V>,
	s2: ReadOnlySet<V>
): ReadOnlySet<V> {
	const result = new Set<V>();
	for (const v of s1) {
		if (s2.has(v)) {
			result.add(v);
		}
	}
	return result;
}

function union<V>(s1: ReadOnlySet<V>, s2: ReadOnlySet<V>): ReadOnlySet<V> {
	return new Set<V>([...s1, ...s2]);
}

function isGraphConnected(list: AdjacencyList<unknown, unknown>): boolean {
	const { value: key, done } = list.keys().next();
	if (done) {
		return false;
	}

	const dfs1 = dfs(list, key, new Set());
	const dfs2 = dfs(reverse(list), key, new Set());

	return union(dfs1, dfs2).size === list.size;
}

function pathHasCycle<K>(
	list: AdjacencyList<K, unknown>,
	startingKey: K,
	visited: ReadOnlySet<K>,
	predecessor: { key: K } | null
): boolean {
	if (visited.has(startingKey)) {
		return true;
	}

	let visits = new Set<K>([startingKey, ...visited]);
	visits.add(startingKey);

	const node = list.get(startingKey);
	if (!node) {
		return false;
	}

	for (const link of node.links) {
		if (!predecessor || link !== predecessor.key) {
			if (pathHasCycle(list, link, visits, { key: startingKey })) {
				return true;
			}
		}
	}
	return false;
}

function graphHasCycle<K>(list: AdjacencyList<K, unknown>): boolean {
	return [...list].some(([key]) => pathHasCycle(list, key, new Set(), null));
}

function isTree(list: AdjacencyList<unknown, unknown>): boolean {
	return !graphHasCycle(list) && isGraphConnected(list);
}

console.log(
	isGraphConnected(
		new Map([
			["cool", { value: 1, links: ["bar"] }],
			["bar", { value: 1, links: ["bar"] }],
			["baz", { value: 1, links: [] }],
		])
	)
);

console.log(
	isTree(
		new Map([
			["cool", { value: 1, links: ["bar", "baz", "foo"] }],
			["bar", { value: 2, links: ["cool", "widgets"] }],
			["baz", { value: 3, links: ["cool"] }],
			["foo", { value: 4, links: ["cool"] }],
			["widgets", { value: 5, links: ["bar"] }],
		])
	)
);