Интерактивная система для работы с графами

Описание проекта

Данный проект разработан для выполнения лабораторных работ, связанных с теорией графов, алгоритмами поиска кратчайших путей и моделированием передачи данных. Проект включает графический интерфейс, поддерживающий несколько задач (лабораторных работ), таких как редактирование графов, визуализация алгоритмов Дейкстры и Флойда, а также моделирование передачи пакетов в сетях.

---

Структура проекта

infproc/
├── graphlib/                 # Библиотека для работы с графами
│   ├── __init__.py           # Инициализация библиотеки
│   ├── algorithms.py         # Реализация алгоритмов графов (Дейкстра, Флойд)
│   ├── io.py                 # Работа с сохранением/загрузкой графов
│   ├── tooltip.py            # Работа с подсказкой для матрицы смежности
│   ├── ui.py                 # Обработчики пользовательского интерфейса
│   └── utils.py              # Утилиты для работы с вершинами, рёбрами и матрицами
├── saves/                    # Папка для хранения сохранённых файлов
├── tasks/                    # Задачи (лабораторные работы)
│   ├── base_graph.py         # Основной класс, от которого наследуются все последющие графы
│   ├── first_task.py         # Редактор графов
│   ├── second_task.py        # Алгоритмы Дейкстры и Флойда
│   ├── third_task.py         # Симуляция передачи пакетов
│   └── four_task.py          # Запуск и работа с HTTP сервером на http.server
├── .gitignore                # Настройки Git для исключения файлов
├── main.py                   # Главное меню приложения
└── readme.md                 # Описание проекта (текущий файл)

---

Установка и запуск

Требования

• Python 3.10 или выше.

Установка

1. Клонируй репозиторий:

   git clone <URL-репозитория>
   cd infproc

2. Установи виртуальное окружение (рекомендуется):

   python -m venv .venv
   .venv\Scripts\activate

Запуск

Запусти главное меню:

python main.py

---

Лабораторные работы

1. Редактор графов

Модуль: tasks.first_task.py
Описание:
Позволяет создавать, редактировать и сохранять графы.
Функционал:

• Добавление и удаление вершин.
• Добавление рёбер с указанием веса.
• Изменение направлений и весов рёбер.
• Сохранение и загрузка графов в формате JSON.

2. Алгоритмы Дейкстры и Флойда

Модуль: tasks.second_task.py
Описание:
Визуализация алгоритмов поиска кратчайших путей.
Функционал:

• Запуск алгоритма Дейкстры для всех пар вершин.
• Запуск алгоритма Флойда для всех пар вершин.
• Сравнение времени выполнения двух алгоритмов.
• Подсветка маршрутов на графе.

3. Симуляция передачи пакетов

Модуль: tasks.third_task.py
Описание:
Моделирование передачи пакетов по сети с использованием различных алгоритмов маршрутизации.
Функционал:

• Создание маршрутов между узлами.
• Реализация виртуального канала (для всех доступных узлов).
• Реализация дейтаграммного метода для случайной маршрутизации.
• Визуализация процесса передачи пакетов.
• Отображение параметров пакетов (адрес отправителя и назначения, номер пакета, маршрут и размер).
• Симуляция передачи данных с учётом задержек и пропускной способности.
• Формирование и отображение таблиц маршрутизации (для алгоритма маршрутизации по предыдущему опыту).

4. Работа с протоколом HTTP

Модуль: tasks.four_task.py
Описание:
Интерактивный инструмент для работы с протоколом HTTP. Пользователь может выполнять различные HTTP-запросы и работать с заголовками и содержимым ответов сервера. Приложение также включает в себя встроенный CGI-сервер.

Функционал:

• Получение опций сервера:
  Отправка HTTP-запроса с методом OPTIONS для получения доступных методов и настроек сервера. Возможность получения информации о конкретном ресурсе, если заранее указан URL.

• GET, POST, HEAD запросы:
  Отправка стандартных запросов HTTP с возможностью сохранения заголовков ответа и содержимого в папке saves.

• POST-запрос для получения переменных окружения:
  Специальный запрос на встроенный CGI-скрипт (environment.py), который отображает переменные окружения сервера в виде HTML-таблицы.

• Работа с заранее указанным URL:
  Переменная self.predefined_url позволяет задавать URL ресурса, который будет использоваться по умолчанию. Если переменная не задана, пользователь будет запрошен на ввод URL.

Встроенный CGI-сервер:

• Автоматически запускается при открытии модуля на локальном адресе http://localhost:8000.
• Обработчик CGI-запросов запускается в отдельном потоке.
• Включает встроенный скрипт environment.py, который генерирует HTML-страницу с переменными окружения сервера.

Сохранение данных:

• Заголовки ответа сохраняются в файлы response_headers_<method>.txt в папке saves.
• Содержимое ответа сохраняется в файлы response_content_<method>.html в папке saves.

Пример работы с self.predefined_url:

• Для выполнения запросов без необходимости ввода URL вручную (указанного преподавателем ресурса) можно указать заранее известный адрес в переменной self.predefined_url. Если переменная пустая, приложение запросит адрес у пользователя через графический интерфейс.

Завершение работы:

• При закрытии приложения сервер CGI автоматически завершает свою работу. Пользователь подтверждает выход через диалоговое окно.

---

Компоненты

1. graphlib

Библиотека для работы с графами:

• algorithms.py: Реализация алгоритмов Дейкстры, Флойда-Уоршелла, утилиты для восстановления и построения путей.
• io.py: Функции сохранения и загрузки графов в формате JSON.
• tooltip.py: Управление подсказками для матрицы смежности и интерфейса.
• ui.py: Обработчики событий пользовательского интерфейса, анимация и визуализация.
• utils.py: Управление вершинами, рёбрами, матрицами и общая функциональность графов.

2. main.py

Главное меню приложения с кнопками для запуска отдельных лабораторных работ.
Функционал:

• Выбор и запуск задач.
• Управление переходами между заданиями.
• Выход из приложения.

---