Uniswap v2 path (route) finder between two tokens, only yields one route

path-finder-recursive.js

class DotPath {
  constructor(a, b) {
    this.storage = [a, b] 
  }

  hasDot(dot) {
    switch (dot) {
      case this.storage[0]:
        return true
      case this.storage[1]:
        return true
      default:
        return false
    }
  }

  getSibling(dot) { // get sibling or null
    switch (dot) {
      case this.storage[0]:
        return this.storage[1]
      case this.storage[1]:
        return this.storage[0]
      default:
        return null
    }
  }
}

class Bag {
  constructor(){
    this.collection = new Set()
    this.path = []
  }

  addDot(a) {
    if (this.collection.has(a)) {
      return false
    } else {
      this.collection.add(a)
      this.path.push(a)
      return true
    }
  }

  hasDot(a) {
    return this.collection.has(a)
  }

  lastDot() {
    return this.path[this.path.length - 1]
  }

  getDots() {
    return this.path
  }
}

class DotGraph {
  constructor(pairs) { // pairs = [(a,b), (a,c), (b,c) ... ]
    this.pairs = []
    this.dots = new Set()
    pairs.forEach(element => {
      this.pairs.push(new DotPath(element[0], element[1]))
      this.dots.add(element[0])
      this.dots.add(element[1])
    });
  }

  hasDot(a) {
    return this.dots.has(a)
  }

  getSiblings(a) { // return [] of siblings
    let siblings = []
    for (let i = 0; i < this.pairs.length; i++) {
      let dot = this.pairs[i].getSibling(a)
      if (dot != null) {
        siblings.push(dot)
      }
    }
    return siblings
  }

  findPath(a, b) {
    if (!this.hasDot(a)) {
      return null
    }
    if (!this.hasDot(b)) {
      return null
    }
    // prepare a bag
    let bag = new Bag()
    bag.addDot(a)
    // prepare a storage for bags
    let finalbag = this._findPath(a, b, bag)
    return finalbag.getDots()
  }

  _findPath(a, b, bag) {
    // Satisfied? Just return the bag
    if (bag.lastDot() == b) {
      return bag
    }
    // Not satisfied? Continue
    let dots = this.getSiblings(a)
    if (dots.length == 0) {
      return null
    } else {
      for (let i = 0; i < dots.length; i++) {
        let success = bag.addDot(dots[i])
        if (!success) {
          continue
        }
        return this._findPath(dots[i], b, bag)
      }
    }
  }
}

let pairs = [['a', 'b'], ['a', 'c'], ['b', 'd'], ['c', 'd']]
dg = new DotGraph(pairs)
console.log(dg.findPath('a', 'd'))