Doesn't always detect cycles

[sandfox]

example code speaks better than words

var DepGraph = require('dependency-graph').DepGraph;

// some arbitrary modules with dependencies
var mods = [
    {name: 'a', deps: []},
    {name: 'b', deps: ['a', 'd']},
    {name: 'c', deps: ['a', 'b']},
    {name: 'd', deps: ['c']}
];

// Helper functions

function _addNode(mod){
  depGraph.addNode(mod.name);
}

function _addEdge(mod){
    function _reallyAddEdge(dep){
      console.log(mod.name + ' -> ' + dep);
      depGraph.addDependency(mod.name, dep);
    }
    mod.deps.forEach(_reallyAddEdge);
}

mods.forEach(_addNode);
mods.forEach(_addEdge);

//this really should explode... but doesn't
console.log(depGraph.overallOrder())
//[ 'a' ]

//this does however cause it to explode
console.log(depGraph.dependantsOf('b'))
/Users/sandfox/code/bizzby/bizzby/node_modules/dependency-graph/lib/dep_graph.js:26
        throw new Error('Dependency Cycle Found: ' + currentPath.join(' -> '))
              ^
Error: Dependency Cycle Found: b -> c -> d -> b
    at /Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:26:15
    at Array.forEach (native)
    at DFS (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:21:17)
    at /Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:23:9
    at Array.forEach (native)
    at DFS (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:21:17)
    at /Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:23:9
    at Array.forEach (native)
    at DFS (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:21:17)
    at Object.DepGraph.dependantsOf (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:147:7)

I think that should be enough but let me know if it's not clear or doesn't make any sense.

EDIT----

Think I have found the/a problem..

TL;DR

the overallOrder function checks every node to find one that is not a dependency of another node, and when that fails just checks the first node to find it's dependencies, even though the first node maybe a leaf (based upon on outgoingEdges)

so, in overallOrder it tries to find a node to start from by checking for a node with 0 incomingEdges (things that are immediately dependent on that node). but every node in my example is a dependency (which means it's cyclic), so the code realises it can't find a starting point and so to find the cyclic dependency it just takes the first node and tries search through it's outgoingEdges (things it is immediately dependent on) and find the cycle that way. This is all groovy and everything unless your first node isn't in the middle of the cycle and is just a leaf node.

I think I can add a small fix to make sure that at least an error gets thrown when trying to render overall order.

[jriecken]

Thanks for the very detailed issue description! I'll take a look at your pull request tonight.

[jriecken]

I've fixed this in a way that will always detect cycles even if there are several disconnected subgraphs (and one of the doesn't have a cycle) and include the correct cycle information in the error message.

I've pushed version 0.4.1 to npm

[sandfox]

Cool, I'm glad you could make something of my rambling, I'm still pretty new to DAGs. Yeah, you're fix is a lot cleaner! Thanks for this.