pygraphviz: поиск узла максимального ранга с использованием наследников

Question

Я пытаюсь найти узел максимального ранга и глубину. Вот мой код

import pygraphviz as pgv


class Test:
    def __init__(self):
        self.G = pgv.AGraph(directed=True)

        self.G.add_node('a')
        self.G.add_node('b')
        self.G.add_node('c')
        self.G.add_node('d')
        self.G.add_node('e')
        self.G.add_node('f')

        self.G.add_edge('a', 'b')
        self.G.add_edge('b', 'c')
        self.G.add_edge('b', 'd')
        self.G.add_edge('d', 'e')
        self.G.add_edge('e', 'f')
        print(self.G.string())
        self.find_max_rank_node()

    def find_max_rank_node(self):
        nodes = self.G.nodes()
        depth = 0
        for n in nodes:
            layer1 = self.G.successors(n)
            if layer1:
                depth = depth + 1
                for layer_one in layer1:
                    layer2 = self.G.successors(layer_one)
                    print(n, layer2)


if __name__ == '__main__': Test()

Выходные данные должны быть f и 4. Я начал кодировать его, но понял, что не буду знать, насколько глубока ветвь ... и я не уверен, как написать цикл.

Answer 1

Использовать алгоритм из NetworkX Библиотека Python для обработки графиков.

Установить NetworkX с pip install networkx. Тогда:

import networkx as nx
from networkx.drawing.nx_agraph import from_agraph
import pygraphviz as pgv

# constructing graph with pygraphviz
G = pgv.AGraph(directed=True)

G.add_node('a')
G.add_node('b')
G.add_node('c')
G.add_node('d')
G.add_node('e')
G.add_node('f')

G.add_edge('a', 'b')
G.add_edge('b', 'c')
G.add_edge('b', 'd')
G.add_edge('d', 'e')
G.add_edge('e', 'f')

# converting pygraphviz graph to networkx graph
X = from_agraph(G)

# dictionary {node: length}
lengths = nx.shortest_path_length(X, 'a')

result = max(lengths.items(), key=lambda p: p[1])

Результат равен ('f', 4).

---

Sidenote

Поскольку вопрос касался pygraphviz, я предоставил решение для преобразования объекта pygraphviz вnetworkx.

В качестве альтернативы вы можете использовать только networkx графики в программном обеспечении, а затем преобразовать затем в pygraphviz графики с помощью networkx.drawing.nx_agraph.to_agraph.

Answer 2

Самое простое решение вашей проблемы можно сделать, используя recursion . Следующая функция find_max_rank_node создана для получения узла, с которого мы собираемся начать поиск, и возвращает самый глубокий узел и глубину:

import pygraphviz as pgv

class Test:
    def __init__(self):
        self.G = pgv.AGraph(directed=True)

        self.G.add_node('a')
        self.G.add_node('b')
        self.G.add_node('c')
        self.G.add_node('d')
        self.G.add_node('e')
        self.G.add_node('f')

        self.G.add_edge('a', 'b')
        self.G.add_edge('b', 'c')
        self.G.add_edge('b', 'd')
        self.G.add_edge('d', 'e')
        self.G.add_edge('e', 'f')
        print(self.G.string())
        # try it out
        self.find_max_rank_node('a')    # ('f', 4)
        self.find_max_rank_node('b')    # ('f', 3)
        self.find_max_rank_node('c')    # ('c', 0)
        self.find_max_rank_node('d')    # ('f', 2)
        self.find_max_rank_node('e')    # ('f', 1)
        self.find_max_rank_node('f')    # ('f', 0)
        # visualize the graph
        self.viz()

    def find_max_rank_node(self, start_node):
        succ = self.G.successors(start_node)
        if len(succ) == 0:
            return (start_node, 0)
        else:
            deepest_node = None
            depth = 0
            for node in succ:
                n, d = self.find_max_rank_node(node)
                if d >= depth:
                    deepest_node = n
                    depth = d
            return (deepest_node, 1+depth)

    def viz(self):
        self.G.layout()
        self.G.draw('file.png')


if __name__ == '__main__': Test()

Кроме того, я создал еще один метод, который называется * 1007. * чтобы визуализировать график и написать его на изображении file.png, показанном ниже:

Надеюсь, что это ответ на ваш вопрос !!