_ = require 'underscore'
class DepGraph
constructor: ->
_ = require 'underscore'
class DepGraph
constructor: ->The internal representation of the dependency graph in the format
id: [ids], indicating only direct dependencies.
@map = {}Add a direct dependency. Returns false if that dependency is a duplicate.
add: (id, depId) ->
@map[id] ?= []
return false if depId in @map[id]
@map[id].push depId
@map[id]Generate a list of all dependencies (direct and indirect) for the given id, in logical order with no duplicates.
getChain: (id) ->First, get a list of all dependencies (unordered)
deps = @descendantsOf idSecond, order them (using the Tarjan algorithm)
chain = []
visited = {}
visit = (node) =>
return if visited[node] or node is id
visited[node] = true
visit parent for parent in @parentsOf(node) when parent in deps
chain.unshift node
for leafNode in _.intersection(deps, @leafNodes()).reverse()
visit leafNode
chain
leafNodes: ->
allNodes = _.uniq _.flatten _.values @map
node for node in allNodes when !@map[node]?.length
parentsOf: (child) ->
node for node in _.keys(@map) when child in @map[node]
descendantsOf: (parent, descendants = [], branch = []) ->
descendants.push parent
branch.push parent
for child in @map[parent] ? []
if child in branch # cycle
throw new Error("Cyclic dependency from #{parent} to #{child}")
continue if child in descendants # duplicate
@descendantsOf child, descendants, branch.slice(0)
descendants[1..]Export the class in Node, make it global in the browser.
if module?.exports?
module.exports = DepGraph
else
@DepGraph = DepGraph