Dustin Boston

/**
 * @file Breadth-First Search
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Represents the possible states that can be assigned to vertices while
 * traversing the graph.
 */
export enum Color {
  /** Vertex has not been visited. */
  White = 0,
  /** Vertex is being visited */
  Gray = 1,
  /** Vertex has been fully visited */
  Black = 2,
}

/** Represents a node in a Directed Acyclic Graph (DAG). */
export class Vertex<T> {
  /** An array of vertices connected to this vertex. */
  adjacent: Array<Vertex<T>> = [];
  /** The parent vertex in a traversal of the graph. */
  parent?: Vertex<T> = undefined;
  /** Steps away from the starting vertex in a graph traversal. */
  distance = Infinity;
  /** State of the vertex in a traversal. */
  color: Color = Color.White;

  /** @param value The value of the vertex. */
  constructor(public value: T) {}
}

/**
 * Performs a breadth-first search (BFS) on a graph starting from a given
 * vertex. Initializes all vertices as unvisited and then processes them level
 * by level.
 *
 * @param graph An array of all vertices in the graph.
 * @param search The starting vertex for the BFS.
 */
export function bfs<T>(graph: Array<Vertex<T>>, search: Vertex<T>) {
  for (const vertex of graph) {
    vertex.color = Color.White;
    vertex.distance = Infinity;
    vertex.parent = undefined;
  }

  search.color = Color.Gray;
  search.distance = 0;
  search.parent = undefined;

  const queue = [search];

  while (queue.length > 0) {
    const vertex: Vertex<T> | undefined = queue.shift();
    if (!vertex) {
      break;
    }

    for (const adjacentVertex of vertex.adjacent ?? []) {
      if (adjacentVertex.color === Color.White) {
        adjacentVertex.color = Color.Gray;
        adjacentVertex.distance = vertex.distance + 1;
        adjacentVertex.parent = vertex;

        queue.push(adjacentVertex);
      }
    }

    vertex.color = Color.Black;
  }
}

/**
 * Prints the path from the search start vertex to a specific vertex
 * recursively. If no path exists, it outputs an appropriate message.
 *
 * @param graph The graph containing all vertices.
 * @param search The starting vertex of the search.
 * @param vertex The target vertex to which the path is to be printed.
 */
export function printPath<T>(
  graph: Array<Vertex<T>>,
  search: Vertex<T>,
  vertex: Vertex<T>,
): string | undefined {
  const path: Array<string | undefined> = [];

  function trace<T>(search: Vertex<T>, vertex: Vertex<T>) {
    if (vertex === search) {
      path.push(String(search.value));
    } else if (vertex.parent === undefined) {
      // No path exists
    } else {
      trace(search, vertex.parent);
      path.push(String(vertex.value));
    }
  }

  trace(search, vertex);
  return path.join(" -> ");
}

import {expect, test, describe} from "bun:test";
import {bfs, printPath, Vertex, Color} from "./code.ts";

describe("Breadth-First Search", () => {
  test("Single Node", () => {
    const vertex = new Vertex("A");
    bfs([vertex], vertex);
    expect(vertex.color).toBe(Color.Black);
    expect(vertex.distance).toBe(0);
  });

  test("Linear Graph", () => {
    const vertA = new Vertex("A");
    const vertB = new Vertex("B");
    const vertC = new Vertex("C");

    vertA.adjacent.push(vertB);
    vertB.adjacent.push(vertC);

    bfs([vertA, vertB, vertC], vertA);
    expect(vertA.distance).toBe(0);
    expect(vertB.distance).toBe(1);
    expect(vertC.distance).toBe(2);
    expect(vertC.color).toBe(Color.Black);
  });

  test("Disconnected Graph", () => {
    const vertA = new Vertex("A");
    const vertB = new Vertex("B");
    const vertC = new Vertex("C"); // Disconnected vertex

    bfs([vertA, vertB, vertC], vertA);
    expect(vertA.color).toBe(Color.Black);
    expect(vertC.distance).toBe(Infinity);
    expect(vertC.color).toBe(Color.White);
  });

  test("Cyclic Graph", () => {
    const vertA = new Vertex("A");
    const vertB = new Vertex("B");
    const vertC = new Vertex("C");

    vertA.adjacent.push(vertB);
    vertB.adjacent.push(vertC);
    vertC.adjacent.push(vertA); // Creating a cycle

    bfs([vertA, vertB, vertC], vertA);
    expect(vertA.color).toBe(Color.Black);
    expect(vertB.color).toBe(Color.Black);
    expect(vertC.color).toBe(Color.Black);
    expect(vertC.distance).toBe(2);
  });

  test("No Path Exists", () => {
    const vertA = new Vertex("A");
    const vertB = new Vertex("B");
    const vertC = new Vertex("C"); // No connection to A or B

    bfs([vertA, vertB], vertA);
    const result = printPath([vertA, vertB, vertC], vertA, vertC);

    expect(result).toBe("");
  });

  test("Path Exists in Linear Graph", () => {
    const vertA = new Vertex("A");
    const vertB = new Vertex("B");
    const vertC = new Vertex("C");

    vertA.adjacent.push(vertB);
    vertB.adjacent.push(vertC);
    bfs([vertA, vertB, vertC], vertA);

    const actual = printPath([vertA, vertB, vertC], vertA, vertC);
    expect(actual).toBe("A -> B -> C");
  });

  test("Path Exists in Cyclic Graph", () => {
    const vertA = new Vertex("A");
    const vertB = new Vertex("B");
    const vertC = new Vertex("C");

    vertA.adjacent.push(vertB);
    vertB.adjacent.push(vertC);
    vertC.adjacent.push(vertA); // Creating a cycle

    bfs([vertA, vertB, vertC], vertA);
    const result = printPath([vertA, vertB, vertC], vertA, vertC);

    expect(result).toBe("A -> B -> C");
  });
});