ancestor

find the lowest common ancestor in a directed, acyclic graph

#Lowest Common Ancestor

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(idcb) {
  cb(null, nodes[id])
}
 
findAncestor([9, 7], readParents, function(errres) {
  // res = 5 
})