Как определить корневые узлы в словаре Python?

Question

У меня есть словарь Python, который представляет график. Я хочу определить корневые / независимые узлы, чтобы я мог обрабатывать их одновременно, и тогда следующие узлы станут корневыми / независимыми узлами. Я запутался в том, как реализовать эту технику в python.

Ниже приведен пример словаря:

my_graph = {
            1:[4],
            2:[6],
            3:[9],
            4:[5,7],
            5:[8],
            6:[],
            7:[],
            8:[],
            9:[]
           }

Я разделю процесс на разные кадры. Ожидаемый результат в зависимости от вышеупомянутого словаря дается как:

1- начало: коренные / независимые узлы = 1,2,3

2- после кадра 1 корневые / независимые узлы = 4,6,9

3- после кадра 2 корень / независимые узлы = 5,7

4- после кадра 3 корень / независимые узлы = 8

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

Я читал о Dask и luigui , но не уверен, являются ли они окончательным решением, или я могу сделать это каким-то простым способом.

Answer 1

Это называется "топологическая сортировка". Простой алгоритм -

1. построить отображение между узлами и количеством "входящих" дуг
2. обрабатывает узлы с 0 (это "корни") и обновляет счетчики по мере того, как вы продолжаете (когда вы обрабатываете счетчик уменьшения узлов для всех соседей).

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

В вашем случае

def tsort(graph): 
    counts = dict((k, 0) for k in graph) 
    for n, neighbors in graph.items(): 
        for nh in neighbors: 
            counts[nh] = counts[nh] + 1 
    while graph: 
        roots = [k for k in graph if counts[k] == 0] 
        if not roots: 
            raise RuntimeError("Cycles present, no topological sort possible") 
        print("roots", roots) 
        for r in roots: 
            print("Processing", r) 
            for nh in graph[r]: 
                counts[nh] -= 1 
            del graph[r] 

Answer 2

Звучит так, будто вы хотите выполнить Топологическую сортировку

Вы можете использовать библиотеку, toposort , чтобы выполнить поднятие тяжестей за вас, она определит зависимости и порядок, в котором должны обрабатываться узлы:

import toposort

my_graph = {
            1:[4],
            2:[6],
            3:[9],
            4:[5,7],
            5:[8],
            6:[],
            7:[],
            8:[],
            9:[]
           }

# change values to sets (required by toposort)
for key, value in my_graph.items():
    my_graph[key] = set(value)

result = toposort.toposort(my_graph)
print(list(result))

[{6, 7, 8, 9}, {2, 3, 5}, {4}, {1}]