/**
 * 가중 그래프 클래스
 * findLowestPath메서드가 다익스트라 알고리즘을 이용하여 최단거리를 탐색
 */
class WeightedGraph {
  constructor() {
    this.vertices = [];
    this.adjList = {};
    this.costs = {};
    this.parents = {};
    this.processed = new Set();
  }

  addVertex(v) {
    this.vertices.push(v);
    this.adjList[v] = {};
  }

  addEdge(start, end, weight) {
    this.adjList[start][end] = weight;
  }

  findLowestPath() {
    let node = this._findLowestAndUnProcessedNode();
    let cost, neighbors, newCost;
    while (node) {
      cost = this.costs[node];
      neighbors = this.adjList[node];

      for (const n in neighbors) {
        newCost = cost + neighbors[n];
        if (this.costs[n] > newCost) {
          this.costs[n] = newCost;
          this.parents[n] = node;
        }
      }

      this.processed.add(node);
      node = this._findLowestAndUnProcessedNode();
    }
  }

  _findLowestAndUnProcessedNode() {
    let lowestCost = Infinity;
    let lowestCostNode, cost;
    this.vertices.forEach(node => {
      cost = this.costs[node];
      if (cost < lowestCost && !this.processed.has(node)) {
        lowestCost = cost;
        lowestCostNode = node;
      }
    });

    return lowestCostNode;
  }

  // 디버깅용 헬퍼 함수
  toString() {
    let result = "### adjList ###\n";
    for (const key in this.adjList) {
      result += `${key}: `;
      for (const key2 in this.adjList[key]) {
        result += `->${key2}(${Object.values(this.adjList[key][key2])}) `;
      }
      result += "\n";
    }

    result += `\n\n### cost ###\n`;
    for (const key in this.costs) {
      result += `${key}: ${this.costs[key]}\n`;
    }

    result += `\n\n### parents ###\n`;
    for (const key in this.parents) {
      result += `${key}: ${this.parents[key]}\n`;
    }

    result += `\n\n### processed ###\n`;
    result += Array.from(this.processed).join(", ");
    return result;
  }
}

// Test
it("가중그래프와 다익스트라 알고리즘은 잘 동작한다.", () => {
  const graph = new WeightedGraph();

  graph.addVertex("START");
  graph.addVertex("A");
  graph.addEdge("START", "A", 6);
  graph.addVertex("B");
  graph.addEdge("START", "B", 2);
  graph.addEdge("B", "A", 3);
  graph.addEdge("B", "END", 5);
  graph.addEdge("A", "END", 1);

  graph.costs["A"] = 6;
  graph.costs["B"] = 2;
  graph.costs["END"] = Infinity;

  graph.parents["A"] = "START";
  graph.parents["B"] = "START";
  graph.parents["END"] = null;

  graph.findLowestPath();

  expect(graph.parents["END"]).toEqual("A");
  expect(graph.parents["A"]).toEqual("B");
  expect(graph.parents["B"]).toEqual("START");
});