Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

graphHasPath.ts

function hasPath<T>(n1: GraphNode<T>, n2: GraphNode<T>): boolean {
  const visitedByN1 = new Map()
  const visitedByN2 = new Map()

  let children1: GraphNode<T>[] = n1.children
  let children2: GraphNode<T>[] = n2.children

  while (children1.length > 0 || children2.length > 0) {
    let output = searchChildren(children1, visitedByN1, n2)
    if (output === true) {
      return true
    } else {
      children1 = output as GraphNode<T>[]
    }

    output = searchChildren(children2, visitedByN2, n1)
    if (output === true) {
      return true
    } else {
      children2 = output as GraphNode<T>[]
    }
  }

  return false
}

function searchChildren<T>(children: GraphNode<T>[], visitedNodes: Map<GraphNode<T>, GraphNode<T>>, targetNode: GraphNode<T>) {
  const tempChildren: GraphNode<T>[] = []
  while (children.length > 0) {
    const node = children.pop() as GraphNode<T>
    if (node === targetNode) return true
    const newChildren = node.children.filter(child => !visitedNodes.get(child))
    newChildren.forEach(child => tempChildren.push(child))
  }
  return tempChildren
}


const n1 = new GraphNode(1)
const n2 = new GraphNode(2)
const n3 = new GraphNode(3)
const n4 = new GraphNode(4)
const n5 = new GraphNode(5)
const n6 = new GraphNode(6)

n1.pointAt(n2)
n1.pointAt(n3)
n2.pointAt(n4)
n3.pointAt(n5)
n4.pointAt(n5)
// n5.pointAt(n6)
n6.pointAt(n2)
n2.pointAt(n1)

console.log('has path', hasPath(n1, n6))