Back to Repositories

Testing Directed Cycle Detection Algorithm in javascript-algorithms

This test suite validates the detection of cycles in directed graphs using JavaScript algorithms. It verifies the functionality of the detectDirectedCycle algorithm by testing graph construction and cycle identification in various vertex configurations.

Test Coverage Overview

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

Key areas tested include:

Graph construction with multiple vertices and edges
Cycle detection in both cyclic and acyclic configurations
Edge case handling for complex graph structures
Vertex relationship validation

Implementation Analysis

The testing approach employs Jest’s describe-it pattern for structured test organization. The implementation creates a directed graph with vertices A through F, systematically adding edges to test both acyclic and cyclic scenarios.

Technical patterns include:

Graph vertex and edge instantiation
Sequential edge addition testing
Null assertion for acyclic graphs
Cycle path verification

Technical Details

Testing infrastructure includes:

Jest testing framework
GraphVertex and GraphEdge data structures
Custom Graph implementation
Directed cycle detection algorithm
Expect assertions for result validation

Best Practices Demonstrated

The test suite exemplifies high-quality testing practices through clear structure and comprehensive validation.

Notable practices include:

Isolated test scenarios
Step-by-step graph construction
Clear expected outcomes
Explicit state verification
Modular test organization

trekhleb/javascript-algorithms

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

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

describe('detectDirectedCycle', () => {
  it('should detect directed 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 edgeAB = new GraphEdge(vertexA, vertexB);
    const edgeBC = new GraphEdge(vertexB, vertexC);
    const edgeAC = new GraphEdge(vertexA, vertexC);
    const edgeDA = new GraphEdge(vertexD, vertexA);
    const edgeDE = new GraphEdge(vertexD, vertexE);
    const edgeEF = new GraphEdge(vertexE, vertexF);
    const edgeFD = new GraphEdge(vertexF, vertexD);

    const graph = new Graph(true);
    graph
      .addEdge(edgeAB)
      .addEdge(edgeBC)
      .addEdge(edgeAC)
      .addEdge(edgeDA)
      .addEdge(edgeDE)
      .addEdge(edgeEF);

    expect(detectDirectedCycle(graph)).toBeNull();

    graph.addEdge(edgeFD);

    expect(detectDirectedCycle(graph)).toEqual({
      D: vertexF,
      F: vertexE,
      E: vertexD,
    });
  });
});