Функция с диапазоном

const canvas = document.getElementById("canvas");
const ctx = canvas.getContext("2d");
const startNodeSelect = document.getElementById("startNode");
const endNodeSelect = document.getElementById("endNode");
const numVerticesInput = document.getElementById("numVertices");
const adjacencyMatrixTextArea = document.getElementById("adjacencyMatrix");
 
let graph = [];
let vertexPositions = [];
let numVertices = 0;
 
let route = []; // Объявляем переменную route
let algorithmType ="prim";
 
 
 
function changeAlgorithm() {
    console.log("changeAlgorithm");
    var select = document.getElementById('algorithm');
    document.getElementById('resultAlg').style.display = "none";
    visualizeGraph();
    // Отримуємо вибране значення в select
    algorithmType = select.value;
 
    if(algorithmType === "prim")
      document.getElementById("selectNodes").style.display = "block";
    else
      document.getElementById("selectNodes").style.display = "none";
}
 
function isGraphContinuous(graph) {
  for (let i = 0; i < graph.length; i++) {
    for (let j = 0; j < graph[i].length; j++) {
      if (i !== j && graph[i][j] <= 0) {
        // Если вес ребра между вершинами i и j не положителен, граф не является непрерывным
        return false;
      }
    }
  }
  return true;
}
 
function generateMatrix() {
  document.getElementById('resultAlg').style.display = "none";
  
  const choice = prompt("Vyberte spôsob vyplnenia matice:\n1. Doplňte náhodnými číslami\n2. Vyplňte ručne");
 
  if (choice === "1") {
    // Случайная генерация
    generateRandomMatrix();
  } else if (choice === "2") {
    // Ручной ввод
    numVertices = parseInt(numVerticesInput.value);
    if (numVertices < 2) {
      alert("Number of vertices must be at least 2.");
      return;
    }
 
    graph = [];
    graph2 = [];
 
    const continuous = isGraphContinuous(graph);
 
    if (continuous) {
      console.log("Граф является непрерывным.");
    } else {
      console.log("Граф не является непрерывным.");
    }
    
    // Определяем тип ввода: manual или random
    const inputChoice = document.getElementById("inputChoice").value;
 
    for (let i = 0; i < numVertices; i++) {
      const row = [];
      for (let j = 0; j < numVertices; j++) {
        if (i < j) {
          let weight;
 
          if (inputChoice === "manual") {
            // Если выбран ввод вручную, запрашиваем у пользователя вес
            do {
              weight = prompt(`Zadajte váhu pre hranu medzi vrcholom ${i} a vrcholom ${j}:`);
              if (weight === null) {
                // Пользователь нажал Cancel
                return;
              }
              weight = parseInt(weight);
              if (isNaN(weight) || weight < 0) {
                alert("Neplatný vstup. Prosím vložte platné nezáporné číslo.");
              }
            } while (isNaN(weight) || weight < 0);
          } else if (inputChoice === "random") {
            // Если выбран ввод случайных чисел, генерируем случайный вес в указанном диапазоне
            const minWeight = parseInt(document.getElementById("minWeight").value);
            const maxWeight = parseInt(document.getElementById("maxWeight").value);
            weight = Math.floor(Math.random() * (maxWeight - minWeight + 1)) + minWeight;
          }
 
          row.push(weight);
        } else {
          row.push(graph[j][i]);
        }
      }
      graph2.push(row);
    }
 
  graph = graph2;
  }
 
// Проходим по верхнему треугольнику матрицы (без диагонали)
  for (let i = 0; i < numVertices; i++) {
    for (let j = i + 1; j < numVertices; j++) {
      // Заполняем элементы симметрично относительно главной диагонали
      graph[j][i] = graph[i][j];
    }
  }
 
 
  updateMatrixTextArea(graph);
  updateMatrixTable(graph);
  updateTableHeaders(numVertices);
  updateNodeSelectOptions(numVertices);
  visualizeGraph();
}
 
 
 
 
 
 
function generateRandomMatrix() {
  numVertices = parseInt(numVerticesInput.value);
  if (numVertices < 2) {
    alert("Počet vrcholov musí byť aspoň 2.");
    return;
  }
 
   const minWeight = parseInt(document.getElementById("minWeight").value);
  const maxWeight = parseInt(document.getElementById("maxWeight").value);
 
  if (isNaN(minWeight) || isNaN(maxWeight) || minWeight < 0 || maxWeight < minWeight) {
    alert("Neplatný vstup pre váhy. Zadajte nezáporné čísla a uistite sa, že maxWeight je väčšia alebo rovná minWeight.");
    return;
  }
 
  graph = generateRandomAdjacencyMatrix(numVertices, minWeight, maxWeight);
  updateMatrixTextArea(graph);
  updateMatrixTable(graph);
  updateTableHeaders(numVertices);
  updateNodeSelectOptions(numVertices);
  visualizeGraph();
}
 
function updateMatrixTextArea(matrix) {
  const matrixText = matrix.map(row => row.join(" ")).join("\n");
  adjacencyMatrixTextArea.value = matrixText;
}
 
function updateNodeSelectOptions(numVertices) {
  startNodeSelect.innerHTML = "";
  endNodeSelect.innerHTML = "";
  for (let i = 0; i < numVertices; i++) {
    const option = document.createElement("option");
    option.value = i;
    option.text = i.toString();
    startNodeSelect.appendChild(option);
    endNodeSelect.appendChild(option.cloneNode(true));
  }
  startNodeSelect.selectedIndex = 0;
  endNodeSelect.selectedIndex = 1;
}
 
function parseAdjacencyMatrix(matrixText) {
  const lines = matrixText.trim().split('\n');
  const matrix = [];
  for (let line of lines) {
    const row = line.trim().split(' ').map(Number);
    matrix.push(row);
  }
  return matrix;
}
 
function generateRandomAdjacencyMatrix(numVertices, minWeight, maxWeight) {
  const matrix = [];
  for (let i = 0; i < numVertices; i++) {
    const row = [];
    for (let j = 0; j < numVertices; j++) {
      if (i === j) {
        row.push(0);
      } else if (j > i) {
        // Генеруємо випадкові ваги в заданому діапазоні
        row.push(Math.floor(Math.random() * (maxWeight - minWeight + 1)) + minWeight);
      } else {
        // Використовуємо значення з симетричної частини матриці
        row.push(matrix[j][i]);
      }
    }
    matrix.push(row);
  }
  return matrix;
}
 
function updateMatrixTable(matrix) {
  const matrixTable = document.getElementById("matrixTable");
  matrixTable.innerHTML = ""; // Очищаем существующее содержимое таблицы
 
  for (let i = 0; i < matrix.length; i++) {
    const row = document.createElement("tr");
    const vertexHeader = document.createElement("td");
    vertexHeader.textContent = i;
    row.appendChild(vertexHeader);
 
    for (let j = 0; j < matrix[i].length; j++) {
      const cell = document.createElement("td");
      cell.textContent = matrix[i][j];
      row.appendChild(cell);
    }
 
    matrixTable.appendChild(row);
  }
}
 
function updateTableHeaders(numVertices) {
  const table = document.querySelector("table");
  const thead = table.querySelector("thead tr");
  thead.innerHTML = ""; // Очищаем существующие заголовки
 
  const emptyTh = document.createElement("th");
  thead.appendChild(emptyTh); // Пустая ячейка в верхнем левом углу
 
  for (let i = 0; i < numVertices; i++) {
    const th = document.createElement("th");
    th.textContent = i;
    thead.appendChild(th);
  }
}
 
function drawGraph() {
  const numVertices = graph.length;
  const vertexRadius = 20;
  const circleRadius = vertexRadius * numVertices * 1.5;
  const textOffset = 15;
 
  canvas.width = circleRadius * 2 + 50;
  canvas.height = circleRadius * 2 + 50;
  const centerX = canvas.width / 2;
  const centerY = canvas.height / 2;
 
  vertexPositions = [];
  for (let i = 0; i < numVertices; i++) {
    const angle = (i / numVertices) * 2 * Math.PI;
    const x = centerX + circleRadius * Math.cos(angle);
    const y = centerY + circleRadius * Math.sin(angle);
 
    for (let j = 0; j < i; j++) {
      while (circlesIntersect(x, y, vertexRadius, vertexPositions[j].x, vertexPositions[j].y, vertexRadius)) {
        x += textOffset;
      }
    }
 
    vertexPositions.push({ x, y });
  }
 
  ctx.clearRect(0, 0, canvas.width, canvas.height);
 
  for (let i = 0; i < numVertices; i++) {
    const x = vertexPositions[i].x;
    const y = vertexPositions[i].y;
 
    // Измените цвет вершины на светло-синий
    ctx.beginPath();
    ctx.arc(x, y, vertexRadius, 0, 2 * Math.PI);
    ctx.fillStyle = "lightblue"; // Измените цвет здесь
    ctx.fill();
    ctx.strokeStyle = "black";
    ctx.stroke();
 
    ctx.textAlign = "center";
    ctx.textBaseline = "middle";
    ctx.font = "bold 16px Arial";
    ctx.fillStyle = "black";
    ctx.fillText(i.toString(), x, y);
  }
 
  ctx.strokeStyle = "gray";
  ctx.lineWidth = 1;
  for (let i = 0; i < numVertices; i++) {
    for (let j = i + 1; j < numVertices; j++) {
      if (graph[i][j] !== 0) {
        const x1 = vertexPositions[i].x;
        const y1 = vertexPositions[i].y;
        const x2 = vertexPositions[j].x;
        const y2 = vertexPositions[j].y;
 
        const dx = x2 - x1;
        const dy = y2 - y1;
        const distance = Math.sqrt(dx * dx + dy * dy);
        const ratio = vertexRadius / distance;
 
        const newX1 = x1 + dx * ratio;
        const newY1 = y1 + dy * ratio;
        const newX2 = x2 - dx * ratio;
        const newY2 = y2 - dy * ratio;
 
        ctx.beginPath();
        ctx.moveTo(newX1, newY1);
        ctx.lineTo(newX2, newY2);
 
        ctx.strokeStyle = "lightgray";
 
        // Рассчитываем координаты для текста веса ребра
        const textX = (newX1 + newX2) / 2;
        const textY = (newY1 + newY2) / 2;
 
        // Перемещаем текст на некоторое расстояние от линии ребра
        const textOffsetX = (dx / distance) * 10;
        const textOffsetY = (dy / distance) * 10;
 
        ctx.textAlign = "center";
        ctx.textBaseline = "middle";
        const textColor = "black"; // Используем цвет ребра для текста
        ctx.font = "bold 16px Arial";
        ctx.fillStyle = textColor;
        ctx.fillText(graph[i][j].toString(), textX + textOffsetX, textY + textOffsetY);
 
        ctx.stroke();
      }
    }
  }
}
 
 
function circlesIntersect(x1, y1, r1, x2, y2, r2) {
  const dx = x2 - x1;
  const dy = y2 - y1;
  const distance = Math.sqrt(dx * dx + dy * dy);
  return distance < r1 + r2;
}
 
function visualizeGraph() {
  const matrixText = adjacencyMatrixTextArea.value;
  graph = parseAdjacencyMatrix(matrixText);
  drawGraph();
}
 
/*Algorithm start button click*/
 
function visualizeAlgorithm() {
  document.getElementById('resultAlg').style.display = "block";
  if (algorithmType === "prim") {
    visualizeRoute();
  } else if (algorithmType === "kruskal") {
    visualizeKruskal();
  }
}
 
 
/*Prima alhorithm*/
 
function visualizeRoute() {
  document.getElementById("visitedVertices").textContent = "";
  const start = parseInt(startNodeSelect.value);
  const end = parseInt(endNodeSelect.value);
 
  if (start === end) {
    return;
  }
 
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  drawGraph();
 
  const parent = prim(graph, start);
  const route = findOptimalRoute(start, end, parent);
 
  drawRouteWithAnimation(route, vertexPositions);
}
 
function prim(graph, startVertex) {
  const parent = new Array(numVertices).fill(-1);
  const key = new Array(numVertices).fill(Infinity);
  const inMST = new Array(numVertices).fill(false);
 
  key[startVertex] = 0;
 
  for (let count = 0; count < numVertices - 1; count++) {
    const u = minKey(key, inMST);
 
    inMST[u] = true;
 
    for (let v = 0; v < numVertices; v++) {
      if (graph[u][v] && !inMST[v] && graph[u][v] < key[v]) {
        parent[v] = u;
        key[v] = graph[u][v];
      }
    }
  }
 
  return parent;
}
 
function minKey(key, mstSet) {
  let min = Number.POSITIVE_INFINITY;
  let minIndex = -1;
 
  for (let v = 0; v < key.length; v++) {
    if (!mstSet[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }
 
  return minIndex;
}
 
function findOptimalRoute(start, end, parent) {
  let current = end;
  const route = [];
 
  while (current !== start) {
    route.unshift(current);
    current = parent[current];
  }
  route.unshift(start);
 
  return route;
}
 
function drawRouteWithAnimation(route, vertexPositions) {
  ctx.strokeStyle = "red";
  ctx.lineWidth = 2;
  let currentIndex = 0;
 
  function animate() {
    if (currentIndex < route.length - 1) {
      const u = route[currentIndex];
      const v = route[currentIndex + 1];
      const x1 = vertexPositions[u].x;
      const y1 = vertexPositions[u].y;
      const x2 = vertexPositions[v].x;
      const y2 = vertexPositions[v].y;
 
      // Рассчитываем координаты окружности вершины для начала и конца линии
      const dx1 = x2 - x1;
      const dy1 = y2 - y1;
      const distance1 = Math.sqrt(dx1 * dx1 + dy1 * dy1);
      const radius1 = 20; // Радиус кружков вершин
      const ratio1 = radius1 / distance1;
 
      const newX1 = x1 + dx1 * ratio1;
      const newY1 = y1 + dy1 * ratio1;
      const newX2 = x2 - dx1 * ratio1;
      const newY2 = y2 - dy1 * ratio1;
 
      ctx.beginPath();
      ctx.moveTo(newX1, newY1);
      ctx.lineTo(newX2, newY2);
      ctx.stroke();
 
      const routeLength = calculateRouteLength(route.slice(0,currentIndex+1));
      document.getElementById("routeLength").textContent = routeLength.toFixed(2);
      document.getElementById("visitedVertices").textContent = document.getElementById("visitedVertices").textContent + route[currentIndex]  + " ➝ ";
 
      currentIndex++;
 
      if (currentIndex < route.length - 1) {
        setTimeout(animate, 1000); // Настройте скорость анимации по желанию  
      }
      else
      {
        const routeLength = calculateRouteLength(route);
        document.getElementById("routeLength").textContent = routeLength.toFixed(2);
        document.getElementById("visitedVertices").textContent = document.getElementById("visitedVertices").textContent + route[currentIndex];
      }
    }
  }
 
  animate();
}
 
function calculateRouteLength(route) {
  let length = 0;
  for (let i = 0; i < route.length - 1; i++) {
    const u = route[i];
    const v = route[i + 1];
    length += graph[u][v];
  }
  return length;
}
 
 
 
/*Kruskal algorithm*/
 
function visualizeKruskal() {
  document.getElementById("visitedVertices").textContent = "";
  const matrixText = adjacencyMatrixTextArea.value;
  graph = parseAdjacencyMatrix(matrixText);
  drawGraph();
  const edges = kruskal(graph);
  drawKruskal(edges);
}
 
function kruskal(graph) {
  const numVertices = graph.length;
 
  // Створення масиву ребер для впорядкування
  const edges = [];
  for (let i = 0; i < numVertices; i++) {
    for (let j = i + 1; j < numVertices; j++) {
      if (graph[i][j] !== 0) {
        edges.push({ u: i, v: j, weight: graph[i][j] });
      }
    }
  }
 
  // Сортування ребер за зростанням ваги
  edges.sort((a, b) => a.weight - b.weight);
 
  const parent = Array(numVertices).fill(-1);
  const result = [];
 
  function find(v) {
    if (parent[v] === -1) {
      return v;
    }
    return find(parent[v]);
  }
 
  function union(x, y) {
    const xRoot = find(x);
    const yRoot = find(y);
    parent[xRoot] = yRoot;
  }
 
  for (let i = 0; i < edges.length; i++) {
    const { u, v, weight } = edges[i];
    const x = find(u);
    const y = find(v);
 
    if (x !== y) {
      result.push(edges[i]);
      union(x, y);
    }
  }
 
  return result;
}
 
function drawKruskal(edges) {
  const animationSpeed = 1000; // Швидкість анімації в мілісекундах
  let currentEdgeIndex = 0;
  const vertexRadius = 20;
  let totalRouteLength = 0;
 
  function drawNextEdge() {
    if (currentEdgeIndex < edges.length) {
      const { u, v, weight } = edges[currentEdgeIndex];
 
      const x1 = vertexPositions[u].x;
      const y1 = vertexPositions[u].y;
      const x2 = vertexPositions[v].x;
      const y2 = vertexPositions[v].y;
 
      const dx = x2 - x1;
      const dy = y2 - y1;
      const distance = Math.sqrt(dx * dx + dy * dy);
      const ratio = vertexRadius / distance;
 
      const startX = x1 + dx * ratio;
      const startY = y1 + dy * ratio;
      const endX = x2 - dx * ratio;
      const endY = y2 - dy * ratio;
 
      ctx.beginPath();
      ctx.moveTo(startX, startY);
      ctx.lineTo(endX, endY);
      ctx.strokeStyle = "green"; // Зелений колір для ребра у маршруті
      ctx.lineWidth = 2;
      ctx.stroke();
 
      totalRouteLength += weight;
      
      updateResult(u,v,totalRouteLength,currentEdgeIndex === (edges.length-1));
 
      currentEdgeIndex++;
 
      document.addEventListener("keydown", function(event) {
        if (event.key === "Enter") {
          drawNextEdge();
        }
      });
      
      // Викликаємо наступний кадр анімації
      setTimeout(drawNextEdge, animationSpeed);
    }
  }
 
  // Запускаємо анімацію
  drawNextEdge();
}
 
function updateResult(u,v, length,flag){
// Оновіть відображення довжини маршруту
    document.getElementById("routeLength").textContent = length;
    // Додайте вершини до списку
    document.getElementById("visitedVertices").textContent = document.getElementById("visitedVertices").textContent + u;
    document.getElementById("visitedVertices").textContent = document.getElementById("visitedVertices").textContent + " ➝ ";
    document.getElementById("visitedVertices").textContent = document.getElementById("visitedVertices").textContent + v ;
    if(!flag)
      document.getElementById("visitedVertices").textContent = document.getElementById("visitedVertices").textContent + "; ";
}
 
 
 
document.addEventListener("DOMContentLoaded", function() {
  changeAlgorithm();
  // Автоматично викликаємо генерацію випадкового графа та візуалізацію при завантаженні сторінки
generateRandomMatrix();
});