find the lowest common ancestor in a directed, acyclic graph
JavaScript
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.travis.yml
LICENSE
README.md
index.js
package.json
test.js

README.md

#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
})