如何对NetworkX有向图(DiGraph)节点按指定规则排序？

要完成这个需求，我们需要借助Graphviz的dot布局引擎（支持层次化布局），先让图按左到右的规则排列，再提取节点的垂直位置信息进行排序。

具体步骤及代码实现 #

1. 安装依赖库：需要networkx和pydot来对接Graphviz，执行以下命令安装：

pip install networkx pydot

2. 编写代码完成布局计算与节点排序：

import networkx as nx
from networkx.drawing.nx_pydot import to_pydot

# 初始化示例有向图
G = nx.DiGraph()
G.add_edges_from([('b','a'), ('b','c'), ('a','c'),('c','d')])

# 将NetworkX图转为pydot对象，指定布局方向为左到右
dot_graph = to_pydot(G)
dot_graph.set_rankdir("LR")

# 调用dot布局引擎计算节点位置
dot_graph.layout(prog='dot')

# 提取每个节点的垂直位置（y坐标）
node_y_pos = {}
for node in dot_graph.get_nodes():
    node_name = node.get_name().strip('"')
    pos_attr = node.get_attributes().get('pos', '')
    if pos_attr:
        _, y = pos_attr.split(',')
        node_y_pos[node_name] = float(y.strip('!'))

# 按y坐标降序排序（y值越大，节点位置越靠上）
sorted_nodes = sorted(node_y_pos.keys(), key=lambda n: -node_y_pos[n])

# 输出结果
for node in sorted_nodes:
    print(node)

结果说明 #

运行上述代码后，会输出符合预期的节点列表：

a
b
c
d

核心逻辑是：dot布局引擎在左到右排列时会自动计算节点的垂直位置，我们提取这些位置的y坐标，按y值从大到小排序，就能得到从上到下的节点顺序。

内容的提问来源于stack exchange，提问作者Sanek Zhitnik