src/graph/Graph.java - master - victor_t/simple_navigator

src/graph/Graph.java
196 строк7 KB
Victor
fix: library classes
06 июл 2026, 01:06
06 июл 2026, 01:0641665e7
package graph;

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * Класс, представляющий граф с использованием матрицы смежности.
 * Поддерживает как ориентированные, так и неориентированные графы.
 * Нумерация вершин в методах, принимающих аргументы-вершины, начинается с 1.
 */
public class Graph {
  /**
   * Количество вершин в графе.
   */
  private int size;

  /**
   * Флаг, указывающий, является ли граф ориентированным.
   * Если false, граф считается неориентированным.
   */
  private boolean isDirected;

  /**
   * Матрица смежности графа.
   * Элемент matrix[i][j] != 0 означает наличие ребра (i+1) → (j+1).
   * Для неориентированного графа матрица симметрична.
   */
  private int[][] adjacencyMatrix;

  /**
   * Конструктор по умолчанию.
   * Создаёт граф из одной вершины без рёбер (неориентированный).
   */
  public Graph() {
    this.size = 1;
    this.isDirected = false;
    this.adjacencyMatrix = new int[1][1];
  }

  /**
   * Загружает граф из текстового файла.
   * Формат файла:
   * - первое целое число — количество вершин N;
   * - затем N строк по N целых чисел — матрица смежности.
   * После загрузки автоматически определяется ориентированность графа.
   *
   * @param filename имя файла для загрузки
   * @throws IOException если файл не найден, имеет неверный формат или
   *                     не удаётся прочитать данные
   */
  public void loadGraphFromFile(String filename) throws IOException {
    File file = new File(filename);
    if (!file.exists()) {
      throw new IOException("File not found: " + filename);
    }
    try (Scanner scanner = new Scanner(file)) {
      if (!scanner.hasNextInt()) {
        throw new IOException("Invalid file format: missing graph size");
      }
      size = scanner.nextInt();
      if (size < 1) {
        throw new IOException("Invalid graph size: " + size);
      }
      adjacencyMatrix = new int[size][size];
      for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
          if (!scanner.hasNextInt()) {
            throw new IOException("Invalid file format: not enough values");
          }
          adjacencyMatrix[i][j] = scanner.nextInt();
        }
      }
      checkDirected();
    }
  }

  /**
   * Экспортирует граф в формат DOT (используемый программой Graphviz).
   * Для ориентированного графа создаётся digraph, для неориентированного — graph.
   * Вершины нумеруются с 1.
   *
   * @param filename имя файла для сохранения
   * @throws IOException если возникает ошибка при записи в файл
   */
  public void exportGraphToDot(String filename) throws IOException {
    try (PrintWriter writer = new PrintWriter(filename)) {
      if (isDirected) {
        writer.println("digraph {");
        for (int i = 0; i < size; i++) {
          for (int j = 0; j < size; j++) {
            if (adjacencyMatrix[i][j] != 0) {
              writer.println("  " + (i + 1) + " -> " + (j + 1) + ";");
            }
          }
        }
      } else {
        writer.println("graph {");
        for (int i = 0; i < size; i++) {
          for (int j = i + 1; j < size; j++) {
            if (adjacencyMatrix[i][j] != 0) {
              writer.println("  " + (i + 1) + " -- " + (j + 1) + ";");
            }
          }
        }
      }
      writer.println("}");
    }
  }

  /**
   * Возвращает количество вершин в графе.
   *
   * @return размер графа
   */
  public int getSize() {
    return size;
  }

  /**
   * Возвращает копию матрицы смежности.
   *
   * @return двумерный массив, представляющий матрицу смежности
   */
  public int[][] getAdjMatrix() {
    int[][] copy = new int[size][size];
    for (int i = 0; i < size; i++) {
      copy[i] = Arrays.copyOf(adjacencyMatrix[i], size);
    }
    return copy;
  }

  /**
   * Возвращает список соседей указанной вершины (нумерация с 1).
   *
   * @param vertex номер вершины (1-indexed)
   * @return список номеров вершин-соседей (также 1-indexed)
   */
  public List<Integer> getNeighboringVertices(int vertex) {
    List<Integer> neighbors = new ArrayList<>();
    int v = vertex - 1;
    for (int j = 0; j < size; j++) {
      if (adjacencyMatrix[v][j] != 0) {
        neighbors.add(j + 1);
      }
    }
    return neighbors;
  }

  /**
   * Определяет, является ли граф ориентированным, на основе симметрии матрицы смежности.
   * Результат сохраняется в поле isDirected.
   */
  private void checkDirected() {
    for (int i = 0; i < size; i++) {
      for (int j = i + 1; j < size; j++) {
        if (adjacencyMatrix[i][j] != adjacencyMatrix[j][i]) {
          isDirected = true;
          return;
        }
      }
    }
    isDirected = false;
  }

  /**
   * Возвращает вес ребра между вершинами графа.
   *
   * Номера вершин считаются начиная с 1.
   *
   * @param from начальная вершина
   * @param to конечная вершина
   * @return вес ребра между вершинами (значение из матрицы смежности)
   */
  public int getDistance(int from, int to) {
    return adjacencyMatrix[from - 1][to - 1];
  }

  /**
   * Проверяет наличие ребра между двумя вершинами графа.
   *
   * Номера вершин считаются начиная с 1.
   *
   * @param from начальная вершина
   * @param to конечная вершина
   * @return true, если существует ребро между вершинами, иначе false
   */
  public boolean hasEdge(int from, int to) {
    return adjacencyMatrix[from - 1][to - 1] != 0;
  }

}