ancestor

find the lowest common ancestor in a directed, acyclic graph

npm install ancestor
12 downloads in the last week
20 downloads in the last month

Lowest Common Ancestor

Build Status

NPM

Find the lowest common ancestor for directed, acyclic graphs in JavaScript.

var findAncestor = require('ancestor')

var nodes = {
  1: [],
  2: [1],
  3: [2],
  4: [2],
  5: [4],
  6: [3, 5],
  7: [6],
  8: [5],
  9: [8]
}

/* the graph:

    4-5-8-9   
   /   \
1-2-3---6-7

*/

var readParents = function(id, cb) {
  cb(null, nodes[id])
}

findAncestor([9, 7], readParents, function(err, res) {
  // res = 5
})
npm loves you