Tarjan's strongly connected components algorithm in TypeScript. Adapted from https://gist.github.com/chadhutchins/1440602

tarjan.test.ts

import { Graph, Vertex, Tarjan } from '../tarjan';

it('handles simple cases', () => {
  const v0 = new Vertex('0');
  const v1 = new Vertex('1');
  const v2 = new Vertex('2');

  v0.connections.add(v1);
  v1.connections.add(v2);

  const vertices = [v0, v1, v2];

  const graph = new Graph(vertices);
  const tarjan = new Tarjan(graph);

  const scc = tarjan.run();

  expect(scc.map((vertices) => vertices.map((vertex) => vertex.name))).toEqual([
    ['2'],
    ['1'],
    ['0'],
  ]);
});

it('finds strongly connected components', () => {
  const v0 = new Vertex('0');
  const v1 = new Vertex('1');
  const v2 = new Vertex('2');

  v0.connections.add(v1);
  v1.connections.add(v2);
  v2.connections.add(v0); // cycle

  const vertices = [v0, v1, v2];

  const graph = new Graph(vertices);
  const tarjan = new Tarjan(graph);

  const scc = tarjan.run();

  expect(scc.map((vertices) => vertices.map((vertex) => vertex.name))).toEqual([['2', '1', '0']]);
});

it('handles a mix of cycles and non-cycles', () => {
  const v0 = new Vertex('0');
  const v1 = new Vertex('1');
  const v2 = new Vertex('2');

  v0.connections.add(v1);
  v1.connections.add(v2);
  v2.connections.add(v1); // cycle

  const vertices = [v0, v1, v2];

  const graph = new Graph(vertices);
  const tarjan = new Tarjan(graph);

  const scc = tarjan.run();

  expect(scc.map((vertices) => vertices.map((vertex) => vertex.name))).toEqual([['2', '1'], ['0']]);
});

it('handles complex scenarios', () => {
  const v0 = new Vertex('0');
  const v1 = new Vertex('1');
  const v2 = new Vertex('2');
  const v3 = new Vertex('3');
  const v4 = new Vertex('4');
  const v5 = new Vertex('5');
  const v6 = new Vertex('6');
  const v7 = new Vertex('7');
  const v8 = new Vertex('8');
  const v9 = new Vertex('9');
  const v10 = new Vertex('10');
  const v11 = new Vertex('11');
  const v12 = new Vertex('12');

  v0.connections.add(v1);
  v0.connections.add(v5);
  v2.connections.add(v0);
  v2.connections.add(v3);
  v3.connections.add(v2);
  v3.connections.add(v5);
  v4.connections.add(v2);
  v4.connections.add(v2);
  v5.connections.add(v4);
  v6.connections.add(v0);
  v6.connections.add(v9);
  v7.connections.add(v6);
  v7.connections.add(v8);
  v8.connections.add(v7);
  v8.connections.add(v9);
  v9.connections.add(v10);
  v9.connections.add(v11);
  v10.connections.add(v12);
  v11.connections.add(v4);
  v11.connections.add(v12);
  v12.connections.add(v9);

  const vertices = [v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12];

  const graph = new Graph(vertices);
  const tarjan = new Tarjan(graph);

  const scc = tarjan.run();

  expect(scc.map((vertices) => vertices.map((vertex) => vertex.name))).toEqual([
    ['1'],
    ['3', '2', '4', '5', '0'],
    ['11', '12', '10', '9'],
    ['6'],
    ['8', '7'],
  ]);
});

tarjan.ts

// Adapted from https://gist.github.com/chadhutchins/1440602

export class Vertex {
  name: string;

  connections: Set<Vertex>;

  index: number;

  lowlink: number;

  constructor(name: string) {
    this.name = name;
    this.connections = new Set();

    // used in tarjan algorithm
    // went ahead and explicity initialized them
    this.index = -1;
    this.lowlink = -1;
  }

  equals(vertex: Vertex) {
    // equality check based on vertex name
    return vertex.name && this.name === vertex.name;
  }
}

export class Graph {
  vertices: Vertex[];

  constructor(vertices: Vertex[]) {
    this.vertices = vertices || [];
  }
}

class VertexStack {
  vertices: Vertex[];

  constructor(vertices?: Vertex[]) {
    this.vertices = vertices || [];
  }

  contains(vertex: Vertex) {
    return this.vertices.some((v) => v.equals(vertex));
  }
}

export class Tarjan {
  index: number;

  stack: VertexStack;

  graph: Graph;

  scc: Vertex[][];

  constructor(graph: Graph) {
    this.index = 0;
    this.stack = new VertexStack();
    this.graph = graph;
    this.scc = [];
  }

  run() {
    this.graph.vertices.forEach((vertex) => {
      if (vertex.index < 0) {
        this.strongconnect(vertex);
      }
    });
    return this.scc;
  }

  strongconnect(vertex: Vertex) {
    // Set the depth index for v to the smallest unused index
    vertex.index = this.index;
    vertex.lowlink = this.index;
    this.index += 1;
    this.stack.vertices.push(vertex);

    // Consider successors of v
    // aka... consider each vertex in vertex.connections
    vertex.connections.forEach((successor) => {
      if (successor.index < 0) {
        // Successor has not yet been visited; recurse on it
        this.strongconnect(successor);
        vertex.lowlink = Math.min(vertex.lowlink, successor.lowlink);
      } else if (this.stack.contains(successor)) {
        // Successor is in stack; thus, it is in the current SCC
        vertex.lowlink = Math.min(vertex.lowlink, successor.index);
      }
    });

    // If v is a root node, pop the stack and generate an SCC
    if (vertex.lowlink === vertex.index) {
      // start a new strongly connected component
      const vertices: Vertex[] = [];
      let w: Vertex | undefined;
      if (this.stack.vertices.length > 0) {
        do {
          w = this.stack.vertices.pop();
          if (w) {
            // add to current strongly connected component
            vertices.push(w);
          }
        } while (w && !vertex.equals(w));
      }

      // output the current strongly connected component
      // ... i'm going to push the results to a member scc array variable
      if (vertices.length > 0) {
        this.scc.push(vertices);
      }
    }
  }
}