dep-graph.coffee

dep-graph

 
_ = 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 id

Second, order them (using the Tarjan algorithm)

 
    chain = []
    visited = {}
    visit = (node) =>
      return if visited[node] or node is id
      visited[node] = true
      for parent in @parentsOf(node)
        visit parent
      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