onion-core/test/dfs.test.ts

import {
  findDFS,
} from "../lib/util/dfs";

import {
  assert,
} from "../lib/util/assert";

import * as _ from "lodash";

const graph = new Map([
  [0, new Map([['a', 1], ['b', 2]])], // meaning: node 0 has two outgoing links: --'a'--> node 1 and --'b'--> node 2
  [1, new Map([['c', 0]])],
  [2, new Map([['d', 3]])],
]);

function getNeighbors(node) {
  const outgoing = graph.get(node);
  if (outgoing === undefined) {
    return [];
  }
  return [...outgoing.entries()]
}

describe("DFS", () => {

  it("Find node one hop", () => {
    const path = findDFS(0, 1, getNeighbors);
    assert(_.isEqual(path, ['a']), "Expected node to be found.");
  })

  it("Find node two hops", () => {
    const path = findDFS(0, 3, getNeighbors);

    // There is more than one path from 0 to 3 (in fact, there are infinitely many, if we allow loops),
    // but we don't allow visiting the same element more than once, so only one path is possible:
    assert(_.isEqual(path, ['b', 'd']), "Expected node to be found.");
  });

  it("Find node zero hops", () => {
    const path = findDFS(0, 0, getNeighbors);
    assert(_.isEqual(path, []), "Expected node to be found.");
  })

  it("Find unreachable node", () => {
    const path = findDFS(3, 0, getNeighbors);
    assert(path === undefined, "Expected node to be unreachable.");
  });
});