tsort

1. Что такое команда tsort и зачем она нужна

Команда tsort входит в пакет GNU coreutils и реализует алгоритм топологической сортировки ориентированных ациклических графов (DAG).
Топология – порядок, при котором каждый ребро указывает от «первоначального» узла к «следующему». В результате выполнения tsort вы получаете список вершин, удовлетворяющий всем ограничениям рёбер.

1.1 Формат входных данных

Текстовый поток вида A B означает ребро от вершины A к вершине B. Вход может содержать:

• пробелы, табуляцию или новую строку как разделители;
• комментарии, начинающиеся с символа #;
• пустые строки, которые игнорируются.

1.2 Вывод

Команда выводит одну вершину на строке в порядке топологической сортировки. Если граф содержит цикл, tsort выдаёт сообщение об ошибке и завершает работу с кодом возврата >0.

2. Алгоритмическая реализация

Команда использует модифицированный алгоритм Кана (Kahn’s algorithm).
Пошагово:

1. Сканирование входа – построение списка смежности и подсчёт в‑града каждой вершины.
2. Инициализация очереди – все вершины с нулевым в‑градом помещаются в очередь.
3. Периодический разбор – извлекаем вершину, выводим её, уменьшаем в‑град соседей и при достижении нуля добавляем их в очередь.
4. Контроль за циклом – если после завершения цикла количество обработанных вершин меньше общего числа, граф содержит цикл.

Алгоритм работает за O(V+E) времени и использует память O(V+E), где V — число вершин, E — рёбер.

2.1 Оптимизации при больших графах

• Потоковый ввод: команда читает вход построчно, не загружая весь файл в память.
• Сжатие строк: идентичные строки объединяются, чтобы уменьшить количество ключей в хеш‑таблице.

3. Практические сценарии применения

3.1 Сборка зависимостей программного обеспечения

Многие менеджеры пакетов (apt, yum) используют топологическую сортировку для установки пакетов в правильном порядке. Команда tsort может служить вспомогательным инструментом при анализе графов зависимостей вручную.

3.2 Планирование задач в CI/CD

В пайплайнах непрерывной интеграции задачи часто зависят друг от друга (например, тесты после сборки). Создавая файл с зависимостями вида build test deploy, можно автоматически получить порядок выполнения команд:

cat deps.txt | tsort > order.txt

cat deps.txt | tsort > order.txt

3.3 Анализ сетевых маршрутов

При моделировании маршрутизации в компьютерных сетях топология сети может быть представлена как DAG, а команда tsort поможет определить корректный порядок проброса пакетов.

4. Расширенные возможности и альтернативы

4.1 Варианты вывода

• --sort (по умолчанию) – стандартная сортировка.
• --no-sort – вывод в порядке обнаружения, полезно при анализе конкретных ветвей графа.

4.2 Слияние с другими утилитами

Комбинируя tsort с awk или grep можно фильтровать узлы по критериям:

cat deps.txt | grep '^build' | tsort > build_order.txt

cat deps.txt | grep '^build' | tsort > build_order.txt

4.3 Альтернативы в экосистеме Linux

5. Чаще возникающие вопросы и ответы

• Как обрабатывать циклы?
  При наличии цикла tsort выдаёт сообщение «cycle detected» и завершает работу с кодом 1. Можно перехватить это в скрипте и вывести более информативный вывод.
• Можно ли задать начальную вершину?
  Встроенной опции нет, но можно предварительно добавить нулевое ребро к нужной вершине для того, чтобы она оказалась первой.
• Как ускорить обработку больших файлов?
  Используйте sort -u перед передачей в tsort, чтобы удалить дубликаты. Также применяйте xargs -n1 tsort при параллельном разборе разделенных подграфов.