У меня есть ориентированный циклический граф с циклами разной длины.Мне нужно выяснить топологическое упорядочение вершин, учитывая источник.
Я поднял глаза и обнаружил, что UNIX's tsort делает это.Таким образом, для ввода ниже в терминале,
tsort << EOF
>1 2
>2 3
>3 1
>1 4
>EOF
я получаю следующий вывод.
tsort: cycle in data
tsort: 1
tsort: 2
tsort: 3
3
1
4
2
Я получаю циклы в графе, а также топологическое упорядочение вершин.
Я смотрел на реализацию tsort здесь .Он использует сбалансированное дерево.
Проблема в том, что у меня есть огромный граф с миллионами вершин и ребер зависимостей.Так что это может занять много дополнительного пространства для дерева (учитывая, что у меня уже есть график) и может быть медленным.
Есть ли другой эффективный способ добиться этого?А также я должен ввести еще один параметр, который называется " iterations_count ".Поэтому, оценивая вершины на основе топологического порядка, я должен пройти через вершины в цикле ровно столько раз, сколько указано в iterations_count .
Например, на приведенном выше графике цикл равен 1-2-3, а если значение iterations_count равно 3, я должен оценить вершины в этом цикле три раза.