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

可以使用递归来完成最简单的问题解决方案。创建以下 find_max_rank_node 函数以获取我们要开始搜索的节点，它 returns 最深的节点和深度：

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()

此外，我还创建了一种名为 viz 的方法来可视化图形并将其写入如下所示的名为 file.png 的图像中：

希望这能回答您的问题！！

Answer 2

使用 NetworkX Python 库中的算法进行图形处理。

使用 pip install networkx 安装 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).

旁注

因为问题是关于 pygraphviz，我提供了将 pygraphviz 对象转换为 networkx 的解决方案。

您也可以在软件及更高版本中仅使用 networkx 图表然后使用 networkx.drawing.nx_agraph.to_agraph.

转换为 pygraphviz 图

pygraphviz：使用后继查找最大等级节点

pygraphviz: finding the max rank node using successors

python

search

loops

binary-search-tree

pygraphviz

旁注