Топологическая сортировка с помощью алгоритма Кана

В одном из недавних проектов мы работали над созданием инструмента, похожего на электронную таблицу, в котором пользователи могли бы делать перекрестные ссылки на различные строки в формулах, как в Excel. Мы столкнулись с вопросом, как упорядочить оценку строк так, чтобы зависимости не вызывали конфликтов.

Например, представьте, что у нас есть три строки:

row1 может быть отображена напрямую, так как ее формула не зависит от других строк. Однако row2 ссылается на row3. row3 ссылается на row1. Таким образом, чтобы отобразить row2, нам сначала нужно отобразить row3.

Оказывается, это довольно распространенная проблема, например, при решении вопроса о порядке импорта различных модулей в проекте.

Мы можем решить эти проблемы с помощью топологической сортировки, которая берет DAG (направленный ациклический граф) и упорядочивает его узлы таким образом, что для каждого ребра x -> y, x оказывается перед y при упорядочивании.

Алгоритм Кана — один из алгоритмов, который может установить такой топологический порядок.

Алгоритм Кана: Теория

Идея алгоритма Кана проста:

1. Поместите в порядок все узлы, которые не имеют зависимостей.
2. Удалите все вхождения этих узлов из зависимостей всех оставшихся узлов. Если нет циклов, это даст вам новые узлы без зависимостей.
3. Повторяйте до тех пор, пока не останется ни одного узла.

Например:

Вот граф зависимостей (где x -> y означает, что x зависит от y.

Таким образом:

1. d не имеет зависимостей. Расположите их в порядке.
   Порядок = [d].

2. Удалите вхождения d из других зависимостей. d встречается в зависимостях b, c. Таким образом, после удаления d из этих зависимостей, ни b, ни c не имеют никаких зависимостей.

1. b и c не имеют зависимостей. Расположите их в порядке.
   Порядок = [d, b, c].

2. Удалите вхождения b и c из других зависимостей. И b, и c встречаются в зависимостях a. Таким образом, после удаления b и c из этих зависимостей, у a больше нет зависимостей.

1. Больше не осталось узлов. Выполнено. Окончательный порядок = [d, b, c, a].

Алгоритм Кана: Реализация

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

Например, если узлы B и C зависят от A, то запись в словаре будет A: [B, C].

Если перевести теорию из предыдущего раздела в код Python, то возможная реализация выглядит следующим образом:

def topological_sort(nodes: dict[str, list[str]]) -> list[str]:
    """
    Topological sort for a network of nodes

        nodes = {"A": ["B", "C"], "B": [], "C": ["B"]}
        topological_sort(nodes)
        # ["A", "C", "B"]

    :param nodes: Nodes of the network
    :return: nodes in topological order
    """

    # Calculate the indegree for each node
    indegrees = {k: 0 for k in nodes.keys()}
    for name, dependencies in nodes.items():
        for dependency in dependencies:
            indegrees[dependency] += 1

    # Place all elements with indegree 0 in queue
    queue = [k for k in nodes.keys() if indegrees[k] == 0]

    final_order = []

    # Continue until all nodes have been dealt with
    while len(queue) > 0:

        # node of current iteration is the first one from the queue
        curr = queue.pop(0)
        final_order.append(curr)

        # remove the current node from other dependencies
        for dependency in nodes[curr]:
            indegrees[dependency] -= 1

            if indegrees[dependency] == 0:
                queue.append(dependency)

    # check for circular dependencies
    if len(final_order) != len(nodes):
        raise Exception("Circular dependency found.")

    return final_order

Давайте попробуем это сделать с более развитой сетью:

Соответствующий ввод выглядит следующим образом:

nodes = {
    "A": ["B", "C"],
    "B": ["C", "D"],
    "C": ["F"],
    "D": ["F"],
    "E": ["F"],
    "F": []
}

Если мы запустим это, то получим следующий порядок:

order = topological_sort(nodes)
print(order)

# ['A', 'E', 'B', 'C', 'D', 'F']

Посмотрите еще раз на график и убедите себя, что это действительно правильный порядок, который позволяет избежать столкновения зависимостей!