Cyclic "dependency detection" in JavaScript

Question

I have written some simple code to detect cyclic dependencies for a module loading system and I'd like some feedback on how I can go about improving it. The code itself finds the first cycle in the dependency graph that starts at the provided node and returns a list of all of the nodes traversed along the way.

Here's an example:

The white node is the one we are starting the traversal at. The JS representation of this graph would look like this:

{
  'A': ['B', 'C'],
  'B': [],
  'C': ['D'],
  'D': ['A']
}

The output from my function is ['A', 'C', 'D', 'A'], which is a list of the nodes traversed before finding a cycle.

Here is the code I have written to generate the array:

function findCyclicDependencies(definitions, identifier) {
  var stack = [];

  // Internal search function.
  var internalSearch = function(currentIdentifier) {

    // If we have visited this node, return whether or not it is the one we
    // are looking for.
    if (stack.indexOf(currentIdentifier) !== -1) {
      return currentIdentifier === identifier;
    }

    stack.push(currentIdentifier);

    // Check all of the child nodes to see if they contain the node we are
    // looking for.
    var found = definitions[currentIdentifier].some(internalSearch);

    // Remove the current node from the stack if it's children do not
    // contain the node we are looking for.
    if (!found) {
      stack.splice(stack.indexOf(currentIdentifier), 1);
    }

    return found;
  };

  // If there isn't a cyclic dependency then we return an empty array,
  // otherwise we return the stack.
  return internalSearch(identifier) ? stack.concat(identifier) : [];
}

And some not-so great code for doing the tests:

[
  {
    name: 'Non-cyclic',
    definitions: {
      'A': ['B', 'C'],
      'B': [],
      'C': ['D'],
      'D': []
    },
    identifier: 'A',
    expected: []
  },
  {
    name: 'Cyclic',
    definitions: {
      'A': ['B', 'C'],
      'B': [],
      'C': ['D'],
      'D': ['A']
    },
    identifier: 'A',
    expected: ['A', 'C', 'D', 'A']
  }
].forEach(function(test) {
  var result = findCyclicDependencies(test.definitions, test.identifier),
      passed = true;

  if (test.expected.length === result.length) {
    for (var i = 0; i < test.expected.length; i++) {
      if (test.expected[i] !== result[i]) {
        passed = false;
        break;
      }
    }
  } else {
    passed = false;
  }

  if (passed) {
    console.log(test.name + ': pass');
  } else {
    var message = test.name + ': fail\n' +
                  '  Got: ' + JSON.stringify(result) + '\n' +
                  '  Expected: ' + JSON.stringify(test.expected);

    console.warn(message);
  }
});

I'm not all that bothered about the quality of the test code as it's mainly for demonstration purposes to show my function works.

One thing I'm not sure about with my code (that I'm not even sure is in the scope of Code Review):

Is there any case where found is false but the stack doesn't contain currentIdentifier (i.e. stack.indexOf(currentIdentifier) === -1? I'm wondering if I need to check whether or not currentIdentifier is in the stack before trying to remove it, as trying to remove something not present ends up with the last element being removed erroneously (indexOf returns -1 and splice(-1, 1) removes the last element from the array).

Answer 1

HashMap of visited nodes is more efficient than array lookup

First of I'd like to acknowledge that I think you've done a fantastic job so far. Your code is thought out really well and from my tests appears to be rock solid. My biggest concern is that using Array.indexOf() isn't as efficient as storing a map of visited nodes:

var visited= {};

if (visited[node]) {
  return;
}
visited[node] = true;
definitions[node].some(internalSearch);

Not only does the map have O(1) lookup--which is nice--but it also would prevent some redundant searches. For example, take a look at the following case:

definitions = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D'],
  'D': []
}

Here's a JSFiddle that shows how node D is checked twice. That doesn't seem like a lot, but the more the dependency tree's branches weave the more redundancy that's introduced:

definitions = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D'],
  'D': ['E', 'F']
  'E': ['G']
  'F': ['G']
  'G': ['H', 'I'],
  'H': ['J'],
  'I': ['J'],
  'J': ['K', 'L'],
  'K': ['M'],
  'L': ['M'],
  'M': []
}

Here's the JSFiddle for this case. Note how M is checked 16 times!

Of course, your module loader may never run into such test cases, but IMO, the time it would take to implement the map is well worth the increase in your algorithm's efficiency.

Redundant comments

I'm not sure if you're just trying to help explain what your code does for code review, but comments like:

// Internal search function.
var internalSearch = function(currentIdentifier) {

don't really contribute to understanding; the code is self explanatory. Your code could be much shorter without the comments, so consider which of your comments actually adds value to the code. Anything else may just be clutter.

---

No faulty case

As of your concern, I'm pretty confident that currentIdentifier, will always be in the stack when you call for it to be removed. My reasoning is as follows:

Proof - First, you check to see if a node, A is on the stack:

• A is on the stack:
  1. return, the stack is unaffected
• A is not yet on the stack:
  1. A is pushed onto the stack [ ..., A]
  2. Call internalSearch on each child, C, consider the three cases of children:
     • If C === A then C is found on the stack because A is on the stack:
       1. return, the stack is unaffected
     • If C !== A and C is not found the stack:
       1. Add C to the stack `[ ..., A, C, ... ]
       2. Call internalSearch on each of C's children
       3. Remove C from the stack [ ..., `A, ... ]
       4. return
     • If C !== A and is found on the stack:
       1. return, the stack is unaffected
  3. Remove A from the stack [ ... ]

The only way for the stack to have the currentIdentifier removed would be if one of it's decedents were equal to it, but because you check the stack at the top of each call to internalSearch, you never deal with a duplicate node, so this will never happen.