Dustin Boston

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

/** Enum representing possible states of a vertex in graph traversal. */
enum VertexColor {
  Unvisited = 0, // Vertex has not been visited.
  Visiting = 1, // Vertex is being visited.
  Visited = 2, // Vertex has been fully visited.
}

/** Class representing a vertex in a graph. */
export class GraphVertex {
  public adjacent: GraphVertex[] = [];
  public predecessor: GraphVertex | undefined = undefined;
  public distance = Infinity;
  public finalDistance = Infinity;
  public state: VertexColor = VertexColor.Unvisited;

  constructor(public value: string) {}
}

/**
 * Function to perform iterative depth-first search on a graph.
 *
 * @param graph Array of vertices representing the graph.
 */
export function iterativeDepthFirstSearch(graph: GraphVertex[]): void {
  for (const vertex of graph) {
    vertex.state = VertexColor.Unvisited;
    vertex.predecessor = undefined;
  }

  let timeCounter = 0;
  const vertexStack: GraphVertex[] = [];

  for (const vertex of graph) {
    if (vertex.state === VertexColor.Unvisited) {
      vertexStack.push(vertex);

      while (vertexStack.length > 0) {
        const currentVertex = vertexStack.pop();
        if (!currentVertex) throw new Error("Stack unexpectedly empty.");

        if (currentVertex.state === VertexColor.Unvisited) {
          currentVertex.state = VertexColor.Visiting;
          currentVertex.distance = ++timeCounter;
        } else if (currentVertex.state === VertexColor.Visited) {
          continue;
        }

        let adjacentAdded = 0;
        for (let i = currentVertex.adjacent.length - 1; i >= 0; i--) {
          const neighbor = currentVertex.adjacent[i];
          if (neighbor.state === VertexColor.Unvisited) {
            neighbor.predecessor = currentVertex;
            vertexStack.push(neighbor);
            adjacentAdded++;
          }
        }

        if (adjacentAdded === 0) {
          currentVertex.state = VertexColor.Visited;
          currentVertex.finalDistance = ++timeCounter;
          if (currentVertex.predecessor)
            vertexStack.push(currentVertex.predecessor);
        }
      }
    }
  }
}

/**
 * Utility to print graph structure for debugging using a for loop.
 *
 * @param graph Array of graph vertices.
 * @returns String representation of the graph structure.
 */
export function printGraphStructure(graph: GraphVertex[]): string {
  const pseudoTime = 1;
  let output = "";

  for (const vertex of graph) {
    const details = getVertexDetails(vertex, pseudoTime);
    output += `(${vertex.value}${details}${vertex.value})`;
  }

  return output;
}

/**
 * Helper function to print details of adjacent vertices.
 *
 * @param vertex Current vertex being explored.
 * @param currentTime Reference to traversal time.
 * @returns String representation of adjacent vertices.
 */
export function getVertexDetails(
  vertex: GraphVertex,
  currentTime: number,
): string {
  currentTime++;
  let details = "";
  for (const neighbor of vertex.adjacent) {
    details += `(${neighbor.value}`;
    const distanceMatches = neighbor.distance === currentTime;
    const isNextVisited = currentTime + 1 !== neighbor.finalDistance;

    if (distanceMatches && isNextVisited) {
      details += getVertexDetails(neighbor, currentTime);
    }

    details += `${neighbor.value})`;
  }

  currentTime++;
  return details;
}

import {describe, test, expect, beforeAll} from "bun:test";
import {iterativeDepthFirstSearch, GraphVertex} from "./code.ts";

function printStructure(g: GraphVertex[]) {
  let ptime = 0;

  function print() {
    ptime = 1;

    const accumulator: string[] = [];
    for (const u of g) {
      const s = printAdjacentVertices(u);
      accumulator.push(`(${u.value}${s}${u.value})`);
    }

    return accumulator.join("");
  }

  function printAdjacentVertices(u: GraphVertex) {
    ptime += 1;
    let s = "";

    for (const v of u.adjacent) {
      s += `(${v.value}`;
      // Distance matches current
      const d = v.distance === ptime;
      // Next adjacent vertex has been visited
      const n = ptime + 1 !== v.finalDistance;

      if (d && n) {
        s += printAdjacentVertices(v);
      }

      s += `${v.value})`;
    }

    ptime += 1;
    return s;
  }

  return print();
}

describe("Depth First Search", () => {
  let graph: GraphVertex[] = [];

  beforeAll(() => {
    // Create verticies V
    graph = [
      new GraphVertex("u"),
      new GraphVertex("v"),
      new GraphVertex("w"),
      new GraphVertex("x"),
      new GraphVertex("y"),
      new GraphVertex("z"),
    ];

    const [nu, nv, nw, nx, ny, nz] = graph;

    // Add edges E
    nu.adjacent = nw.adjacent.concat([nv, nx]);
    nv.adjacent.push(ny);
    nw.adjacent = nw.adjacent.concat([ny, nz]);
    nx.adjacent.push(nv);
    ny.adjacent.push(nx);
    nz.adjacent.push(nz);

    graph = [nu, nv, nw, nx, ny, nz];
  });

  test("Depth", () => {
    iterativeDepthFirstSearch(graph);
    const nw = graph[2];
    const expectedTime = 12; // Time is V + E (from u and w)
    expect(nw.finalDistance).toBe(expectedTime);
  });

  test("Structure", () => {
    iterativeDepthFirstSearch(graph);
    const [nu, , nw] = graph;
    const expectedStructure = "(u(v(y(xx)y)v)(xx)u)(w(yy)(zz)w)";
    const structure = printStructure([nu, nw]);
    expect(expectedStructure).toBe(structure);
  });
});