Skip to content

Instantly share code, notes, and snippets.

@gibson042

gibson042/graph-path-extremes.ts

Created April 28, 2026 17:51
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save gibson042/0cb1328eef610208abad49d2d5ba440a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save gibson042/0cb1328eef610208abad49d2d5ba440a to your computer and use it in GitHub Desktop.
Download ZIP
beyond Dijkstra's algorithm
Raw
graph-path-extremes.ts
/**
* Calculate shortest and longest paths from specific nodes in a directed graph
* to all other nodes.
* Consider loading in the TypeScript Playground:
* https://www.typescriptlang.org/play/
*/
// #region utils
/**
* @typedef {<O extends Record<string, unknown>>(
* obj: O,
* ) => Exclude<
* { [K in keyof O]: K extends string ? [K, O[K]] : never }[keyof O],
* undefined
* >[]} TypedEntries
*/
const typedEntries = /** @type {TypedEntries} */ (Object.entries);
/**
* Return the value from `map` associated with `key`. If there is not yet such a
* value, get one from `makeValue(key)` and update `map` before returning the
* new value.
*
* @template K
* @template V
* @param {K extends WeakKey ? WeakMap<K, V> : Map<K, V>} map
* @param {K} key
* @param {(key: K) => V} makeValue
* @returns {V}
*/
const provideLazyMap = (map, key, makeValue) => {
const found = map.get(key);
if (found !== undefined || map.has(key)) {
return /** @type {V} */ (found);
}
const value = makeValue(key);
map.set(key, value);
return value;
};
/**
* Map the elements of an array to new values, skipping elements for which the
* mapping results in either `undefined` or `false`.
*
* @template T
* @template U
* @param {T[]} arr
* @param {(value: T, index: number, arr: T[]) => U | undefined | false} mapOrDrop
* @returns {U[]}
*/
const partialMap = (arr, mapOrDrop) =>
arr.reduce((results, el, i, arrArg) => {
const result = mapOrDrop(el, i, arrArg);
if (result !== undefined && result !== false) {
results.push(result);
}
return results;
}, /** @type {U[]} */ ([]));
// #endregion utils
/** @typedef {number} FlowNode */
/** @typedef {FlowNode} PathStart */
/** @typedef {FlowNode} PathEnd */
/** @typedef {[start: PathStart, ...midpoints: FlowNode[]]} Path */
const arcs = /** @type {Array<[source: FlowNode, target: FlowNode]>} */ ([
[1, 2],
[1, 3],
[3, 2],
[3, 4],
[4, 3],
[3, 3.5],
[3.5, 4],
]).sort((_a, _b) => Math.random() - 0.5);
const nodes = [...new Set(arcs.flatMap(arc => arc))];
const rootSet = new Set(nodes);
for (const [_src, target] of arcs) rootSet.delete(target);
const roots = rootSet.size > 0 ? [...rootSet] : nodes.filter(() => Math.random() < 0.5);
/** @type {Map<PathEnd, Map<PathStart, Path[]>>} */
const pathsToNode = new Map(roots.map(n => [n, new Map()]));
/** @type {(oldEnd: FlowNode) => Array<[start: FlowNode, pathsFromStart: Path[]]>} */
const makePathExtensions = oldEnd => {
/** @type {Array<[start: FlowNode, pathsFromStart: Path[]]>} */
const prefixes = [
...pathsToNode.get(oldEnd),
[oldEnd, [/** @type {Path} */ (/** @type {unknown} */ ([]))]],
];
return prefixes.map(([start, pathsFromStart]) => [
start,
pathsFromStart.map(path => [...path, oldEnd]),
]);
};
/**
* Add a new Path to an existing array, maintaining heap-like invariants
* (no other element shorter than the first or longer than the last).
*
* @param {Path[]} paths
* @param {Path} path
*/
const addPath = (paths, path) => {
if (paths.length === 0 || path.length >= paths.at(-1).length) paths.push(path);
else if (path.length < paths[0].length) paths.unshift(path);
else paths.splice(-1, 0, path);
};
let pendingArcs = [...arcs];
let frontier = new Set(roots);
while (frontier.size !== 0) {
const nextFrontier = new Set();
const consumedArcs = [];
for (let i = 0; i < pendingArcs.length; i += 1) {
const arc = pendingArcs[i];
const [src, target] = arc;
if (!frontier.has(src)) continue;
consumedArcs.push(arc);
pendingArcs[i] = undefined;
if (!pathsToNode.has(target)) {
nextFrontier.add(target);
pathsToNode.set(target, new Map());
}
/** Paths ending with `arc`, excluding those that pass *through* `target`. */
const pathsEndingWithArcByStart = new Map(partialMap(makePathExtensions(src), ([start, pathsFromStart]) => {
const acyclicPaths = pathsFromStart.filter(path => !path.includes(target));
return acyclicPaths.length > 0 && [start, acyclicPaths];
}));
/** Paths starting with `target` that don't already include `src`. */
const downstreamPaths = partialMap(nodes, /** @type {(downstream: FlowNode) => [PathEnd, Path[]]} */ (downstream => {
if (downstream === target) return [target, [/** @type {Path} */ (/** @type {unknown} */ ([]))]];
const pathsFromTarget = pathsToNode.get(downstream)?.get(target);
const acyclicPaths = pathsFromTarget?.filter(path => !path.includes(src));
return acyclicPaths?.length > 0 && [downstream, acyclicPaths];
}));
for (const [downstream, pathsFromTarget] of downstreamPaths) {
const pathsToDownstream = pathsToNode.get(downstream);
for (const [upstream, pathsEndingWithArc] of pathsEndingWithArcByStart) {
if (upstream === downstream) continue;
const upstreamToDownstream = provideLazyMap(pathsToDownstream, upstream, () => /** @type {Path[]} */ ([]));
for (const prefix of pathsEndingWithArc) {
for (const suffix of pathsFromTarget) {
/** @type {Path} */
const newPath = [...prefix, ...suffix];
const newPathNodes = new Set(newPath).add(downstream);
if (newPathNodes.size !== newPath.length + 1) continue;
// console.log({arc:[src,target].join(" "),upstream,downstream,prefix:[...prefix].join(" "),suffix:[...suffix].join(" ")});
addPath(upstreamToDownstream, newPath);
}
}
}
}
}
pendingArcs = pendingArcs.filter(x => x);
frontier = nextFrontier;
}
for (const [pathEnd, pathsMap] of [...pathsToNode].sort(([a], [b]) => a < b ? -1 : a > b ? 1 : 0)) {
console.log(`# TO ${pathEnd}`);
for (const [pathStart, paths] of [...pathsMap].sort(([a], [b]) => a < b ? -1 : a > b ? 1 : 0)) {
console.log(`FROM ${pathStart}`, paths.map(path => path.join(" ")));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment