1
\$\begingroup\$

I have produced this GitHub repository that compares the performance of:

  1. Robert Tarjan's off-line lowest common ancestors algorithm,
  2. An improvement of the above algorithm.

Typical demo program output

Seed: 1676201833609
Tree constructed in 0 milliseconds.
Number of nodes: 77487
com.github.coderodde.algo.lca.impl.TarjansOfflineLCAAlgorithm in 1039 milliseconds.
com.github.coderodde.algo.lca.impl.FasterTarjansOfflineLCAAlgorithm in 17 milliseconds.
Algorithms agree: true

As you can see from the output, the faster version requires, like, easily 30 times less of effort.

What comes to algorithm 2, I don't iterate all the queries, but instead constrain my search for those queries that share a currently recursed node.

Below is my code.

com.github.coderodde.algo.lca.OfflineLCAAlgorithm.java:

package com.github.coderodde.algo.lca;

import java.util.List;

/**
 * This interface defines the API for the offline lowest common ancestors
 * algorithms.
 * 
 * @param <E> the general tree node satellite datum type.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 */
public interface OfflineLCAAlgorithm<E> {
    
    /**
     * Process all the LCA queries and returns their respective results.
     * 
     * @param tree    tree to search in.
     * @param queries the list of queries to perform.
     * @return        the list of lowest common ancestors entries.
     */
    public List<LowestCommonAncestorResult<E>> 
        processQueries(GeneralTree<E> tree,
                       List<LowestCommonAncestorQuery<E>> queries);
}

com.github.coderodde.algo.lca.impl.TarjansOfflineLCAAlgorithm.java:

package com.github.coderodde.algo.lca.impl;

import com.github.coderodde.algo.lca.GeneralTree;
import com.github.coderodde.algo.lca.GeneralTreeNode;
import com.github.coderodde.algo.lca.LowestCommonAncestorQuery;
import com.github.coderodde.algo.lca.LowestCommonAncestorResult;
import com.github.coderodde.algo.lca.OfflineLCAAlgorithm;
import java.util.ArrayList;
import java.util.List;
import com.github.coderodde.util.disjointset.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm">Robert Tarjan's offline lowest common ancestors algorithm</a>.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 */
public final class TarjansOfflineLCAAlgorithm<E> 
        implements OfflineLCAAlgorithm<E> {

    private final DisjointSetRootFinder
            <GeneralTreeNode<E>> rootFinder = 
            new DisjointSetRootFinder<>();
    
    private final DisjointSetUnionComputer<GeneralTreeNode<E>> 
            unionComputer = new DisjointSetUnionComputer<>();
    
    public List<LowestCommonAncestorResult<E>> 
        processQueries(GeneralTree<E> root,
                       List<LowestCommonAncestorQuery<E>> queries) {
            
        List<LowestCommonAncestorResult<E>> lowestCommonAncestorsResults = 
                new ArrayList<>(queries.size());
        
        DisjointSet<GeneralTreeNode<E>> disjointSet = 
                new DisjointSet<>(
                        rootFinder,
                        unionComputer);
        
        Map<GeneralTreeNode<E>, GeneralTreeNode<E>> ancestorMap =
                new HashMap<>(queries.size());
        
        Set<GeneralTreeNode<E>> blackSet = 
                new HashSet<>(queries.size());
        
        tarjanOffLineLowestCommonAncestors(
                root.getRoot(), 
                lowestCommonAncestorsResults,
                queries,
                disjointSet,
                ancestorMap,
                blackSet);
        
        return lowestCommonAncestorsResults;
    }
        
    private void tarjanOffLineLowestCommonAncestors(
            GeneralTreeNode<E> node,
            List<LowestCommonAncestorResult<E>> lowestCommonAncestorsList,
            List<LowestCommonAncestorQuery<E>> queries,
            DisjointSet<GeneralTreeNode<E>> disjointSet,
            Map<GeneralTreeNode<E>, GeneralTreeNode<E>> ancestorMap,
            Set<GeneralTreeNode<E>> blackSet) {
        
        disjointSet.find(node);
        ancestorMap.put(node, node);
        
        for (GeneralTreeNode<E> child : node.getChildren()) {
            tarjanOffLineLowestCommonAncestors(
                    child, 
                    lowestCommonAncestorsList,
                    queries,
                    disjointSet,
                    ancestorMap,
                    blackSet);
            
            unionComputer.union(node, child);
            ancestorMap.put(rootFinder.find(node), node);
        }
        
        blackSet.add(node);
        
        for (LowestCommonAncestorQuery<E> pair : queries) {
            if (pair.queryContainsNode(node)) {
                GeneralTreeNode<E> v = pair.getOppositeNode(node);
                
                if (blackSet.contains(v)) {
                    LowestCommonAncestorResult<E> result =
                            new LowestCommonAncestorResult<>(
                                    pair.getFirstGeneralTreeNode(),
                                    pair.getSecondGeneralTreeNode(),
                                    ancestorMap.get(
                                            rootFinder.find(v)));
                    
                    lowestCommonAncestorsList.add(result);
                }
            }
        }
    }
}

com.github.coderodde.algo.lca.impl.FasterTarjansOfflineLCAAlgorithm.java:

package com.github.coderodde.algo.lca.impl;

import com.github.coderodde.algo.lca.GeneralTree;
import com.github.coderodde.algo.lca.GeneralTreeNode;
import com.github.coderodde.algo.lca.LowestCommonAncestorQuery;
import com.github.coderodde.algo.lca.LowestCommonAncestorResult;
import com.github.coderodde.algo.lca.OfflineLCAAlgorithm;
import java.util.ArrayList;
import java.util.List;
import com.github.coderodde.util.disjointset.*;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * This class improves on the 
 * {@link com.github.coderodde.algo.lca.impl.TarjansOfflineLCAAlgorithm} via 
 * caching queries.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 */
public final class FasterTarjansOfflineLCAAlgorithm<E> 
        implements OfflineLCAAlgorithm<E> {

    private final DisjointSetRootFinder
            <GeneralTreeNode<E>> rootFinder = 
            new DisjointSetRootFinder<>();
    
    private final DisjointSetUnionComputer<GeneralTreeNode<E>> 
            unionComputer = new DisjointSetUnionComputer<>();
    
    public List<LowestCommonAncestorResult<E>> 
        processQueries(GeneralTree<E> tree,
                       List<LowestCommonAncestorQuery<E>> queries) {
            
        List<LowestCommonAncestorResult<E>> lowestCommonAncestorsResults = 
                new ArrayList<>(queries.size());
        
        DisjointSet<GeneralTreeNode<E>> disjointSet = 
                new DisjointSet<>(
                        rootFinder,
                        unionComputer);
        
        Map<GeneralTreeNode<E>, GeneralTreeNode<E>> ancestorMap =
                new HashMap<>(queries.size());
        
        Set<GeneralTreeNode<E>> blackSet = 
                new HashSet<>(queries.size());
        
        Map<GeneralTreeNode<E>, Set<LowestCommonAncestorQuery<E>>> nodePairMap = 
                new HashMap<>();
        
        loadPairMap(nodePairMap, queries);
        
        tarjanOffLineLowestCommonAncestors(
                tree.getRoot(), 
                lowestCommonAncestorsResults,
                queries,
                disjointSet,
                ancestorMap,
                nodePairMap,
                blackSet);
        
        return lowestCommonAncestorsResults;
    }
        
    private void tarjanOffLineLowestCommonAncestors(
            GeneralTreeNode<E> node,
            List<LowestCommonAncestorResult<E>> lowestCommonAncestorsList,
            List<LowestCommonAncestorQuery<E>> queries,
            DisjointSet<GeneralTreeNode<E>> disjointSet,
            Map<GeneralTreeNode<E>, GeneralTreeNode<E>> ancestorMap,
            Map<GeneralTreeNode<E>, 
                Set<LowestCommonAncestorQuery<E>>> nodePairMap,
            Set<GeneralTreeNode<E>> blackSet) {
        
        disjointSet.find(node);
        ancestorMap.put(node, node);
        
        for (GeneralTreeNode<E> child : node.getChildren()) {
            tarjanOffLineLowestCommonAncestors(
                    child, 
                    lowestCommonAncestorsList,
                    queries,
                    disjointSet,
                    ancestorMap,
                    nodePairMap,
                    blackSet);
            
            unionComputer.union(node, child);
            ancestorMap.put(rootFinder.find(node), node);
        }
        
        blackSet.add(node);
        
        Set<LowestCommonAncestorQuery<E>> pairSet = nodePairMap.get(node);
        
        if (pairSet == null) {
            // Guard against the null values in the below for each loop.
            return;
        }
        
        for (LowestCommonAncestorQuery<E> pair : nodePairMap.get(node)) {
            if (pair.queryContainsNode(node)) {
                GeneralTreeNode<E> v = pair.getOppositeNode(node);
                
                if (blackSet.contains(v)) {
                    LowestCommonAncestorResult<E> result =
                            new LowestCommonAncestorResult<>(
                                    pair.getFirstGeneralTreeNode(),
                                    pair.getSecondGeneralTreeNode(),
                                    ancestorMap.get(
                                            rootFinder.find(v)));
                    
                    lowestCommonAncestorsList.add(result);
                }
            }
        }
    }
    
    private static <E> void loadPairMap(
            Map<GeneralTreeNode<E>, Set<LowestCommonAncestorQuery<E>>> pairMap, 
            List<LowestCommonAncestorQuery<E>> queries) {
        
        for (LowestCommonAncestorQuery<E> query : queries) {
            GeneralTreeNode<E> firstNode = query.getFirstGeneralTreeNode();
            GeneralTreeNode<E> secondNode = query.getSecondGeneralTreeNode();
            
            if (!pairMap.containsKey(firstNode)) {
                pairMap.put(firstNode, new HashSet<>());
            }
            
            pairMap.get(firstNode).add(query);
            
            if (!pairMap.containsKey(secondNode)) {
                pairMap.put(secondNode, new HashSet<>());
            }
            
            pairMap.get(secondNode).add(query);
        }
    }
}

com.github.coderodde.algo.lca.GeneralTree.java:

package com.github.coderodde.algo.lca;

import java.util.Objects;

/**
 * This class implements a general rooted tree.
 * 
 * @param <E> the satellite datum type. Relies on its {@code equals} and 
 *            {@code hashCode}.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 */
public final class GeneralTree<E> {
    
    private final GeneralTreeNode<E> root;
    
    public GeneralTree(GeneralTreeNode<E> root) {
        this.root = Objects.requireNonNull(
                root, 
                "The root node is null.");
    }
    
    public GeneralTreeNode<E> getRoot() {
        return root;
    }
}

com.github.coderodde.algo.lca.GeneralTreeNode.java:

package com.github.coderodde.algo.lca;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements a multibranched node in a general tree.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 */
public final class GeneralTreeNode<E> {
    
    /**
     * The set of child nodes.
     */
    private final Set<GeneralTreeNode<E>> children = new HashSet<>();
    
    /**
     * The satellite datum this node holds.
     */
    private final E datum;
    
    public GeneralTreeNode(E datum) {
        this.datum = Objects.requireNonNull(
                datum, 
                "The input datum is null.");
    }
    
    /**
     * Adds {@code child} to the child list of this node. This operation cannot
     * prevent directed cycles in the tree.
     * 
     * @param child the child node to add.
     */
    public void addChild(GeneralTreeNode<E> child) {
        children.add(child);
    }
    
    public E getDatum() {
        return datum;
    }
    
    public Collection<GeneralTreeNode<E>> getChildren() {
        return Collections.<GeneralTreeNode<E>>unmodifiableSet(children);
    }
    
    @Override
    public boolean equals(Object o) {
        GeneralTreeNode<E> other = (GeneralTreeNode<E>) o;
        return datum.equals(other.datum);
    }
    
    @Override
    public int hashCode() {
        return datum.hashCode();
    }
    
    @Override
    public String toString() {
        return new StringBuilder().append("[")
                                  .append(datum.toString())
                                  .append("]")
                                  .toString();
    }
}

com.github.coderodde.algo.lca.GeneralTreeBuilder.java:

package com.github.coderodde.algo.lca;

import java.util.Random;

/**
 * This class attempts to build a general tree with {@code requestedSize} nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 */
public final class GeneralTreeBuilder {
    
    private int id;
    private int actualSize = 1; // 1 for the root.
    private final int requestedSize;
    private final Random random;
    private final GeneralTree<Integer> tree = 
            new GeneralTree<>(new GeneralTreeNode<>(0));
    
    public GeneralTreeBuilder(int size, int depth, Random random) {
        this.requestedSize = size;
        this.random = random;
        buildImpl(tree.getRoot(), 5);
    }
    
    public GeneralTree<Integer> getTree() {
        return tree;
    }
    
    public int getActualSize() {
        return actualSize;
    }
    
    private void buildImpl(GeneralTreeNode<Integer> parent, int depth) {
        
        if (depth == -1 || actualSize >= requestedSize) {
            return;
        }
        
        int branches = random.nextInt(4, 10);
        
        for (int i = 0; i < branches; i++) {
            if (actualSize >= requestedSize) {
                return;
            }
            
            GeneralTreeNode<Integer> child = new GeneralTreeNode<>(++id);
            parent.addChild(child);
            actualSize++;
            
            buildImpl(child, depth - 1);
        }
    }
}

com.github.coderodde.algo.lca.Demo.java:

package com.github.coderodde.algo.lca;

import com.github.coderodde.algo.lca.impl.FasterTarjansOfflineLCAAlgorithm;
import com.github.coderodde.algo.lca.impl.TarjansOfflineLCAAlgorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

/**
 * This class implements the demo program/benchmark for comparing performance of
 * the two offline LCA algorithms in this project.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 12, 2023)
 * @since 1.6 (Feb 12, 2023)
 * @author Potilaskone
 */
public final class Demo {
    
    private static final int TREE_SIZE = 1_000_000;
    private static final int TREE_DEPTH = 10000;
    private static final int NUMBER_OF_QUERIES = 2000;
    
    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);
        System.out.println("Seed: " + seed);
        long startTime = System.currentTimeMillis();
        
        GeneralTreeBuilder builder = 
                new GeneralTreeBuilder(
                        TREE_SIZE,
                        TREE_DEPTH,
                        random);
        
        GeneralTree<Integer> tree = builder.getTree();
        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;
        System.out.println(
                "Tree constructed in " + duration + " milliseconds.");
        
        System.out.println("Number of nodes: " + builder.getActualSize());
        
        Map<Integer, GeneralTreeNode<Integer>> nodeMap = computeNodeMap(tree);
        List<LowestCommonAncestorQuery<Integer>> queries = 
                createRandomQueries(
                        builder, 
                        nodeMap,
                        NUMBER_OF_QUERIES, 
                        random);
        
        startTime = System.currentTimeMillis();
        
        List<LowestCommonAncestorResult<Integer>> results1 =
                profileLCAAlgorithm(
                        new TarjansOfflineLCAAlgorithm<>(), 
                        tree, 
                        queries);
        
        List<LowestCommonAncestorResult<Integer>> results2 =
                profileLCAAlgorithm(
                        new FasterTarjansOfflineLCAAlgorithm<>(), 
                        tree, 
                        queries);
        
        Set<LowestCommonAncestorResult<Integer>> resultSet1 = 
                new HashSet<>(results1);
        
        Set<LowestCommonAncestorResult<Integer>> resultSet2 = 
                new HashSet<>(results2);
        
        System.out.println("Algorithms agree: " + 
                resultSet1.equals(resultSet2));
    }
    
    private static GeneralTreeBuilder getGeneralTreeBuilder() {
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);
        
        System.out.println("Seed: " + seed);
        
        GeneralTreeBuilder builder = 
                new GeneralTreeBuilder(
                        TREE_SIZE, 
                        TREE_DEPTH,
                        random);
        
        GeneralTree<Integer> tree = builder.getTree();
        
        System.out.println("Tree size: " + builder.getActualSize());
        return builder;
    }
    
    private static Map<Integer, GeneralTreeNode<Integer>> 
        computeNodeMap(GeneralTree<Integer> tree) {
        Map<Integer, GeneralTreeNode<Integer>> nodeMap = 
                new HashMap<>(2 * TREE_SIZE);
        
        GeneralTreeNode<Integer> rootNode = tree.getRoot();
        nodeMap.put(rootNode.getDatum(), rootNode);
        
        for (GeneralTreeNode<Integer> child : rootNode.getChildren()) {
            computeNodeMapImpl(nodeMap, child);
        }
        
        return nodeMap;
    }
        
    private static void computeNodeMapImpl(
            Map<Integer, GeneralTreeNode<Integer>> nodeMap, 
            GeneralTreeNode<Integer> node) {
        
        nodeMap.put(node.getDatum(), node);
        
        for (GeneralTreeNode<Integer> child : node.getChildren()) {
            computeNodeMapImpl(nodeMap, child);
        }
    }

    private static List<LowestCommonAncestorQuery<Integer>> 
        createRandomQueries(GeneralTreeBuilder builder,
                            Map<Integer, GeneralTreeNode<Integer>> nodeMap,
                            int numberOfQueries,
                            Random random) {
            
        int sz = builder.getActualSize();
        List<LowestCommonAncestorQuery<Integer>> queries = new ArrayList<>();
        
        for (int i = 0; i < numberOfQueries; i++) {
            GeneralTreeNode<Integer> treeNode1 =
                    nodeMap.get(random.nextInt(sz));
            
            GeneralTreeNode<Integer> treeNode2 = 
                    nodeMap.get(random.nextInt(sz));
            
            LowestCommonAncestorQuery<Integer> query = 
                    new LowestCommonAncestorQuery<>(
                            treeNode1, 
                            treeNode2);
            
            queries.add(query);
        }
        
        return queries;
    }
        
    private static List<LowestCommonAncestorResult<Integer>> 
        profileLCAAlgorithm(
            OfflineLCAAlgorithm<Integer> algorithm, 
            GeneralTree<Integer> tree, 
            List<LowestCommonAncestorQuery<Integer>> queries) {
        
        long startTime = System.currentTimeMillis();
        
        List<LowestCommonAncestorResult<Integer>> results =
                algorithm.processQueries(tree, queries);
        
        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;
        System.out.println(
                algorithm.getClass().getName()
                        + " in "
                        + duration 
                        + " milliseconds.");
        
        return results;
    }
}

Critique request

I would like to hear anything that comes to mind, as always.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Perhaps you're also interested in Schieber&Vishkin's algorithm, which fills a couple of arrays of integers as its precomputation (in linear time) and then does each query in a constant number of integer operations. \$\endgroup\$
    – user555045
    Commented Feb 12, 2023 at 12:15
  • \$\begingroup\$ @harold Is it offline too? Anyway, I can’t afford the research paper. \$\endgroup\$
    – coderodde
    Commented Feb 12, 2023 at 12:40
  • \$\begingroup\$ Scihub then? It's also explained in The Art of Computer Programming volume 4A (fascicle 1) (section 7.1.3) so you can get it that way (there used to be a draft version freely available, but I couldn't find that now) \$\endgroup\$
    – user555045
    Commented Feb 12, 2023 at 12:53
  • \$\begingroup\$ @harold Could you provide me with the name of the article by Schieber & Vishkin? \$\endgroup\$
    – coderodde
    Commented Feb 12, 2023 at 16:24
  • \$\begingroup\$ On Finding Lowest Common Ancestors: Simplification and Parallelization doi.org/10.1137/0217079 \$\endgroup\$
    – user555045
    Commented Feb 12, 2023 at 23:10

0

Your Answer

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