Студент

Курдюков Алексей

Задача

Топологическая сортировка

Состояние

Завершено

Баллов

5

Дедлайн

Назначено

27.10.2014, 12:55

Завершено

17.11.2014, 17:41

Требуется реализовать программу, которая осуществляет топологическую сортировку аналогично тому, как это делает программа make.

Входные данные

Файл с графом зависимостей в следующем формате:

<узел_A> = <узел_A1>, <узел_A2>, ... <узел_AN>
<узел_B> = <узел_B1>, <узел_B2>, ... <узел_BN>
...

При таком формате данных, слева от знака = записывается имя зависимого узла, а справа — список (упорядоченный) узлов от которых зависит данный узел. Имя узла — это строка, которая не содержит пробелов в начале и в конце, но может содержать пробелы в середине.

Пример графа зависимостей

поехать в магазин = сесть в машину, тронуться, ехать, остановиться у магазина

сесть в машину = открыть водительскую дверь, сесть на сиденье, закрыть дверь, пристегнуть ремень

тронуться = сесть на сиденье, завести мотор, нажать на тормоз, отпустить ручник, включить поворотник, отпустить тормоз, нажать на газ

остановиться у магазина = ехать, увидеть магазин, нажать на тормоз, остановить автомобиль, затянуть ручник

Задача

Разработать программу, на вход которой подаётся граф зависимостей, и которая осуществляет сортировку, т. е. выстраивает узлы в таком порядке, чтобы ни один узел не шёл раньше, чем любой из узлов, от которых он зависит.

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

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

Выходные данные

Файл с отсортированным списком узлов:

<узел_1>
<узел_2>
...

Для приведённого выше примера, одна из возможных последовательностей узлов после топологической сортировки будет следующей:

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