Grafo.js

import Vertice from './Vertice.js';
import Aresta from './Aresta.js';



class Grafo {
  constructor(numVertices) {
    this.numVertices = numVertices;
    this.numArestas = 0;
    this.vertices = [];
    this.arestas = [];
  }

  getNumVertices() {
    return this.numVertices;
  }

  getNumArestas() {
    return this.numArestas;
  }

  adicionarVertice(indice, rotulo) {
    this.vertices.push(new Vertice(indice, rotulo));

    for (let i = 0; i < this.getNumVertices(); i++) {
      this.getVertice(indice).addDistancia(0);
    }
  }
  criarGrafo(numVertices) {
    let grafo1 = new Grafo(numVertices);
    for (let i = 1; i <= numVertices; i++) {
      grafo1.adicionarVertice(i, `V${i}`);
    }
    return grafo1;
  }


  getVertice(i) {
    return this.vertices[i - 1];
  }

  criarMatrizDePesos() {
    const matrixDePesos = Array.from({ length: this.getNumVertices() }, () =>
      Array.from({ length: this.getNumVertices() }, () => 0)
    );

    for (let linhas = 0; linhas < this.getNumVertices(); linhas++) {
      for (let colunas = 0; colunas < this.getNumVertices(); colunas++) {
        matrixDePesos[linhas][colunas] = this.getVertice(linhas + 1).getDistancias()[colunas];
      }
    }

    return matrixDePesos;
  }

  adicionarAresta(origem, destino, peso) {
    if (origem === destino) {
      this.getVertice(origem).addVerticeVizinho(this.getVertice(destino));
    } else {
      this.getVertice(origem).addVerticeVizinho(this.getVertice(destino));
      this.getVertice(origem).setDistancia(destino, peso);
      this.getVertice(destino).addVerticeVizinho(this.getVertice(origem));
      this.getVertice(destino).setDistancia(origem, peso);
    }

    this.arestas.push(new Aresta(this.getVertice(origem), this.getVertice(destino), peso));
    this.numArestas++;
  }

  imprimirGrafo() {
    let output = "<br>Numero de vertices: " + this.getNumVertices();
    output += "<br>Numero de arestas: " + this.getNumArestas() + "<br>";

    output += "<br>Lista de Adjacencias: <br>";

    for (let x = 0; x < this.getNumVertices(); x++) {
      output += this.vertices[x].getRotulo() + " -> ";
      for (const vertice of this.vertices[x].verticesVizinhos) {
        output += vertice.getRotulo() + "  ";
      }
      output += "<br>";
    }

    if (this.numArestas > 0) {
      output += "<br>Lista de Distancias: <br>";
      for (const aresta of this.arestas) {
        output += aresta.getAresta() + "<br>";
      }
    }

    output += "<br>";
    return output;
  }

  visualizeWithD3() {
    const d3 = window.d3;

    const nodes = this.vertices.map((vertex, i) => ({ id: i, label: vertex.getRotulo() }));
    const links = this.arestas.map(aresta => {
      const sourceIndex = this.vertices.indexOf(aresta.getVertice1());
      const targetIndex = this.vertices.indexOf(aresta.getVertice2());
      return {
        source: sourceIndex,
        target: targetIndex,
        weight: aresta.getPeso()
      };
    });
    const svg = d3.select("#grafoImpresso").append("svg")
      .attr("width", 600)
      .attr("height", 600);

    const raio = 15; // raio dos vértices
    const node = svg.selectAll(".node").data(nodes).enter().append("circle")
      .attr("r", raio)
      .style("fill", "rgba(90, 90, 90)"); // cor do círculo - cinza

    // Cria a simulação
    const simulation = d3.forceSimulation(nodes)
      .force("link", d3.forceLink(links).id(d => d.id).distance(d => Math.min(Math.max(d.weight * raio, 75), 450)))
      .force("charge", d3.forceManyBody().strength(-6 * raio))
      .force("center", d3.forceCenter(300, 300)); // centro da tela de 600x600


    const link = svg.selectAll(".link").data(links).enter().append("line")
      .style("stroke", "#000")
      .style("stroke-width", 2);

    const linkText = svg.selectAll(".link-text").data(links).enter().append("g");

    linkText.append("rect")
      .attr("width", d => String(d.weight).length * 14)
      .attr("height", 20)
      .style("fill", "rgba(128, 128, 128, 0.7)"); // cinza claro para o fundo das distancias

    linkText.append("text")
      .text(d => d.weight)
      .style("fill", "blue")
      .style("font-size", "24px")
      .attr("dx", d => (d.source.x + d.target.x) / 2)
      .attr("dy", d => (d.source.y + d.target.y) / 2);


    const rotuloVertice = svg.selectAll(".label").data(nodes).enter().append("text")
      .text(d => d.label)
      .attr("x", d => d.x)
      .attr("y", d => d.y)
      .style("fill", "#fff")
      .style("font-size", "12px")
      .style("text-anchor", "middle")
      .style("alignment-baseline", "middle");

    simulation.on("tick", () => {
      link.attr("x1", d => d.source.x)
        .attr("y1", d => d.source.y)
        .attr("x2", d => d.target.x)
        .attr("y2", d => d.target.y);
      linkText.select("rect")
        .attr("x", d => (d.source.x + d.target.x) / 2 + 3)
        .attr("y", d => (d.source.y + d.target.y) / 2 - 18)
      linkText.select("text")
        .attr("dx", d => (d.source.x + d.target.x) / 2 + 3)
        .attr("dy", d => (d.source.y + d.target.y) / 2);

      node.attr("cx", d => d.x)
        .attr("cy", d => d.y);
      rotuloVertice.attr("x", d => d.x)
        .attr("y", d => d.y);

    });
  }

  minDistance(dist, sptSet) {
    let min = Infinity, min_index = -1;

    for (let v = 0; v < this.getNumVertices(); v++) {
      if (!sptSet[v] && dist[v] <= min) {
        min = dist[v];
        min_index = v;
      }
    }

    return min_index;
  }

  printadorCidade(j, origem) {
    console.log(`${this.getVertice(origem).getCidade()}  ${this.getVertice(j + 1).getCidade()}`);
  }

  printSolution(dist, origem) {
    console.log("Vertice  Distancia da Origem");
    let j = 0;

    for (let i = 0; i < this.getNumVertices(); i++) {
      this.printadorCidade(j, origem);
      console.log(`  ${dist[i]}`);
      if (i < this.getNumVertices() - 1) {
        j++;
      }
    }
  }

  dijkstra(grafo, origem) {
    const dist = Array.from({ length: this.getNumVertices() }, () => Infinity);
    const sptSet = Array(this.getNumVertices()).fill(false);

    dist[origem] = 0;

    for (let count = 0; count < this.getNumVertices() - 1; count++) {
      const u = this.minDistance(dist, sptSet);

      sptSet[u] = true;

      for (let v = 0; v < this.getNumVertices(); v++) {
        if (!sptSet[v] && grafo[u][v] !== 0 && dist[u] !== Infinity && dist[u] + grafo[u][v] < dist[v]) {
          dist[v] = dist[u] + grafo[u][v];
          //caminho[v] = grafo[u][v];
        }
      }
    }

    this.printSolution(dist, origem + 1);
  }

  /*
  * Aqui definimos nossa heurítica. 
  * Por exemplo, poderia ser a distância em linha reta (euclidiana) entre as coordenadas dos vértices.
  * Em nosso cado, a heurística será o peso (distancia) entre os vértices.
  */
  heuristica(verticeAtual, verticeDestino) {
    return verticeAtual.getDistancias()[verticeDestino.getIndice() - 1];
  }

  aStar(grafo, origem, destino) {
    const pai = new Array(this.getNumVertices()).fill(null);
    const fScore = new Array(this.getNumVertices()).fill(Number.MAX_SAFE_INTEGER);
    const gScore = new Array(this.getNumVertices()).fill(Number.MAX_SAFE_INTEGER);
    const openSet = new Set();

    gScore[origem - 1] = 0;
    fScore[origem - 1] = this.heuristica(this.getVertice(origem), this.getVertice(destino));

    openSet.add(origem);

    while (openSet.size > 0) {
      const verticeAtual = Array.from(openSet).reduce((a, b) => (fScore[a - 1] < fScore[b - 1] ? a : b));

      if (verticeAtual === destino) {
        // Reconstruir o caminho
        const caminho = [];
        let vertice = destino;

        while (pai[vertice - 1] !== null) {
          caminho.unshift(vertice);
          vertice = pai[vertice - 1];
          console.log(caminho)
        }
        caminho.unshift(origem);
        return caminho;
      }

      openSet.delete(verticeAtual);

      for (const verticeVizinho of this.getVertice(verticeAtual).verticesVizinhos) {
        const tentativaGScore = gScore[verticeAtual - 1] + grafo[verticeAtual - 1][verticeVizinho.getIndice() - 1];

        if (tentativaGScore < gScore[verticeVizinho.getIndice() - 1]) {
          pai[verticeVizinho.getIndice() - 1] = verticeAtual;
          gScore[verticeVizinho.getIndice() - 1] = tentativaGScore;
          fScore[verticeVizinho.getIndice() - 1] =
            gScore[verticeVizinho.getIndice() - 1] + this.heuristica(verticeVizinho, this.getVertice(destino));

          if (!openSet.has(verticeVizinho.getIndice())) {
            openSet.add(verticeVizinho.getIndice());
          }
        }
      }

    }
    // Caminho não encontrado
    return null;
  }
}

export default Grafo;