Исправление и тестирование Python-алгоритма Push–Relabel

Используемые навыки Git Python Отладка Регрессионное тестирование Тестирование / QA

Описание

Личный технический проект по переработке исследовательского прототипа алгоритма максимального потока Push–Relabel.

Исходный код находился в Jupyter Notebook и содержал несколько вариантов алгоритма. Его было сложно повторно использовать и надёжно проверять: отсутствовали единый публичный интерфейс, систематические регрессионные тесты и независимая проверка результатов.

При тестировании были выявлены две воспроизводимые проблемы:
— неверный подсчёт максимального потока на графах с рёбрами, входящими в источник;
— незавершение варианта с global relabeling на отдельных входных данных.

Цель проекта — найти причины дефектов, исправить алгоритмическую логику, отделить её от исследовательского notebook и подготовить понятный воспроизводимый Python-модуль с проверяемыми результатами.

Решение

Программная логика была вынесена из Jupyter Notebook в отдельный тестируемый Python-модуль.

В ходе работы:
— пять вариантов Push–Relabel приведены к общему интерфейсу;
— добавлены публичная функция compute_max_flow и класс PushRelabelHighest;
— исправлен подсчёт потока при наличии рёбер, входящих в источник;
— скорректирована обработка меток недостижимых от стока вершин, вызывавшая незавершение global relabeling;
— реализована независимая эталонная версия Edmonds–Karp для сравнительной проверки;
— написаны регрессионные и сравнительные тесты для циклов, встречных рёбер, отсутствия пути, нескольких маршрутов и других граничных случаев;
— добавлена проверка того, что входной список рёбер не изменяется;
— подготовлены README, публичный API и инструкции по запуску.

Для проверки всех вариантов использовался общий набор детерминированных графов и единая эталонная реализация.

Результат

Получен воспроизводимый Python-модуль с единым публичным API, тестами и инструкциями по запуску.

Проверяемые результаты:
— проходят 17 регрессионных и сравнительных тестов;
— пять вариантов Push–Relabel сопоставлены с независимой реализацией Edmonds–Karp на общем наборе из 70 малых детерминированных графов;
— размеры проверочных графов составляют от 2 до 10 вершин, ёмкости рёбер — от 1 до 20;
— подтверждена корректная обработка циклов, встречных рёбер, рёбер в источник, рёбер из стока, отсутствия пути и нескольких маршрутов;
— входной список рёбер при вычислении не изменяется;
— устранены два воспроизводимых дефекта: неверный результат и незавершение алгоритма.

Репозиторий можно клонировать, установить зависимости и проверить стандартной командой запуска тестов. Проект демонстрирует работу с ошибочным и зависающим Python-кодом: от локализации причины до исправления, регрессионного тестирования и независимой проверки результата.