Back to Repositories

Testing Undirected Cycle Detection with Disjoint Sets in javascript-algorithms

This test suite validates cycle detection in undirected graphs using the Disjoint Set data structure. It ensures accurate identification of cyclic patterns within graph structures by testing both acyclic and cyclic graph configurations.

Test Coverage Overview

The test suite provides comprehensive coverage for cycle detection in undirected graphs.

Key areas tested include:

Acyclic graph verification
Cycle detection after edge addition
Graph construction with multiple vertices and edges
Edge case handling for connected components

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for structured test organization. The implementation creates a test graph with six vertices (A-F) and various connecting edges, validating both non-cyclic and cyclic configurations through sequential edge additions.

Technical patterns include:

Graph vertex and edge instantiation
Incremental graph construction
State verification before/after modifications

Technical Details

Testing infrastructure includes:

Jest testing framework
Graph data structure implementation
DisjointSet algorithm integration
GraphVertex and GraphEdge class utilization
Boolean return value assertions

Best Practices Demonstrated

The test suite exemplifies several testing best practices for graph algorithms.

Notable practices include:

Clear test case isolation
Systematic graph construction
Explicit state verification
Modular component testing
Progressive complexity building

trekhleb/javascript-algorithms

src/algorithms/graph/detect-cycle/__test__/detectUndirectedCycleUsingDisjointSet.test.js

            
import GraphVertex from '../../../../data-structures/graph/GraphVertex';
import GraphEdge from '../../../../data-structures/graph/GraphEdge';
import Graph from '../../../../data-structures/graph/Graph';
import detectUndirectedCycleUsingDisjointSet from '../detectUndirectedCycleUsingDisjointSet';

describe('detectUndirectedCycleUsingDisjointSet', () => {
  it('should detect undirected cycle', () => {
    const vertexA = new GraphVertex('A');
    const vertexB = new GraphVertex('B');
    const vertexC = new GraphVertex('C');
    const vertexD = new GraphVertex('D');
    const vertexE = new GraphVertex('E');
    const vertexF = new GraphVertex('F');

    const edgeAF = new GraphEdge(vertexA, vertexF);
    const edgeAB = new GraphEdge(vertexA, vertexB);
    const edgeBE = new GraphEdge(vertexB, vertexE);
    const edgeBC = new GraphEdge(vertexB, vertexC);
    const edgeCD = new GraphEdge(vertexC, vertexD);
    const edgeDE = new GraphEdge(vertexD, vertexE);

    const graph = new Graph();
    graph
      .addEdge(edgeAF)
      .addEdge(edgeAB)
      .addEdge(edgeBE)
      .addEdge(edgeBC)
      .addEdge(edgeCD);

    expect(detectUndirectedCycleUsingDisjointSet(graph)).toBe(false);

    graph.addEdge(edgeDE);

    expect(detectUndirectedCycleUsingDisjointSet(graph)).toBe(true);
  });
});