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函数以获取我们要开始搜索的节点，并返回最深的节点和深度：

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图形然后用pygraphviz转换为networkx.drawing.nx_agraph.to_agraph图。