Back to Repositories

Testing Brute Force Traveling Salesman Algorithm in javascript-algorithms

This test suite validates the Brute Force Traveling Salesman algorithm implementation, ensuring correct path finding in a weighted directed graph. It verifies the algorithm’s ability to find the optimal route visiting all vertices exactly once and returning to the starting point.

Test Coverage Overview

The test suite provides comprehensive coverage of the Traveling Salesman Problem (TSP) implementation.

Key areas tested include:

Graph construction with weighted edges
Path verification for a simple directed graph
Vertex order validation in the final path
Path length confirmation

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for structured test organization. The implementation creates a directed graph with four vertices (A, B, C, D) and twelve edges with different weights, validating the algorithm’s ability to find the optimal path through all vertices.

Technical patterns include:

Graph object initialization and configuration
Edge weight management
Path validation using Jest’s expect assertions

Technical Details

Testing infrastructure includes:

Jest testing framework
GraphVertex and GraphEdge custom implementations
Graph data structure with directed edge support
Assertion-based validation for path properties

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Clear test case organization
Comprehensive setup of test data
Explicit expected outcomes
Granular assertions for path validation
Modular test structure

trekhleb/javascript-algorithms

src/algorithms/graph/travelling-salesman/__test__/bfTravellingSalesman.test.js

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

describe('bfTravellingSalesman', () => {
  it('should solve problem for simple graph', () => {
    const vertexA = new GraphVertex('A');
    const vertexB = new GraphVertex('B');
    const vertexC = new GraphVertex('C');
    const vertexD = new GraphVertex('D');

    const edgeAB = new GraphEdge(vertexA, vertexB, 1);
    const edgeBD = new GraphEdge(vertexB, vertexD, 1);
    const edgeDC = new GraphEdge(vertexD, vertexC, 1);
    const edgeCA = new GraphEdge(vertexC, vertexA, 1);

    const edgeBA = new GraphEdge(vertexB, vertexA, 5);
    const edgeDB = new GraphEdge(vertexD, vertexB, 8);
    const edgeCD = new GraphEdge(vertexC, vertexD, 7);
    const edgeAC = new GraphEdge(vertexA, vertexC, 4);
    const edgeAD = new GraphEdge(vertexA, vertexD, 2);
    const edgeDA = new GraphEdge(vertexD, vertexA, 3);
    const edgeBC = new GraphEdge(vertexB, vertexC, 3);
    const edgeCB = new GraphEdge(vertexC, vertexB, 9);

    const graph = new Graph(true);
    graph
      .addEdge(edgeAB)
      .addEdge(edgeBD)
      .addEdge(edgeDC)
      .addEdge(edgeCA)
      .addEdge(edgeBA)
      .addEdge(edgeDB)
      .addEdge(edgeCD)
      .addEdge(edgeAC)
      .addEdge(edgeAD)
      .addEdge(edgeDA)
      .addEdge(edgeBC)
      .addEdge(edgeCB);

    const salesmanPath = bfTravellingSalesman(graph);

    expect(salesmanPath.length).toBe(4);

    expect(salesmanPath[0].getKey()).toEqual(vertexA.getKey());
    expect(salesmanPath[1].getKey()).toEqual(vertexB.getKey());
    expect(salesmanPath[2].getKey()).toEqual(vertexD.getKey());
    expect(salesmanPath[3].getKey()).toEqual(vertexC.getKey());
  });
});