λ Lowest common ancestor

======= Algorithm ======= <syntax js> function LowestCommonAncestor(nodeA, nodeB) { // Find all of `nodeA`s parents. var lca = null; var nodeAParents = new Set(); while (nodeA) { nodeAParents.add(nodeA); nodeA = nodeA.parent; } // Find the first intersection with `nodeB`s parents. while (nodeB) { if (nodeAParents.has(nodeB)) { lca = nodeB; break; } nodeB = nodeB.parent; } return lca; }</syntax> ======= Support ======= <syntax js> // Quick and dirty set. function Set() { var items = []; this.add = function(x) { items.push(x); return this; } this.has = function(x) { return items.indexOf(x) !== -1; } } function run(args) { result = LowestCommonAncestor(args[0], args[1]); } </syntax> ======= Tests ======= <syntax js> function testLCARoot() { var root = {}; var nodeA = {parent:root}; var nodeB = {parent:root}; assert( LowestCommonAncestor(nodeA, nodeB) === root ); } function testLCA() { var root = {}; var nodeA = {parent:root}; var nodeB = {parent:nodeA}; var nodeC = {parent:nodeA}; var nodeD = {parent:nodeC}; /* R | A / \ B C | D */ assert( LowestCommonAncestor(nodeD, nodeB) === nodeA ); assert( LowestCommonAncestor(nodeD, nodeD) === nodeD ); assert( LowestCommonAncestor(nodeA, nodeD) === nodeA ); assert( LowestCommonAncestor(nodeD, nodeC) === nodeC ); assert( LowestCommonAncestor(nodeC, nodeD) === nodeC ); } function testLCANone() { var root = {}; var root2 = {}; var nodeA = {parent:root}; var nodeB = {parent:root2}; assert( LowestCommonAncestor(nodeA, nodeB) === null, "LCA of two separate nodes is null."); }</syntax> ======= Options ======= <syntax js> { "height":"360px", "title":"Lowest common ancestor" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g.node { font-family: Verdana, Helvetica; font-size: 12px; font-weight: bold; } circle.node-dot { fill: white; stroke: red; stroke-width: 1px; } g.childAPath circle.node-dot { fill: #FAA; stroke: blue; } g.childAIterator circle.node-dot { fill: #F33; stroke: blue; } g.childBIterator circle.node-dot { fill: #33F; stroke: blue; } g.childA circle.node-dot { fill: #F66; stroke: blue; } g.childB circle.node-dot { fill: #66F; stroke: blue; } path.link { fill: none; stroke: gray; } body {margin:0px} </style> <script src="http://d3js.org/d3.v2.js"></script> <script> var maxNodes = 10; var treeData; var childA; var childB; function newTree() { treeData = {data:Math.floor(Math.random()*20), children:[], parent:null}; var allNodes = [treeData]; // generate a random tree for (var i=0; i<maxNodes; i++) { var child = {data:Math.floor(Math.random()*20), children:[]}; var parent = allNodes[Math.floor(allNodes.length*Math.random())]; parent.children.push(child); child.parent = parent; allNodes.push(child); } childA = allNodes[allNodes.length-1]; childB = allNodes[allNodes.length-2]; buildTree("#tree-container"); if (window.reset) reset(); } var layoutRoot = null; function buildTree(containerName) { // size of the diagram var size = { width:300, height: 250}; var tree = d3.layout.tree() .sort(null) .size([size.width, size.height-40]) .children(function(d) { return d.children; }); var nodes = tree.nodes(treeData); var links = tree.links(nodes); // root if (!layoutRoot) { layoutRoot = d3.select(containerName) .append("svg:svg").attr("width", size.width).attr("height", size.height) .append("svg:g") .attr("class", "container") .attr("transform", "translate(0,20)"); } else { layoutRoot.selectAll("path.link").remove(); layoutRoot.selectAll("g.node").remove(); } // Edges between nodes as a <path class="link" /> var link = d3.svg.diagonal(); layoutRoot.selectAll("path.link") .data(links) .enter() .append("svg:path") .attr("class", "link") .attr("d", link); layoutRoot.selectAll("path.link").each(function(d) {d.link = this;}); // nodes var nodeGroup = layoutRoot.selectAll("g.node") .data(nodes) .enter() .append("svg:g") .attr("class", "node") .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); nodeGroup.append("svg:circle") .attr("class", "node-dot") .attr("r", 15); nodeGroup.append("svg:text") .attr("dy", 4) .text(function(d) { return d.data; }) .attr("text-anchor", "middle"); } function update(n, x, isRunning, duration, $prev) { var childAIterator = x.lookupInScope("nodeA"); var childAParents = x.lookupInScope("nodeAParents"); var childBIterator = x.lookupInScope("nodeB"); var result = x.lookupInScope("result"); d3.selectAll("g.node") .classed("childAIterator", function(d) {return d===childAIterator;}); d3.selectAll("g.node") .classed("childBIterator", function(d) {return d===childBIterator || (x.stack.length < 2 && d===result);}); d3.selectAll("g.node") .classed("childA", function(d) {return d===childA;}); d3.selectAll("g.node") .classed("childAPath", function(d) {return childAParents && childAParents.has(d);}); d3.selectAll("g.node") .classed("childB", function(d) {return d===childB;}); } function args() { return [childA, childB]; } </script> </head> <body onload="newTree()"> <div id="tree-container" style="position:relative"> <button onclick="newTree()" style="position:absolute;left:0px;top:0px">New Tree</button> </div> </body> </html></syntax>