I have produced this GitHub repository that compares the performance of:
- Robert Tarjan's off-line lowest common ancestors algorithm,
- 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.
