Back to Repositories

Testing DisjointSet Component Operations in javascript-algorithms

This test suite validates the DisjointSetAdhoc data structure implementation, focusing on union operations and connected component detection. It ensures proper set relationships and tree height optimization in disjoint set operations.

Test Coverage Overview

The test suite comprehensively covers disjoint set operations with multiple test cases.

Key areas tested include:

Union operations between elements
Connectivity checks between elements
Tree height optimization
Multiple component handling

Edge cases verify isolated elements and cross-component relationships.

Implementation Analysis

The testing approach uses Jest’s describe/it pattern to organize test cases logically. Tests implement a step-by-step verification of set operations, creating complex relationship trees and validating connections. The implementation uses expect assertions to verify both positive and negative connectivity scenarios.

Technical Details

Testing infrastructure includes:

Jest testing framework
DisjointSetAdhoc class implementation
Expect assertions for boolean checks
Array spread operator for height calculations

Best Practices Demonstrated

The test suite exhibits strong testing practices through clear test case organization and comprehensive coverage.

Notable practices include:

Isolated test scenarios
Progressive complexity building
Performance consideration testing
Clear test case descriptions

trekhleb/javascript-algorithms

src/data-structures/disjoint-set/__test__/DisjointSetAdhoc.test.js

            
import DisjointSetAdhoc from '../DisjointSetAdhoc';

describe('DisjointSetAdhoc', () => {
  it('should create unions and find connected elements', () => {
    const set = new DisjointSetAdhoc(10);

    // 1-2-5-6-7 3-8-9 4
    set.union(1, 2);
    set.union(2, 5);
    set.union(5, 6);
    set.union(6, 7);

    set.union(3, 8);
    set.union(8, 9);

    expect(set.connected(1, 5)).toBe(true);
    expect(set.connected(5, 7)).toBe(true);
    expect(set.connected(3, 8)).toBe(true);

    expect(set.connected(4, 9)).toBe(false);
    expect(set.connected(4, 7)).toBe(false);

    // 1-2-5-6-7 3-8-9-4
    set.union(9, 4);

    expect(set.connected(4, 9)).toBe(true);
    expect(set.connected(4, 3)).toBe(true);
    expect(set.connected(8, 4)).toBe(true);

    expect(set.connected(8, 7)).toBe(false);
    expect(set.connected(2, 3)).toBe(false);
  });

  it('should keep the height of the tree small', () => {
    const set = new DisjointSetAdhoc(10);

    // 1-2-6-7-9 1 3 4 5
    set.union(7, 6);
    set.union(1, 2);
    set.union(2, 6);
    set.union(1, 7);
    set.union(9, 1);

    expect(set.connected(1, 7)).toBe(true);
    expect(set.connected(6, 9)).toBe(true);
    expect(set.connected(4, 9)).toBe(false);

    expect(Math.max(...set.heights)).toBe(3);
  });
});