Graphate

Graphate — настольное приложение для интерактивной визуализации и пошаговой трассировки алгоритмов поиска экстремальных путей и минимальных остовных деревьев на графах.

Реализовано на Python 3.11 + PySide6 (Qt 6). Поддерживает загрузку реальных дорожных сетей из OpenStreetMap, синтетические генераторы графов, импорт/экспорт GraphML/JSON, а также режим карты с растровой подложкой.

Выпускная квалификационная работа, кафедра «Прикладная математика», НГТУ им. Р.Е. Алексеева.
Автор: Былов Вадим Михайлович, группа 22-ПМ-1.

---

Возможности

Алгоритмы (8 штук, с пошаговой трассировкой)

Группа	Алгоритм	Задача
Обходы	BFS	SPSP, невзвешенный кратчайший путь
Обходы	DFS	Обход, поиск пути
Обходы	IDDFS	SPSP, оптимальный по памяти
Кратчайшие пути	Dijkstra	SSSP, неотрицательные веса
Кратчайшие пути	A*	SPSP, с эвристикой (Евклид / Манхэттен)
Кратчайшие пути	Floyd–Warshall	APSP, все пары
Кратчайшие пути	Bellman–Ford	SSSP, произвольные веса, детектирование отриц. циклов
Остовные деревья	Prim	MST, от стартовой вершины
Остовные деревья	Kruskal	MST, жадный по рёбрам + DSU

• Поддержка min-пути и max-пути (переключатель в панели алгоритмов).
• Пошаговый таймлайн: перемотка вперёд/назад, воспроизведение с регулируемой скоростью.
• Теоретическая справка и учебный пример для каждого алгоритма (диалоги «Подробнее» и «Пример»).

Редактирование графа

• Создание вершин двойным кликом, рёбер — перетаскиванием между вершинами.
• Перемещение вершин мышью с синхронизацией через QGraphicsItem.ItemIsMovable.
• Rubber-band выделение: прямоугольная рамка выделяет несколько вершин; групповое перемещение и удаление через Delete.
• Undo/Redo (Ctrl+Z / Ctrl+Y): отмена перемещений и удалений через QUndoStack.
• Ввод графа через матрицу смежности (диалог произвольного размера).

Источники данных

Способ	Описание
Генераторы	Erdős–Rényi, Watts–Strogatz, Barabási–Albert, решётка, полный граф
GraphML	Стандартный академический формат (NetworkX-совместимый)
JSON	Собственный формат: {directed, nodes, edges}
OpenStreetMap	По названию района или bbox; кэш в samples/osm_cache/
Матрица смежности	Диалог ввода [[u, v, w], ...]

Карта района

• Режим «Карта»: граф OSM поверх растровой подложки.
• По умолчанию: CartoDB Positron (через contextily).
• При наличии ключа: Yandex Tiles API (настраивается в «Настройки → Конфигурация»).
• Мониторинг доступности сервисов в строке состояния (Nominatim, Overpass, CartoDB, Yandex).

Интерфейс

• Тёмная и светлая темы (меню «Настройки → Тема оформления»); стилизация заголовка окна Windows через DWM API.
• Масштабирование колесом мыши, панорамирование, сброс вида (Ctrl+0 / Ctrl+F).
• Три режима центральной панели: «Граф», «Граф + дерево обхода», «Карта».
• Статусная строка: масштаб, маркеры S/T, число вершин/рёбер, индикатор сети.

---

Скриншоты

Тёмная тема	Светлая тема

Скриншоты будут добавлены после финальной сборки.

---

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

Требования

• Python 3.11 (рекомендуется CPython 3.11.x)
• Windows 10/11 (основная платформа), Linux/macOS — без гарантии DWM-функций

Установка зависимостей

python -m venv .venv
.\.venv\Scripts\activate          # Windows
# source .venv/bin/activate       # Linux / macOS
pip install -r requirements.txt

OSMnx на Windows. Если pip install osmnx падает из-за geopandas/fiona, используйте conda: conda install -c conda-forge osmnx.

Запуск из исходников

python graphate_entry.py
# или
python -m app.main

Готовый исполняемый файл

Скачайте graphate.exe из раздела Releases — установка Python не требуется.

Для самостоятельной сборки:

pip install pyinstaller
python -m PyInstaller --noconfirm --clean graphate.spec
# результат: dist/graphate/graphate.exe

---

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

Graphate/
├── app/
│   ├── main.py                      # Точка входа, настройка логирования
│   ├── network_reachability.py      # Мониторинг внешних сервисов
│   ├── config/
│   │   └── user_settings.py         # Сохранение настроек (theme, api_key)
│   ├── core/
│   │   ├── graph_model.py           # Обёртка над networkx.MultiDiGraph + Qt-сигналы
│   │   ├── trace.py                 # Snapshot / Trace (пошаговая трассировка)
│   │   └── algorithms/              # 8 алгоритмов + базовый класс
│   │       ├── base.py
│   │       ├── bfs.py, dfs.py, iddfs.py
│   │       ├── dijkstra.py, astar.py, floyd_warshall.py, bellman_ford.py
│   │       └── prim.py, kruskal.py
│   ├── data/
│   │   ├── generators.py            # ER, WS, BA, grid, complete
│   │   ├── importers.py             # GraphML + JSON
│   │   ├── exporters.py
│   │   └── osm_loader.py            # OSMnx + дисковый кэш
│   ├── gui/
│   │   ├── main_window.py           # Главное окно — диспетчер
│   │   ├── canvas.py                # QGraphicsView (pan, zoom, rubber-band)
│   │   ├── graph_scene.py           # QGraphicsScene + VertexItem / EdgeItem
│   │   ├── algorithm_panel.py       # Выбор и запуск алгоритма
│   │   ├── styles.py                # Семантическая палитра (тёмная / светлая)
│   │   ├── undo_commands.py         # QUndoCommand: Move, Delete
│   │   ├── timeline.py              # Таймлайн (слайдер по снимкам)
│   │   ├── stats_panel.py           # Метрики + журнал шагов
│   │   ├── algorithm_theory.py      # HTML-тексты теории для диалогов
│   │   ├── example_dialog.py        # Диалог «Пример работы»
│   │   ├── map_view.py              # Режим карты (matplotlib + contextily)
│   │   ├── windows_titlebar.py      # DWM API для стилизации заголовка окна
│   │   └── adjacency_matrix_dialog.py
│   └── workers/
│       ├── algorithm_runner.py      # QThread для выполнения алгоритмов
│       └── osm_worker.py            # QThread для загрузки OSM
├── diagrams/                        # PlantUML-диаграммы + PNG
├── samples/                         # Демо-графы (.graphml, .json)
├── tests/                           # Pytest-тесты
├── graphate_entry.py                # Точка входа для PyInstaller
├── graphate.spec                    # Конфигурация PyInstaller
├── pyproject.toml
└── requirements.txt

---

Управление

Действие	Способ
Создать вершину	Двойной клик на пустом месте
Создать ребро	Правая кнопка → «Добавить ребро»
Выбрать источник / цель	Правая кнопка на вершине → «Сделать источником / целью»
Переместить вершину	Левая кнопка + перетаскивание
Выделить несколько	Левая кнопка на пустом месте + рамка
Удалить выделенные	Delete
Отменить / повторить	Ctrl+Z / Ctrl+Y
Панорамирование	Средняя кнопка мыши или Ctrl + левая
Масштаб	Колесо мыши
Сбросить вид	Ctrl+0
Подогнать по графу	Ctrl+F

---

Тестирование

pytest -q

Тесты покрывают:

• tests/test_bfs_dfs.py — BFS/DFS на сетках, полных графах, недостижимые вершины
• tests/test_dijkstra.py — сравнение Dijkstra и A* с эталоном NetworkX
• tests/test_bellman_ford.py — пути с отрицательными весами, детекция отриц. циклов
• tests/test_floyd_warshall.py — матрица расстояний APSP
• tests/test_prim_kruskal.py — корректность MST, суммарный вес
• tests/test_osm_loader.py — smoke-тест загрузчика OSM (пропускается без сети)

---

Зависимости

Библиотека	Назначение
PySide6 >= 6.7	GUI (Qt 6), сцена графов, сигналы
networkx >= 3.2	Хранение и обработка графов
osmnx >= 2.0	Загрузка дорожных сетей из OpenStreetMap
matplotlib >= 3.8	Режим карты, отрисовка рёбер
contextily >= 1.6	Растровые картографические тайлы
rasterio >= 1.3	Репроекция координат (EPSG:4326 ↔ EPSG:3857)
numpy >= 1.26	Векторные операции в режиме карты

---

Лицензия

MIT — см. файл LICENSE.