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'],
  ]);
});