LamaGraph

Inets-isomorphism - утилита командной строки (CLI) на Haskell для поиска точного графового изоморфизма. Реализует алгоритм структурного сопоставления графов с отсечением неперспективных ветвей (бэктрекинг), аналогичный подходу VF2.

Архитектура

Процесс поиска изоморфизма разбит на два этапа:

1. Эвристический фильтр (Invariants.hs): Проверка базовых графовых инвариантов (количество вершин, рёбер, распределение степеней) за O(1).
2. Топологическое сопоставление (Isomorphism.hs): Обход дерева состояний с использованием монады State. Алгоритм строит взаимно однозначное отображение между узлами графов, откатываясь (backtracking) при обнаружении топологических противоречий.

Стек технологий

• Язык: Haskell (GHC 9.10.3)
• Сборка: Stack
• Зависимости:
  • fgl (Functional Graph Library) - внутреннее представление графов.
  • hspec, QuickCheck — тестирование.

Установка и сборка

Для сборки проекта на вашей машине должен быть установлен stack.

git clone [https://github.com/Lamagraph/inets-isomorphism.git](https://github.com/Lamagraph/inets-isomorphism.git)
cd inets-isomorphism
stack build

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

Проект покрыт модульными тестами (проверка краевых случаев) и property-based тестами (QuickCheck генерирует сотни случайных графов для математической валидации свойств изоморфизма).

stack test

CI/CD

В репозитории настроен GitHub Actions пайплайн (.github/workflows/ci.yml). При каждом пуше в ветку main или создании Pull Request сервер автоматически выполняет:

1. Кэширование зависимостей (Pantry/GHC).
2. Сборку проекта (stack build).
3. Запуск тестов (stack test --system-ghc).

Лицензия

Проект распространяется под лицензией MIT.