Graph.findCycles() does not always find cycles

[calebj0seph]

Consider the following systems with some trivial scheduling constraints that have a cycle:

class SystemA extends System { }

class SystemB extends System {
  constructor() {
    super();
    this.schedule(s => s.after(SystemD));
  }
}

class SystemC extends System {
  constructor() {
    super();
    this.schedule(s => s.after(SystemB));
  }
}

class SystemD extends System {
  constructor() {
    super();
    this.schedule(s => s.after(SystemC));
  }
}

await World.create({
  defs: [
    SystemA,
    SystemB,
    SystemC,
    SystemD,
  ],
});

World.create() will happily accept this despite the cycle between SystemB -> SystemD -> SystemC -> SystemB. This has bitten us on our application where we had such a cycle that went undetected. This caused the dependency graph to be broken causing strange behaviour.

When we rewrote findCycles() using Tarjan's strongly connection component algorithm, it was able to properly detect the cycle:

findCycles() {
    const cycles = [];
    const S = [];
    const index = new Array(this.numVertices).fill(null);
    const lowlink = new Array(this.numVertices).fill(null);
    const onStack = new Array(this.numVertices).fill(false);

    let i = 0;
    const strongconnect = (v) => {
        // Set the depth index for v to the smallest unused index
        index[v] = i;
        lowlink[v] = i;
        i++;
        S.push(v);
        onStack[v] = true;

        // Consider successors of v
        for (let w = 0; w < this.numVertices; w++) {
            if (this.hasEdgeBetweenIds(v, w)) {
                if (v === w)
                    console.log('self edge')
                if (index[w] == null) {
                    // Successor w has not yet been visited; recurse on it
                    strongconnect(w);
                    lowlink[v] = Math.min(lowlink[v], lowlink[w]);
                } else if (onStack[w]) {
                    // Successor w is in stack S and hence in the current SCC
                    // If w is not on stack, then (v, w) is an edge pointing to an SCC already found and must be ignored
                    // Note: The next line may look odd - but is correct.
                    // It says w.index not w.lowlink; that is deliberate and from the original paper
                    lowlink[v] = Math.min(lowlink[v], index[w]);
                }
            }
        }
        // If v is a root node, pop the stack and generate an SCC
        if (lowlink[v] === index[v]) {
            const cycle = [];
            let w;
            do {
                w = S.pop();
                onStack[w] = false;
                cycle.push(this.vertices[w]);
            } while (w !== v);

            if (cycle.length > 1) {
                cycles.push(cycle);
            }
        }
    };

    for (let v = 0; v < this.numVertices; v++) {
        if (index[v] == null) {
            strongconnect(v);
        }
    }

    return cycles;
}

[pkaminski]

Sorry about that -- nice catch! I think this was due to an early exit "optimization" in my findCycles loop that I must've made up all by myself, since I can't find any backing for it in Johnson's algorithm when I look now. I added your test case to the tests and it passes now (fix here).

Thanks for taking the time to implement Tarjan's on Becsy's data structures! I'm going to try sticking to my algorithm for now since it's not clear to me whether Tarjan's finds the smallest possible cycles or just any strongly connected components. (I want to find the smallest cycles as those are the most useful when debugging your system dependencies.)

Please let me know if you find another bug, though, and I'll most likely dump Johnson in favor of Tarjan. :)

I'll publish the fixed version later tonight as 0.10.0.

[calebj0seph]

Thanks @pkaminski, appreciate the super fast fix 😃