Back to Repositories

Testing Undirected Cycle Detection Algorithm in javascript-algorithms

This test suite validates the detectUndirectedCycle algorithm implementation for detecting cycles in undirected graphs. It verifies the algorithm’s ability to correctly identify circular dependencies between vertices and return null when no cycles exist.

Test Coverage Overview

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

Key areas tested include:

Cycle-free graph validation
Cycle detection with multiple vertices
Edge case handling for connected components
Vertex relationship mapping

Implementation Analysis

The testing approach utilizes Jest’s describe/it blocks for structured test organization. The implementation creates a test graph with multiple vertices (A-F) and edges, first verifying no cycles exist, then adding an edge to create and detect a cycle.

Technical patterns include:

Graph construction using vertex and edge objects
Incremental edge addition
Cycle detection verification

Technical Details

Testing infrastructure includes:

Jest testing framework
GraphVertex and GraphEdge data structures
Custom Graph implementation
Expect assertions for null and object matching

Best Practices Demonstrated

The test suite exemplifies strong testing practices through clear structure and comprehensive validation.

Notable practices include:

Isolated test scenarios
Step-by-step graph construction
Clear expected outcomes
Proper test case organization

trekhleb/javascript-algorithms

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

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

describe('detectUndirectedCycle', () => {
  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(detectUndirectedCycle(graph)).toBeNull();

    graph.addEdge(edgeDE);

    expect(detectUndirectedCycle(graph)).toEqual({
      B: vertexC,
      C: vertexD,
      D: vertexE,
      E: vertexB,
    });
  });
});