Реализация DAG в Python - PullRequest
Новая
       70

Реализация DAG в Python

0 голосов
/ 16 июня 2020 
def get_Indegree_Of_Vertices(self):
    for ele in self.graph.keys():
        self.indegree[ele] = 0
        for i in self.graph.values():
            self.indegree[ele] += i.count(ele)
    return self.indegree

def DAG(self, root):
    # Queue is where I store all the nodes that have in-degree of zero
    queue = deque([root])
    x = queue.popleft()
    print(x)
    for neighbour in self.graph[x]:
        self.indegree[neighbour] -= 1 
        queue.append(neighbour)
        if self.indegree[neighbour] == 0:
            self.DAG(neighbour)

Здесь мой подход состоит в том, чтобы сначала найти все вершины, которые имеют нулевую внутреннюю степень, а затем найти внутреннюю степень каждой из вершин. По мере прохождения вы можете вывести степень каждой вершины. Если внутренняя степень равна нулю, выполните рекурсию ЗДЕСЬ, self.indegree и self.graph являются словарными представлениями. Не знаю, оптимален ли мой способ решения проблемы, но я просто хочу решить проблему таким образом. Также, если есть какая-то импровизация, которую можно приветствовать !!

Также я не понимаю, почему я получаю этот неподдерживаемый тип (ы) операнда ERROR для - =: 'list' и 'int'

1 Ответ

0 голосов
/ 30 июля 2020

py-dag имеет читаемую реализацию, но довольно глючную.

Код networkx DAG намного более полный, но трудный для понимания. Вот несколько простых примеров nextworkx DAG .

Если вы внедряете DAG в производственный код, вероятно, лучше всего полагаться на networkx. Если вы хотите узнать, как реализовать DAG в Python, ознакомьтесь с исходным кодом networkx.

...