remove-cyclic-dependencies.ts

/**
 * Main source of cyclic dependencies is previous step where graph is created
 * Often top-level task has same owner as children tasks
 * Since we create edge in graph also by same owner that's why there is cyclic deps
 *
 * IDEA: mitigate the issue by starting DFS walk from top-level (source) tasks!
 */
export const removeCyclicDependencies = (
  graph: Graph,
  tasks: Array<Task>
): void => {
  // Track visited to avoid computing path for already computed nodes
  const visited = new Set();
  let cyclicDepsRemovedCount = 0;

  const dfsAndRemove = (rootTaskId: ID) => {
    // [current task ID, set of previously visited tasks]
    const stack: Array<[ID, Set<ID>]> = [[rootTaskId, new Set()]];

    while (stack.length > 0) {
      const nextValue = stack.pop();
      nullthrows(nextValue);
      const [taskId, prevSet] = nextValue;

      const blockedBy = graph.get(taskId) ?? new Set();

      visited.add(taskId);

      for (const blockedById of blockedBy) {
        // cycle detected!
        if (prevSet.has(blockedById)) {
          // remove that edge
          blockedBy.delete(blockedById);
          cyclicDepsRemovedCount++;
          continue;
        }

        const newPrevSet = new Set(prevSet);
        newPrevSet.add(blockedById);
        stack.push([blockedById, newPrevSet]);
      }
    }
  };

  for (const task of tasks) {
    if (visited.has(task.id)) {
      continue;
    }

    dfsAndRemove(task.id);
  }

  console.debug("Cyclic deps removed:", cyclicDepsRemovedCount);
};