class Graph {
  constructor () {
    this.adjacencyMap = {}
  }

  addVertex (v) {
    this.adjacencyMap[v] = []
  }

  containsVertex (vertex) {
    return typeof (this.adjacencyMap[vertex]) !== 'undefined'
  }

  addEdge (v, w) {
    let result = false
    if (this.containsVertex(v) && this.containsVertex(w)) {
      this.adjacencyMap[v].push(w)
      this.adjacencyMap[w].push(v)
      result = true
    }
    return result
  }

  printGraph () {
    const keys = Object.keys(this.adjacencyMap)
    for (const i of keys) {
      const values = this.adjacencyMap[i]
      let vertex = ''
      for (const j of values) { vertex += j + ' ' }
      console.log(i + ' -> ' + vertex)
    }
  }

  /**
   * Prints the Breadth first traversal of the graph from source.
   *
   * @param {number} source The source vertex to start BFS.
   */
  bfs (source) {
    const queue = []
    const visited = new Set()
    queue.unshift([source, 0]) // level of source is 0
    visited.add(source)
    while (queue.length) {
      const front = queue[0]
      const node = front[0]
      const level = front[1]
      queue.shift() // remove the front of the queue
      console.log(`Visited node ${node} at level ${level}.`)
      for (const next of this.adjacencyMap[node]) {
        if (!visited.has(next)) { // not visited
          queue.unshift([next, level + 1]) // level 1 more than current
          visited.add(next)
        }
      }
    }
  }
}

const example = () => {
  const g = new Graph()
  g.addVertex(1)
  g.addVertex(2)
  g.addVertex(3)
  g.addVertex(4)
  g.addVertex(5)
  g.addEdge(1, 2)
  g.addEdge(1, 3)
  g.addEdge(2, 4)
  g.addEdge(2, 5)
  console.log('Printing the adjacency list:\n')
  g.printGraph()

  // perform a breadth first search
  console.log('\nBreadth first search at node 1:\n')
  g.bfs(1)
}
example()