TypeScript

by tedbeer

HTML

<div id="app"></div>

TypeScript

let parentChildPairs1 = [
    [1, 3], [2, 3], [3, 6], [5, 6],
    [5, 7], [4, 5], [4, 8], [8, 10]
];

let parentChildPairs2 = [
    [10, 2], [10, 5], [1, 3], [2, 3],
    [3, 4], [5, 6], [5, 7], [7, 8]
];
const _ = require('lodash');

const findAncestors = (graph, startNode) => {
  const findParents = (arr, node) => arr.filter(rel => rel[1] === node).map(rel => rel[0]);

  const ancestors = [];
  let parents = findParents(graph, startNode);
  ancestors.push(...parents);

  parents.forEach(node => ancestors.push(...findAncestors(graph, node)));
  return ancestors;
}

function hasCommonAncestor(arr, node1, node2) {
  const ancestors1 = findAncestors(arr, node1);
  const ancestors2 = findAncestors(arr, node2);
  return _.intersection(ancestors1, ancestors2).length > 0;
}


console.log(hasCommonAncestor(parentChildPairs1, 3, 8));// => false
console.log(hasCommonAncestor(parentChildPairs1, 5, 8));// => true
console.log(hasCommonAncestor(parentChildPairs1, 6, 8));// => true
console.log(hasCommonAncestor(parentChildPairs1, 1, 3));// => false
console.log(hasCommonAncestor(parentChildPairs1, 6, 5));// => true

console.log(hasCommonAncestor(parentChildPairs2, 4, 8)); // true
console.log(hasCommonAncestor(parentChildPairs2, 1, 6)); // false