1
\$\begingroup\$

Now I have two algorithms solving a problem: given a general (multi-way) tree, and any array of node names, find the the node that is the deepest common ancestor.

LCAComputer.java:

package com.github.coderodde.generallca;

/**
 * This interface specifies the API for methods computing multiple node LCAs.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 19, 2022)
 */
public interface LCAComputer {
    
    GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                String... nodeNames);
}

LCAComputerV1.java:

package com.github.coderodde.generallca.impl;

import com.github.coderodde.generallca.GeneralTree;
import com.github.coderodde.generallca.GeneralTreeNode;
import com.github.coderodde.generallca.LCAComputer;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * This class provides a method for computing general lowest common ancestors.
 * For each query node {@code n}, the algorithm computes the path from 
 * {@code n} to the root node. Then, it marches along all the paths upwards 
 * towards the root node incrementing the counts of each visited nodes. The 
 * first node whose counter reaches the number of query nodes, is the LCA.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 18, 2022)
 */
public final class LCAComputerV1 implements LCAComputer {
    
    public GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                       String... nodeNames) {
        List<List<GeneralTreeNode>> paths = new ArrayList<>(nodeNames.length);
        
        for (int i = 0; i < nodeNames.length; ++i) {
            GeneralTreeNode node = tree.getNode(nodeNames[i]);
            Objects.requireNonNull(
                    node,
                    "There is no node with name '" + nodeNames[i] + "'.");
            
            paths.add(getPathToRoot(node));
        }
        
        Map<GeneralTreeNode, Integer> visitedMap = new HashMap<>();
        
        for (List<GeneralTreeNode> path : paths) {
            for (GeneralTreeNode node : path) {
                visitedMap.put(node, visitedMap.getOrDefault(node, 0) + 1);
                
                if (visitedMap.get(node) == nodeNames.length) {
                    return node;
                }
            }
        }
        
        throw new IllegalStateException("Should not get here.");
    }
    
    private List<GeneralTreeNode> getPathToRoot(GeneralTreeNode node) {
        List<GeneralTreeNode> path = new ArrayList<>();
        
        while (node != null) {
            path.add(node);
            node = node.getParent();
        }
        
        return path;
    }
}

LCAComputerV2.java

package com.github.coderodde.generallca.impl;

import com.github.coderodde.generallca.GeneralTree;
import com.github.coderodde.generallca.GeneralTreeNode;
import com.github.coderodde.generallca.LCAComputer;
import java.util.Arrays;

/**
 * 
 * This class provides a method for computing general lowest common ancestors.
 * The algorithm moves all the query nodes to the level of the shallowest node,
 * and keeps moving all the nodes until they all visit a single node, which is
 * a LCA.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 19, 2022)
 */
public final class LCAComputerV2 implements LCAComputer {

    @Override
    public GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                       String... nodeNames) {
        GeneralTreeNode[] nodes = new GeneralTreeNode[nodeNames.length];
        
        for (int i = 0; i < nodes.length; ++i) {
            nodes[i] = tree.getNode(nodeNames[i]);
        }
        
        Arrays.sort(
                nodes,
                (n1, n2) -> { 
                    return Integer.compare(n1.getDepth(), n2.getDepth());
                });
        
        int minimumDepth = nodes[0].getDepth();
        
        for (int i = 1; i < nodes.length; ++i) {
            while (nodes[i].getDepth() > minimumDepth) {
                nodes[i] = nodes[i].getParent();
            }
        }
        
        // Here, nodes points to the visited nodes at the minimum depth:
        while (!visitingOnlyOneNode(nodes)) {
            for (int i = 0; i < nodes.length; ++i) {
                nodes[i] = nodes[i].getParent();
            }
        }
        
        return nodes[0];
    }
    
    private boolean visitingOnlyOneNode(GeneralTreeNode[] nodes) {
        for (int i = 0; i < nodes.length - 1; ++i) {
            if (nodes[i] != nodes[i + 1]) {
                return false;
            }
        }
        
        return true;
    }
}

GeneralTreeNode.java:

package com.github.coderodde.generallca;

import java.util.Objects;

/**
 * This class implements a node for general trees. It allows any number of 
 * child nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 18, 2022)
 */
public final class GeneralTreeNode {
    
    private final String name;
    private final int depth;
    private GeneralTreeNode parent;
    
    GeneralTreeNode(String name, int depth, GeneralTreeNode parent) {
        this.name = name;
        this.depth = depth;
        this.parent = parent;
    }
    
    public int getDepth() {
        return depth;
    }
    
    public String getName() {
        return name;
    }
    
    public GeneralTreeNode getParent() {
        return parent;
    }
    
    public void setParent(GeneralTreeNode parent) {
        this.parent = parent;
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof GeneralTreeNode)) {
            return false;
        }
        
        GeneralTreeNode other = (GeneralTreeNode) o;
        return name.equals(other.name);
    }

    @Override
    public int hashCode() {
        // Generated by NetBeans IDE 12.6
        int hash = 7;
        hash = 19 * hash + Objects.hashCode(this.name);
        return hash;
    }
}

GeneralTree.java:

package com.github.coderodde.generallca;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 *
 * @author rodde
 */
public final class GeneralTree {
    
    private final Map<String, GeneralTreeNode> treeNodeMap = new HashMap<>();
    private GeneralTreeNode root;
    
    public GeneralTreeNode getNode(String name) {
        return treeNodeMap.get(name);
    }
    
    public void addRootNode(String name) {
        Objects.requireNonNull(name, "The node name is null.");
        
        if (treeNodeMap.containsKey(name)) {
            throw new IllegalArgumentException(
                    "The node named '" + name + "' is already in this tree.");
        }
        
        root = new GeneralTreeNode(name, 0, null);
        treeNodeMap.put(name, root);
    }
    
    public void addNode(String childNodeName, String parentNodeName) {
        GeneralTreeNode parentNode = treeNodeMap.get(parentNodeName);
        Objects.requireNonNull(parentNode, "The parent node is null.");
        
        GeneralTreeNode childNode = 
                new GeneralTreeNode(
                        childNodeName, 
                        parentNode.getDepth() + 1, 
                        parentNode);
        
        treeNodeMap.put(childNodeName, childNode);
    }
}

BenchmarkApp.java:

package com.github.coderodde.generallca;

import com.github.coderodde.generallca.impl.LCAComputerV1;
import com.github.coderodde.generallca.impl.LCAComputerV2;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public final class BenchmarkApp {
    
    private static final int NUMBER_OF_TREE_NODES = 1000_000;
    private static final int NUMBER_OF_QUERIES = 100_000;
    private static final int MAXIMUM_QUERY_LENGTH = 50;
    
    private final long seed;
    private final GeneralTree tree = new GeneralTree();
    private final LCAComputer lcaComputerV1 = new LCAComputerV1();
    private final LCAComputer lcaComputerV2 = new LCAComputerV2();
    
    public BenchmarkApp(long seed) {
        this.seed = seed;
        buildTree();
    }
    
    public void warmup() {
        doRun(false);
    }
    
    public void benchmark() {
        doRun(true);
    }
    
    private void doRun(boolean print) {
        Random random = new Random(seed);
        List<GeneralTreeNode> result1 = new ArrayList<>(NUMBER_OF_QUERIES);
        List<GeneralTreeNode> result2 = new ArrayList<>(NUMBER_OF_QUERIES);
        String[][] queries = getQueries();
        
        long startTime = System.currentTimeMillis();
        
        for (int i = 0; i < NUMBER_OF_QUERIES; ++i) {
            result1.add(
                    lcaComputerV1.computeLowestCommonAncestor(
                            tree,
                            queries[i]));
        }
        
        long endTime = System.currentTimeMillis();
        
        if (print) {
            long duration = endTime - startTime;
            
            System.out.println(
                    lcaComputerV1.getClass().getSimpleName() 
                            + " in " 
                            + duration 
                            + " milliseconds.");
        }
        
        startTime = System.currentTimeMillis();
        
        for (int i = 0; i < NUMBER_OF_QUERIES; ++i) {
            result2.add(
                    lcaComputerV2.computeLowestCommonAncestor(
                            tree,
                            queries[i]));
        }
        
        endTime = System.currentTimeMillis();
        
        if (print) {
            long duration = endTime - startTime;
            
            System.out.println(
                    lcaComputerV2.getClass().getSimpleName() 
                            + " in " 
                            + duration 
                            + " milliseconds.");
            
            System.out.println("Algorithms agree: " + result1.equals(result2));
        }
    }
    
    private void buildTree() {
        Random random = new Random(this.seed);
        List<GeneralTreeNode> createdNodeList = new ArrayList<>();
        tree.addRootNode("Root");
        GeneralTreeNode root = tree.getNode("Root");
        createdNodeList.add(root);
        
        for (int i = 1; i < NUMBER_OF_TREE_NODES; ++i) {
            String childName = Integer.toString(i);
            int index = random.nextInt(createdNodeList.size());
            GeneralTreeNode parentNode = createdNodeList.get(index);
            tree.addNode(childName, parentNode.getName());
            createdNodeList.add(tree.getNode(childName));
        }
    }
    
    private String[][] getQueries() {
        String[][] queries = new String[NUMBER_OF_QUERIES][];
        
        for (int i = 0; i < NUMBER_OF_QUERIES; ++i) {
            queries[i] = generateQuery();
        }
        
        return queries;
    }
    
    private String[] generateQuery() {
        Random random = new Random(this.seed);
        int queryLength = random.nextInt(MAXIMUM_QUERY_LENGTH) + 1;
        String[] query = new String[queryLength];
        
        for (int i = 0; i < query.length; ++i) {
            query[i] = Integer.toString(random.nextInt(NUMBER_OF_TREE_NODES));
        }
        
        return query;
    }
}

Demo.java:

package com.github.coderodde.generallca;

public final class Demo {
    
    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        System.out.println("--- Seed = " + seed + " ---");
        
        BenchmarkApp app = new BenchmarkApp(seed);
        
        System.out.println(">>> Warming up...");
        app.warmup();
        
        System.out.println(">>> Warming up done.");
        System.out.println();
        
        System.out.println(">>> Benchmarking...");
        app.benchmark();
        
        System.out.println(">>> Benchmarking done.");
    }
}

LCAComputerTest.java:

package com.github.coderodde.generallca;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class LCAComputerTest {

    final LCAComputer lcaComputer;
    
    public LCAComputerTest(LCAComputer lcaComputer) {
        this.lcaComputer = lcaComputer;
    }
    
    @Test
    public void testComputeLowestCommonAncestor() {
        GeneralTree tree = new GeneralTree();
        
        tree.addRootNode("A");
        
        tree.addNode("B", "A");
        tree.addNode("C", "A");
        
        tree.addNode("D", "B");
        tree.addNode("E", "B");
        
        tree.addNode("F", "C");
        tree.addNode("G", "C");
        
        tree.addNode("H", "G");
        tree.addNode("I", "G");
        tree.addNode("J", "G");
        
        //                  A
        //                 / \
        //                /   \
        //               B     C
        //              / \   / \
        //             D   E F   G
        //                      /|\
        //                     H I J
        
        assertEquals(tree.getNode("A"), 
                     lcaComputer.computeLowestCommonAncestor(tree, "D", "H"));
        
        assertEquals(tree.getNode("G"), 
                     lcaComputer.computeLowestCommonAncestor(tree,
                                                             "I",
                                                             "H", 
                                                             "J"));
        
        assertEquals(tree.getNode("C"), 
                     lcaComputer.computeLowestCommonAncestor(tree, "F", "G"));
        
        assertEquals(tree.getNode("A"), 
                     lcaComputer.computeLowestCommonAncestor(
                             tree,
                             "D", "H", "G", "F"));
    }
}

LCAComputerV1Test.java:

package com.github.coderodde.generallca;

import com.github.coderodde.generallca.impl.LCAComputerV1;

public class LCAComputerV1Test extends LCAComputerTest {
    
    public LCAComputerV1Test() {
        super(new LCAComputerV1());
    }    
}

LCAComputerV2Test.java:

package com.github.coderodde.generallca;

import com.github.coderodde.generallca.impl.LCAComputerV2;

public class LCAComputerV2Test extends LCAComputerTest {
    
    public LCAComputerV2Test() {
        super(new LCAComputerV2());
    }    
}

Critique request

Please, tell me anything that comes to mind. Thank you in advance.

\$\endgroup\$
1
  • \$\begingroup\$ new Random(this.seed) would be better in getQueries() than in generateQuery(). (There is a similar glitch in the benchmark data preparation for your trie - Strings "48" - "57" instead of "0"-"9".) \$\endgroup\$
    – greybeard
    Mar 19, 2022 at 12:48

1 Answer 1

1
\$\begingroup\$

Programming "against" interfaces - way to go.
In LCAComputer I'd appreciate a definition whether for a node n and its parent p the LCA is p or p's parent.
(I'd prefer LCAfinder & lowestCommonAncestor().
 I'm undecided whether I'd prefer a bunch of nodes over a bunch of names - have both?
 If I was into Java stream processing, I'd ponder to offer just pair of whatever.
)
GeneralTree & GeneralTreeNode:
I'd appreciate interfaces.
I'm used to tree operations to start at the root/a node in case of recursive ones.
I expect to be able to iterate the children of a node.

LCAComputerV1&2
I see collecting items to process instead of processing them right away.

In visitingOnlyOneNode() (foundLCA()?), I might use

if (nodes.length <= 1)
    return true;
final GeneralTreeNode first = nodes[0];
for (int i = 1 ; i < nodes.length ; i++) {
    if (nodes[i] != first) {
        return false;
    }
}

Keeping it simple performed well with Random moved to getQueries():

   /* - pick a champion
    * - for every possible challenger, find LCA
    * - early out on <code>champion.getDepth()</code> 0
    */
    public GeneralTreeNode computeLowestCommonAncestor(GeneralTree tree,
                                                       String... nodeNames) {
        if (null == tree || null == nodeNames || 0 == nodeNames.length)
            return null;
        GeneralTreeNode
            champion = tree.getNode(nodeNames[nodeNames.length-1]);
        for (String name: nodeNames) {
            GeneralTreeNode challenger = tree.getNode(name);
            while (champion.getDepth() < challenger.getDepth())
                challenger = challenger.getParent();
            while (challenger.getDepth() < champion.getDepth())
                champion = champion.getParent();
            while (champion != challenger) {
                champion = champion.getParent();
                challenger = challenger.getParent();
            }
            if (0 == champion.getDepth())
                return champion;
        }
        return champion;
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.