Блок задач

4. Один класс

Темы
Сложность 5

Задача «Топологическая сортировка»

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

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

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

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

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

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

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

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

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

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

Задача

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

Интерфейс класса:

  1. Добавить узел. У метода два аргумента: имя узла (std::string) и список зависимостей (std::vector<std::string>). Все перечисленные узлы из обоих аргументов добавляются в список узлов (если не были добавлены ранее). Также регистрируются зависимости.
  2. Сортировка. Метод возвращает результат в std::vector<std::string> с именами узлов в отсортированном порядке.

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

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

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

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

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

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

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