Back to Repositories

Testing Lowest Common Ancestor Euler Tour Implementation in Algorithms Repository

This test suite validates the Lowest Common Ancestor (LCA) implementation using Euler Tour technique in a tree data structure. It ensures correct ancestor identification in various tree configurations and compares results against a reference implementation.

Test Coverage Overview

The test suite provides comprehensive coverage of LCA calculations in tree structures:

Predefined tree structure validation with known LCA values
Same-node LCA verification
Randomized tree generation and LCA queries
Edge cases including root node, leaf nodes, and adjacent nodes
Performance comparison with alternative LCA implementation

Implementation Analysis

The testing approach employs JUnit Jupiter framework with systematic validation patterns:

Tree construction helper methods for consistent test scenarios
Assertion-based verification using Google Truth library
Randomized testing for thorough validation
Comparative testing against reference implementation

Technical Details

Testing infrastructure includes:

JUnit Jupiter test framework
Google Truth assertion library
Custom tree generation utilities
Random test data generation
Tree node wrapper classes for different implementations

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Isolated test cases with clear purpose
Comprehensive edge case coverage
Randomized testing for robust validation
Helper methods for test data setup
Comparative testing for implementation verification

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/graphtheory/treealgorithms/LowestCommonAncestorEulerTourTest.java

            
package com.williamfiset.algorithms.graphtheory.treealgorithms;

import static com.google.common.truth.Truth.assertThat;

import java.util.*;
import org.junit.jupiter.api.*;

public class LowestCommonAncestorEulerTourTest {

  private LowestCommonAncestorEulerTour.TreeNode createFirstTreeFromSlides() {
    int n = 17;
    List<List<Integer>> tree = LowestCommonAncestorEulerTour.createEmptyGraph(n);

    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 0, 1);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 0, 2);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 1, 3);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 1, 4);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 2, 5);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 2, 6);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 2, 7);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 3, 8);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 3, 9);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 5, 10);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 5, 11);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 7, 12);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 7, 13);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 11, 14);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 11, 15);
    LowestCommonAncestorEulerTour.addUndirectedEdge(tree, 11, 16);

    return LowestCommonAncestorEulerTour.TreeNode.rootTree(tree, 0);
  }

  @Test
  public void testLcaTreeFromSlides1() {
    LowestCommonAncestorEulerTour.TreeNode root = createFirstTreeFromSlides();
    LowestCommonAncestorEulerTour fastSolver = new LowestCommonAncestorEulerTour(root);
    assertThat(fastSolver.lca(14, 13).index()).isEqualTo(2);
    assertThat(fastSolver.lca(10, 16).index()).isEqualTo(5);
    assertThat(fastSolver.lca(9, 11).index()).isEqualTo(0);
  }

  @Test
  public void testLcaTreeFromSlides2() {
    LowestCommonAncestorEulerTour.TreeNode root = createFirstTreeFromSlides();
    LowestCommonAncestorEulerTour fastSolver = new LowestCommonAncestorEulerTour(root);
    assertThat(fastSolver.lca(8, 9).index()).isEqualTo(3);
    assertThat(fastSolver.lca(4, 8).index()).isEqualTo(1);
    assertThat(fastSolver.lca(6, 13).index()).isEqualTo(2);
    assertThat(fastSolver.lca(7, 13).index()).isEqualTo(7);
    assertThat(fastSolver.lca(10, 5).index()).isEqualTo(5);
    assertThat(fastSolver.lca(2, 16).index()).isEqualTo(2);
  }

  @Test
  public void testLcaOfTheSameNodeIsItself() {
    LowestCommonAncestorEulerTour.TreeNode root = createFirstTreeFromSlides();
    LowestCommonAncestorEulerTour fastSolver = new LowestCommonAncestorEulerTour(root);

    // Try all nodes
    for (int id = 0; id < root.size(); id++) {
      assertThat(fastSolver.lca(id, id).index()).isEqualTo(id);
    }
  }

  @Test
  public void randomizedLcaQueriesVsOtherImpl() {
    for (int n = 1; n < 1000; n++) {
      List<List<Integer>> g = generateRandomTree(n);

      LowestCommonAncestor.TreeNode root1 = LowestCommonAncestor.TreeNode.rootTree(g, 0);
      LowestCommonAncestorEulerTour.TreeNode root2 =
          LowestCommonAncestorEulerTour.TreeNode.rootTree(g, 0);

      LowestCommonAncestor slowSolver = new LowestCommonAncestor(root1);
      LowestCommonAncestorEulerTour fastSolver = new LowestCommonAncestorEulerTour(root2);

      for (int i = 0; i < 100; i++) {
        int l = (int) (Math.random() * n);
        int r = (int) (Math.random() * n);
        int L = Math.min(l, r);
        int R = Math.max(l, r);

        LowestCommonAncestor.TreeNode lca1 = slowSolver.lca(L, R);
        LowestCommonAncestorEulerTour.TreeNode lca2 = fastSolver.lca(L, R);

        assertThat(lca1).isNotNull();
        assertThat(lca2).isNotNull();
        assertThat(lca1.id()).isEqualTo(lca2.index());
      }
    }
  }

  public static List<List<Integer>> generateRandomTree(int n) {
    List<Integer> nodes = new ArrayList<>();
    nodes.add(0);

    List<List<Integer>> g = LowestCommonAncestorEulerTour.createEmptyGraph(n);
    for (int nextNode = 1; nodes.size() != n; nextNode++) {
      int randomNode = nodes.get((int) (Math.random() * nodes.size()));
      LowestCommonAncestorEulerTour.addUndirectedEdge(g, randomNode, nextNode);
      nodes.add(nextNode);
    }
    return g;
  }
}