有向グラフの閉路を見つけるJS

DetectCircularDepencies.js

/** @type {Map<string, Set<string>>} */
const dependencyMap = /* provide source */;

/** @type {Set<string>} */
const searched = new Set();

/**
 * @param {string} target
 * @param {string[]} path
 */
const search = (target, path) => {
  if (searched.has(target)) return;

  searched.add(target);

  const children = dependencyMap.get(target);

  if (!children) return;

  for (const child of children.values()) {
    const newPath = [...path, child];

    if (!isUniqueArray(newPath)) {
      printLoop(newPath);
    } else {
      search(child, newPath);
    }
  }
};

/**
 * @param {string[]} array
 */
const isUniqueArray = (array) => {
  return array.length == new Set(array).size;
};

/**
 * @param {string[]} path
 */
const printLoop = (path) => {
  const last = path.at(-1);
  const index = path.findIndex((entry) => entry == last);
  const loop = path.slice(index);

  console.log(loop.join(" -> "));
};

for (const key of dependencyMap.keys()) {
  search(key, [key]);
}