Skip to content

Instantly share code, notes, and snippets.

@DimitryDushkin

DimitryDushkin/remove-cyclic-dependencies.ts

Created June 5, 2022 23:19
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save DimitryDushkin/b223ebba5a2e6bfdb87a5406eae32ef8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save DimitryDushkin/b223ebba5a2e6bfdb87a5406eae32ef8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. DimitryDushkin created this gist Jun 5, 2022.
    54 changes: 54 additions & 0 deletions remove-cyclic-dependencies.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,54 @@
    /**
    * 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);
    };