В одном из недавних проектов мы работали над созданием инструмента, похожего на электронную таблицу, в котором пользователи могли бы делать перекрестные ссылки на различные строки в формулах, как в Excel. Мы столкнулись с вопросом, как упорядочить оценку строк так, чтобы зависимости не вызывали конфликтов.
Например, представьте, что у нас есть три строки:
Идентификатор строки | Формула | Воспроизведенные значения |
---|---|---|
row1 |
manual input |
1, 2, 3 |
row2 |
6, 8, 6 | |
row3 |
2, 3, 4 |
row1
может быть отображена напрямую, так как ее формула не зависит от других строк. Однако row2
ссылается на row3
. row3
ссылается на row1
. Таким образом, чтобы отобразить row2
, нам сначала нужно отобразить row3
.
Оказывается, это довольно распространенная проблема, например, при решении вопроса о порядке импорта различных модулей в проекте.
Мы можем решить эти проблемы с помощью топологической сортировки, которая берет DAG (направленный ациклический граф) и упорядочивает его узлы таким образом, что для каждого ребра x -> y
, x
оказывается перед y
при упорядочивании.
Алгоритм Кана — один из алгоритмов, который может установить такой топологический порядок.
Алгоритм Кана: Теория
Идея алгоритма Кана проста:
- Поместите в порядок все узлы, которые не имеют зависимостей.
- Удалите все вхождения этих узлов из зависимостей всех оставшихся узлов. Если нет циклов, это даст вам новые узлы без зависимостей.
- Повторяйте до тех пор, пока не останется ни одного узла.
Например:
Узел | Зависит от |
---|---|
a |
|
b |
d |
c |
d |
d |
— |
Вот граф зависимостей (где x
-> y
означает, что x
зависит от y
.
Таким образом:
-
d
не имеет зависимостей. Расположите их в порядке.
Порядок = [d
]. -
Удалите вхождения
d
из других зависимостей.d
встречается в зависимостяхb
,c
. Таким образом, после удаленияd
из этих зависимостей, ниb
, ниc
не имеют никаких зависимостей.
-
b
иc
не имеют зависимостей. Расположите их в порядке.
Порядок = [d
,b
,c
]. -
Удалите вхождения
b
иc
из других зависимостей. Иb
, иc
встречаются в зависимостяхa
. Таким образом, после удаленияb
иc
из этих зависимостей, уa
больше нет зависимостей.
- Больше не осталось узлов. Выполнено. Окончательный порядок = [
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']
Посмотрите еще раз на график и убедите себя, что это действительно правильный порядок, который позволяет избежать столкновения зависимостей!